9/24/21

Stacks

Akashdeep

Stack
Stack is an ordered collection of items into which new items may be inserted and from
which items may be deleted from one end, called top of stack.
Two basic operations: Push and Pop

push The stack

push

push
depth
pop (returned)

pop (returned)

peek (returned) LIFO: Last-In-First-Out

1
 9/24/21

The Stack ADT

• A linear structure of fixed or variable size

• Only the top of the stack is used to add, remove and examine
– push: add an object to the top of the stack

– pop: remove an object from the top of the stack

2
 9/24/21

– peek: examine the object at the top of the stack (pop

without removal)
• Other operations include:
– isEmpty: determines whether or not the stack is
empty
– depth: returns the number of objects in the stack
• Intermediate values from one state to another
state of stack are not stored.
• By definition there is no limit on the number of
elements in the stack.

Implementing stacks using arrays

push The array

push

push

pop (returned)

pop (returned) length

peek (returned)

3
 9/24/21

Push and pop operation

Stack Implementation in C

datatype list[ ];
void push (datatype element);
datatype pop( );
datatype peek( );
boolean isEmpty( );
main
{
call different functions;
}

4
 9/24/21

Stack Implementation in C++

class Stack
{
Private:
datatype list[];
int top;
Public:
void push (datatype element);
datatype pop( );
datatype peek( );
boolean isEmpty( );
}
9

What if list[] was not private?

• We have used information hiding by making the
instance variable ‘list’ private
• If we made it public, the class user would have direct
access to the ‘list’ variable
• Array & stack are two different objects. Array only
provides home for stack.
• Program should take corrective measures instead of
halting in case of underflow or overflow.
• This would allow the user to do more than the stack
allows
– e.g. The user could remove an element from the bottom of
the stack

10

10

5
 9/24/21

Push(Stack,Top,Maxstk,Item)
1. [Stack already filled?]
If Top=Maxstk then Print Overflow and Return;
2. Set Top=Top+1 [Increase top by 1]
3. Set Stack[Top]:= Item [Insert Item in new Top
position]
4. Return

11

Implementing the method push

int firstFree;
firstFree: 4
0
1
2
3
void push(datatype element)
{ [0] [1] [2] [3]
list
// If stack is full, Print Message
if (firstFree == length of list)
{
print (“stack is full”); return;
}

// Add new element to list element

list[firstFree] = element; ……
firstFree++;
}

12

12

6
 9/24/21

The method isEmpty

• Returns true if the stack is empty, or false if
non-empty
• How can we implement this? Try in the lab.

13

13

Pop(Stack, Top, Item)

1. [Stack has no item to remove]
If Top=0 then Print : Underflow and Return
2. Set Item = Stack[top]. [assign top element to
Item]
3. Set Top=Top-1 [Decrease top by 1]
4. Return

14

7
 9/24/21

The method pop

Datatype pop( )
{
if (Firstfree == 0) then

Print: UnderFLOW and return.

Item = LIST[FirstFree-1].

Firstfree = Firstfree-1

return (Item)

15

15

The method peek

• It returns the last element of the stack
• How can we implement this? Try in lab.

16

16

8
 9/24/21

The method depth

• It returns the number of elements in the stack
• How can we implement this?

17

17

Linked Representation of Stack

• Info field holds items of stack
• Next field indicates the next item in the stack
• Start indicates the TOP of stack element

18

9
 9/24/21

Linked Stacks (Link list implementation of stack):

Header Node

19

19

Linked Stacks (Link list implementation of

stack):
• A stack can be implemented by using link list.
• Insertion & Deletion is possible only at one end of stack (Top).

• Similarly, list can be accessed only from the pointer to first

node.
•How to implement Pop with Linked implementation
•Remove from the front in case of list is analogous to pop
function of stack.
•What about Push ??
•Insert at front in case of list is analogous to push function of stack.

20

20

10
 9/24/21

Operations on linked stack

21

PUSH_LINKSTACK(INFO,LINK,TOP,AVAIL,ITEM)

1. [Available space ?]If AVAIL=NULL, then Write

OVERFLOW and Exit.
2. [Get a NEW node from the free store [ call
malloc/new].
3. Set INFO[NEW]:=ITEM. [Copies ITEM].
4. Set LINK[NEW]:=TOP [New Node points to
original TOP Node]
5. Set TOP=NEW. [Reset TOP to point to new node
at Top of Stack]
6. Exit.

22

11
 9/24/21

POP_LINKSTACK(INFO,LINK,TOP,AVAIL,ITEM)

1. [Stack is empty?] If TOP=NULL, then Write

UNDERFLOW and Exit.
2. Set ITEM:=INFO[TOP]
3. Set TEMP:=TOP AND TOP:=LINK[TOP]. [reset
Pointers]
4. [Return deleted node to FREE SPACE] call
delete(TEMP)
5. Exit.

23

APPLICATIONS OF STACK

24

12
 9/24/21

A look into the FUNCTION Calls

Sample Code:
1 void main( ){
2 int a = 3;
3 int b = timesFive(a);
4 cout<< b;
5 }

6 int timesFive(int a){

7 int b = 5;
8 int c = a * b;
9 return (c);
10 }

25

A look into the compiler

Important:

Every call to a method creates a new set of

local variables !

These Variables are created on the stack and deleted

when the method returns

26

13
 9/24/21

A look into the compiler

Inside the compiler a stack
(system)is used
• to create the local variables
• to store the return address
from a call
• to pass the method-
parameters
• and many more things

27

Memory Layout of C/C++ Program

28

14
 9/24/21

A look into the compiler

1 void main( ) {
2 int a = 3;
3 int b = timesFive(a);
4 cout<<b;
5 }

6 int timesFive(int a){

c = 15
7 int b = 5;
b=5
8 int c = a * b; a=3
9 return (c); Return to LINE 3

10 } b
a=3

29

A look into the internals

• ... 15 Temporary storage
9 return (c);
Return to LINE 3 Return to LINE 3
10 ...

c = 15
b=5
a=3
Return to LINE 3 c = 15
Clear Stack
b b b
a=3 a=3 a=3
CIS 068

30

15
 9/24/21

A look into the internals

1 void main( ) {
2 int a = 3;
3 int b = timesFive(a);
4 cout<<b;
5 }

c = 15
b b = 15
a=3 a=3

Temporary storage
CIS 068

31

A look into the internals

1 void main( ) {
2 int a = 3;
3 int b = timesFive(a);
4 cout<<b;
5 }

clear stack from local variables

32

16
 9/24/21

Recursion

• Sometimes, the best way to solve a problem is by

solving a smaller version of the exact same
problem first

• Recursion is a technique that solves a problem by

solving a smaller problem of the same type

• A procedure that is defined in terms of itself

33

Recursion

When you turn that into a program, you end up with functions
that call themselves:

Recursive Functions

34

17
 9/24/21

RECURSION
Suppose P is a procedure containing either a Call
statement to itself. Then P is called a recursive
procedure.
Recursive procedure must have the following
properties:
1. There must be certain criteria, called base criteria,
for which the procedure does not call itself.
2. Each time the procedure does call itself, it must be
closer to the base criteria.

35

Space
occupied

36

18
 9/24/21

Time Complexity
• T(n) = 1 if n ==0
• T(n) = T(n-1) + 1 if n >=1
• T(n-1) = T (n-2) +1
T(n-2) = T (n-3) +1
Backward Substituting:
• T(n)= T ((n-2) +1 ) + 1
= T ( n-2) + 2
= T (( n-3) +1) +2
= T (n-3) + 3
……
= T ( n-k) + k
• We need to omit term of T . We know that the T ‘s term will vanish when recursion will
stops and it will stop when n-k=0 or n=k
• Substituting value of k in the equation we get
= T(n-n) + n
= T(0) + n
=1+n
Or O(n)
37

Another Example

39

19
 9/24/21

40

41

20
 9/24/21

Iterative Factorial
Iterative definition
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1

int factorial (int n)

{
int i, result;
result = 1;
for (i = 1; i <= n; i++) {
result = result * i;
}
return ( result );
}

42

42

Recursive Factorial
Recursive N! definition
N! = 1 if N = 0
= N * (N-1)! Otherwise
int factorial ( int n)
{
if (n == 0)
return (1);

return (n * factorial(n - 1) );
}

43

43

21
 9/24/21

Iterative vs Recursive factorial

Iterative Recursive
1. 2 local variables 1. No local variables
2. 3 statements 2. One statement
3. Saves solution in an 3. Returns result in
intermediate variable single expression

Recursion simplifies factorial by making the computer do the work.

But we aren’t seeing the stack manipulations which require pushing a new n,
space for the function’s return value, and updating the stack pointer register,
and popping off the return value and n when done

44

44

How does it work?

Each recursive call creates an “activation
record” which contains
-local variables and parameters
-return address
and is saved on the stack.

45

45

22
 9/24/21

Recursion
What’s behind this function ?

int f(int a){

if (a==1)
return(1);
else
return(a * f( a-1));
}

46

Factorial
Factorial:

a! = 1 * 2 * 3 * ... * (a-1) * a
Note:
a! = a * (a-1)!
remember:
...splitting up the problem into a smaller problem of the same type...

a!

a * (a-1)!

a-1 a-2!

47

23
 9/24/21

Tracing the example

int factorial(int a){
if (a==0)
return(1); RECURSION !
else
return(a * factorial( a-1));
}

48

Watching the Stack

int factorial(int a){
if (a==1)
return(1);
else
return(a * factorial( a-1));
}

a=1
Return to L4
a=2
Return to L4
a=3
Return to L4
a=4 a=4
Return to L4 Return to L4
a=5 a=5
… a=5
Initial After 1 recursion After 4th recursion

Every call to the method creates a new set of local

variables !
49

24
 9/24/21

Watching the Stack

int factorial(int a){
if (a==1)
return(1);
else
return(a * factorial( a-1));
}

a=1
Return to L4
a=2 a = 2*1 = 2
Return to L4 Return to L4
a=3 a=3 a = 3*2 = 6
Return to L4 Return to L4 Return to L4
a=4 a=4 a=4 a = 4*6 = 24
Return to L4 Return to L4 Return to L4 Return to L4
a=5 a=5 a=5 a=5 a = 5*24 = 120
After 4 recursion
th Result

50

Properties of Recursive Functions

Problems that can be solved by recursion have these characteristics:
• One or more stopping cases have a simple, nonrecursive solution
• The other cases of the problem can be reduced (using recursion) to
problems that are closer to stopping cases
• Eventually the problem can be reduced to only stopping cases, which are
relatively easy to solve

Follow these steps to solve a recursive problem:

• Try to express the problem as a simpler version of itself
• Determine the stopping cases
• Determine the recursive steps

51

25
 9/24/21

Solution
The recursive algorithms we write generally consist of an if statement:
IF
the stopping case is reached solve it
ELSE
split the problem into simpler cases using recursion

Solution on stack
Solution on stack
Solution on stack

52

Common Programming Error

Recursion does not terminate properly:

Stack Overflow !

53

26
 9/24/21

Ensuring that Recursion Works

Using “factorial” as an example,

1. A recursive subprogram must have at least one base case and

one recursive case (it's OK to have more than one base case
and/or more than one recursive case).
The first condition is met, because if (a==1) return 1
is a base case, while the "else" part includes a recursive
call (factorial(a-1)).
2. The test for the base case must execute before the recursive
call.
If we reach the recursive call, we must have already evaluated
if (a==1); this is the base case test, so this criterion is met.

54

54

Does It Work? (cont’d)

3. The problem must be broken down in such a way that the
recursive call is closer to the base case than the top-level
call.
The recursive call is factorial(a-1). The argument to the
recursive call is one less than the argument to the top-
level call to factorial. It is, therefore, closer” to the base
case of a=1.
4. The recursive call must not skip over the base case.

Because a is an integer, and the recursive call reduces n

by just one, it is not possible to skip over the base case.

55

55

27
 9/24/21

Does It Work? (cont’d)

5. The non-recursive portions of the subprogram must operate
correctly.

-Assuming that the recursive call works properly, we must now

verify that the rest of the code works properly. We can do this
by comparing the code with our definition of factorial. This
definition says that if a=0 then a! is one.
-Our function correctly returns 1 when a is 1. If a is not 1, the
definition says that we should return (a-1)! * a.
-The recursive call (which we now assume to work properly)
returns the value of a-1 factorial, which is then multiplied by a.
Thus, the non--recursive portions of the function behave as
required.

56

56

Matching Balancing Parenthesis

n Given an expression of ‘(‘ and ‘)’, a ‘(‘ must
match with a ‘)’, or else it is illegal.

( )( ), ( ( ( ) ) ), ( ( ( ) ) ( ) ) are all legal, while

( ( ) (, ) ( ) ( are all illegal.

n Obviously, counting the numbers of ‘(‘ and ‘)’

in the expression is not enough.

57

57

28
 9/24/21

Matching Balancing Parenthesis

n Insights à By convention, the expression is
reading from left-to-right. A ‘)’ is matched with
the closest, unmatched ‘(‘ on its left.

For example,
((())())

58

58

Matching Balancing Parenthesis

n Suppose we have a ‘)’. How do we know
which ‘(’ is closest and unmatched?
u If we read the expression from left-to-right, the
MOST RECENTLY UNMATCHED ‘(’ is
cancelled with ‘)’.
u How can we keep track of the MOST
RECENTLY READ (LAST) ‘(’ ? (keep in mind
there are many pending unmatched ‘(’).
« Which data structure is keeping track of the most recent item ?

Stack ß LIFO structure

59

59

29
 9/24/21

Matching Balancing Parenthesis: Algorithm

n When we see a ‘(‘, we push it into a stack.
n When we see a ‘)’, we pop ‘(‘ from the stack.
This ‘(‘ matches with current ‘)’.
u What happen if the stack is empty (meaning
there is no such ‘(’) at that moment ?
It means the input is illegal.
n What happen if we have finished reading the
expression, but the stack is not empty ?
u It means there are more ‘(‘ than ‘)’ in the
expression.
It means the input is illegal.
60

60

61

30
 9/24/21

Applications of STACK
• If Q is any arithmetic expression, find the value of Q by using
reverse polish notation.
• Polish Notation
- infix notation is A + B, C- D
- Polish Notation is + A B, - C D

- Reverse Polish refers to analogous definition in which

operator is placed after operands. Ie AB+, C D-

62

Use of the stack data structure:

postfix notation (Reverse Polish)
• Infix: The operator is written between the operands
Postfix: The operator is written after the operands
– infix: 3+4 postfix:3 4 +
– infix: 2+3*4 postfix:2 3 4 * +
– infix: 2*3+4 postfix:2 3 * 4 +

• Consider the expression 13 – 2 * (5 * 2 – 4)

– Think about your eye movements as you try to evaluate it
– This is inefficient for a computer! (has to read it several
times)
• Post fix is a way to represent any expression.
• If an expression is in Postfix notation then it is easier
for computer to evaluate the expression.
63

63

31
 9/24/21

Infix to Postfix Expressions

n Infix expression
u Suppose the expression only has operators ‘*’
and ‘+’; and ‘*’ has a higher precedence than
‘+’.
u So, 5+2+3 = 10, and 1+2*4=9, etc.
u The expression may also have parenthesis to
complicate the problem, i.e.,
1. (1+2)*4=12
2. (1+2*5+1)*3=36.
3. (1+2*(5+1))*3=39.

Applications of Stacks 64

64

Infix to Postfix Expressions

n Postfix expression
1. 13+
2. 1 2 4 * +
3. 1 2 + 4 *
4. 6 5 2 3 + 8 * + 3 + *
are all postfix expressions.
n No ‘(‘, ‘)’ is in the expression.
n Computer converts infix expression into postfix
(reverse polish notation) and then evaluates it. Stack
is an important tool for both operations.
n To evaluate a postfix expression, we need a
stack. Applications of Stacks 65

65

32
 9/24/21

Infix to Postfix Expressions

n Evaluate a postfix expression.
1. Read the expression from left-to-right.
2. When a number is seen, it is pushed onto the
stack.
3. When an operator is seen, the operator is
applied to the two numbers that are popped
from the stack. The result is pushed on the
stack.

66

66

Evaluation of a POSTFIX Expression

1. Add a right parenthesis “)” at the end of P. [acts like sentinel]
2. Scan P from left to right and repeat steps 3 and 4 for each
element of P until “)” is encountered.
3. If an operand is encountered ,put it on STACK.
4. If an operator * is encountered, then:
a) Remove the two top elements of STACK, where A is the top
element and B is the next-to-top element.
b) Evaluate B * A.
c) Place the result of (b) back on STACK.
[ End if]
[End of step 2 Loop]
5. Set VALUE equal to the top element on STACK.
6. Exit.

67

33
 9/24/21

STACK
5

5,6

30

30,10

20

68

68

Infix to Postfix Expressions

n Example : 6 5 2 3 + 8 * + 3 + *

69

69

34
 9/24/21

infix-to-postfix using a stack:

Suppose Q is an arithmetic expression written in infix notation.
This algorithm finds the equivalent postfix expression P.
1. Push ‘(' onto STACK, and add ‘)’ to the end of Q
2. Scan Q from left to right and repeat Steps 3 to6 for each element of Q until the STACK is
empty.
3. If an operand is encountered, add it to P
4. If a left parenthesis is encountered, push it onto STACK
5. If an operator (op) is encountered, then
(a) Repeatedly pop from STACK and add to P each operator (on the top of STACK) which has
the same precedence as or higher precedence than operator (op)
(b) Add (op) to STACK.
/*End of If structure*/
6. If a right parenthesis is encountered, then
(a) Repeatedly pop from STACK and add to P each operator (on the top of STACK)
until a left parenthesis is encountered.
(b) Remove the left parenthesis. [Do not add the left parenthesis to P]
/*End of If structure*/
/*End of Step 2 loop*/
7. Exit.
70

70

Example : Q:- A + ( B * C – ( D / E ^ F ) * G ) * H

71

71

35
 9/24/21

Symbol Scanned Stack Expression P

1 A ( A Q:- A + ( B * C – ( D / E ^ F ) * G ) * H )
2 + ( + A
3 ( ( + ( A
4 B ( + ( A B
5 * ( + (* A B
6 C ( + ( * A B C
7 - ( + ( - A B C *
8 ( ( + ( -- ( A B C *
9 D ( + ( -- ( A B C * D
10 / ( + ( -- ( / A B C * D
11 E ( + ( -- ( / A B C * D E
12 ^ ( + ( -- ( / ^ A B C * D E
13 F ( + ( -- ( / ^ A B C * D E F
14 ) ( + ( -- A B C * D E F ^ /
15 * ( + ( -- * A B C * D E F ^ /
16 G ( + ( -- * A B C * D E F ^ / G
17 ) ( + A B C * D E F G * --
18 * ( + * A B C * D E F ^ / G * --
19 H ( + * A B C * D E F ^ / G * -- H
20 ) A B C * D E F ^ / G * -- H * +

72

MERGE SORT

74

74

36
 9/24/21

Merging

• Merging is the
process of
combining two or
more sorted
arrays into a third
sorted array.

75

75

Merging

76

76

37
 9/24/21

Merging

77

77

Merging

78

78

38
 9/24/21

Merging

79

79

Merging
merge( A,p,q,r) // merge procedure
{
n1=q-p+1;
n2=r-q;
//Let L[1,2,...n+1] and R[1 to n2+1] be new arrays
for(i=1 to n1)
L[i]=A[p+i-1]
for (j=1 to n2)
R[j]=A[q+j]
L[n1+1]= INFY
R[n2+1]= INFY
i=1, j=1
for ( k= p to r)
{ if (L[i]<=R[j])
A[k]=L[i]
i=i+1;
else
A[k]=R[j]
j=j+1;
}
}

80

39
 9/24/21

Example of merge procedure

Complexity of procedure MERGE

• N for copying From A to L and R ( sub-lists)
• (n) comparisons are required and adding with number of copies =O(n+n)
• Space complexity of is the order O(n) as extra space is required to store elements ( out of place
sort)

81

Merge Sort [divide and conquer sorting]

Algorithm:
– Divide: If S has at least two elements (nothing needs to be
done if S has zero or one elements, just return S),
– remove all the elements from S and put them into two
sequences, S1 and S2, each containing about half of the
elements of S. (i.e. S1 contains the first én/2ù elements and
S2 contains the remaining ën/2û elements.
– Recur: Recursively sort sequences S1 and S2.
– Conquer: Put back the elements into S by merging the
sorted sequences S1 and S2 into a sorted sequence.

82

82

40
 9/24/21

Merge Sort (Divide)

5 1 4 2 10 3 9 15

5 1 4 2 10 3 9 15

5 1 4 2 10 3 9 15

5 1 4 2 10 3 9 15

83

83

Merge Sort (conquer)

1 2 3 4 5 9 10 15

1 2 4 5 3 9 10 15

1 5 2 4 3 10 9 15

5 1 4 2 10 3 9 15

84

84

41
 9/24/21

Merge Sort – Another Example

18 26 32 6 43 15 9 1 22 26 19 55 37 43 99 2

18 26 32 6 43 15 9 1 22 26 19 55 37 43 99 2

18 26 32 6 43 15 9 1 22 26 19 55 37 43 99 2

18 26 32 6 43 15 9 1 22 26 19 55 37 43 99 2

18 26 32 6 43 15 9 1 22 26 19 55 37 43 99 2

85

Merge Sort – Another Example

Original Sequence Sorted Sequence
18 26 32 6 43 15 9 1 1 6 9 15 18 26 32 43

18 26 32 6 43 15 9 1 6 18 26 32 1 9 15 43
43

18 26 32 6 43 15 9 1 18 26 6 32 15 43 1 9

18 26 32 6 43 15 9 1 18 26 32 6 43 15 9 1

18 26 32 6 43 15 9 1

Comp 122

86

42
 9/24/21

Merge Sort Algorithm

• Divide and conquer
• Array A with elements from p to r

merge_sort(A,p,r)
{
if p<r
{
q=(p+r)/2;
merge_sort(A,p,q)
merge_sort(A,q+1,r)
merge(A,p,q,r)
}
}

87

88

43
 9/24/21

First Step

89

Second Step

90

44
 9/24/21

91

Final list is retrieved

92

45
 9/24/21

Space required
• Extra space is required for merging as merge will need
extra space.
• Once merge is active no other copy of merge is active
simultaneously.
• Extra space is equal to number of elements = O(n)
• Space required for function calls.
• Total function calls = 16 in last case but only (4) equal to
height of tree calls are active
• Genrally number of levels in stack is log(n)+1
• Size of stack is log(n) +1
• Total space = O(n) + O(log(n)) ~ O(n)

93

94

46
 9/24/21

95

Analysis of Merge Sort

• Let the time to carry out a MergeSort on n elements be
T(n)
• Assume that n is a power of 2, so that we always split into
equal halves
• For n=1, the time is constant, so we can take T(1) = 1
• Otherwise, the time T(n) is the time to do two MergeSorts
on n/2 elements, plus the time to merge, which is linear
• So, T(n) = 2 T(n/2) + n
• Divide through by n to get T(n)/n = T(n/2)/(n/2) + 1
• Replacing n by n/2 gives, T(n/2)/(n/2) = T(n/4)/(n/4) + 1
• And again gives, T(n/4)/(n/4) = T(n/8)/(n/8) + 1

97

97

47
 9/24/21

Analysis of Merge Sort

• And again gives, T(n/4)/(n/4) = T(n/8)/(n/8) + 1
• We continue until we end up with T(2)/2 = T(1)/1 + 1
• Since n is divided by 2 at each step, we have log2n steps
• Add all equations
T(N) / N + T(N/2) / (N/2) + T(N/4) / (N/4) + … + T(2)/2 =
T(N/2) / (N/2) + T(N/4) / (N/4) + ….+ T(2) / 2 + T(1)
/ 1 + LogN
• After crossing equal terms on both sides gives T(n)/n =
T(1)/1 + log2n
• That is, T(n)/n = log2n + 1
• So T(n) = n log2n + n = O(n log n)
• Although this is an O(n log n) algorithm, it is hardly ever
used for main memory sorts because it requires linear
extra memory

98

98

Quick Sort [divide and conquer sorting]

• Quick Sort is the fastest known sorting algorithm in
practice.
• It was devised by C.A.R. Hoare in 1962
• Its complexity is O( n log n).
• It has worst-case complexity of O(n2).

99

99

48
 9/24/21

Quick Sort [divide and conquer sorting]

The idea is as follows:
1. If the number of elements to be sorted is 0 or 1, then
return
2. Pick any element ‘a’ from any location within an array of
size ‘n’. This is called the pivot. Let it be jth element.
3. Partition the other elements into two disjoint sets, S1 of
elements £ ‘a’, and S2 of elements > ‘a’. Hence elements
from 0 to (j-1) are less or equal then ‘a’ and elements
from (j+1) to (n-1) are greater than ‘a’.
4. Repeat the above process for each sub-array S1 and S2
and for any sub-array created by the process in successive
iterations.

100

100

Idea of Quick Sort

1) Select: pick an element

2) Divide: rearrange elements so that x goes to

its final position E

3) Sort both the parts.

101

101

49
 9/24/21

QuickSort- Recursive

102

QuickSort

The Pseudo-Code

103

50
 9/24/21

Complexity of Quick Sort

104

Complexity of Quick sort

• Worst case running time is (n2 /2 )
• Worst case occurs when list is already sorted.
– First element will make n comparisons to identify that its at its correct position.
– First sublist will have only one element and second has (n-1) elements
– Second element will again require n-2 comparisons and so on.
• Average running time of n log n. Because on average two sub-
lists are produced at every step.
Step 1 = 2 sublists
Step 2 = 4=22 sublists …..
Step k = 2k or it must be equal to n. or total steps = log2 (n)
There are n comparisons at every step.

105

51
 9/24/21

Worst Case complexity

• T(n) = T (n-1) + O(n)
= T(n-1) + cn
= T( n-2) + c(n-1) + cn ( Back substituting)
= T(n-3) + c(n-2) + c(n-1) + cn
= c.1 + c.2 + c.3 +………. c(n-1) + cn
= O (n2)

106

What if the division is of ratio 1:9

107

52
 9/24/21

Maximum levels will be from the right

half of the tree
• N-àn/(10/9)--à n/(10/9)^2………

• = log n10/9

~ log n. or Theta(log n.)

2 2

108

Towers of Hanoi
• Move n (4) disks from pole A to pole C
• such that a disk is never put on a smaller disk

AA B
B C
C

109

53
 9/24/21

For n=3, steps are

110

• Move n (4) disks from A to C

– Move n-1 (3) disks from A to B
– Move 1 disk from A to C
– Move n-1 (3) disks from B to C

A B C

111

54
 9/24/21

Figure a and b
a) The initial state; b) move n - 1 disks from A to C

112

Figure c and d
c) move one disk from A to B; d) move n - 1 disks from C to B

113

55
 9/24/21

Hanoi towers
void solveTowers(int count, char source,
char destination, char spare)
{

if (count == 1)
{
cout<< "Move top disk from pole " <<source<< " \t---->"<<destination<<"\n";
}
else
{
solveTowers(count-1, source, spare, destination); // X
solveTowers(1, source, destination, spare); // Y
solveTowers(count-1, spare, destination, source); // Z
} // end if

114
} // end solveTowers

Recursion tree:
The order of recursive calls that results from solveTowers(3,A,B,C)

115

56
 9/24/21

Figure 2.21a
Box trace of solveTowers(3, ‘A’, ‘B’, ‘C’)

A B C

A B C

A B C

A B C

116

Figure 2.21b
Box trace of solveTowers(3, ‘A’, ‘B’, ‘C’)

A B C

A B C

A B C

A B C

117

57
 9/24/21

Figure 2.21c
Box trace of solveTowers(3, ‘A’, ‘B’, ‘C’)

A B C

A B C

A B C

A B C

118

Figure 2.21d
Box trace of solveTowers(3, ‘A’, ‘B’, ‘C’)

A B C

119

58
 9/24/21

Figure 2.21e
Box trace of solveTowers(3, ‘A’, ‘B’, ‘C’)

120

Cost of Hanoi Towers

• How many moves is necessary to solve Hanoi
Towers problem for N disks?
• moves(1) = 1
• moves(N) = moves(N-1) + moves(1) + moves(N-1)
• i.e.
moves(N) = 2*moves(N-1) + 1

• Guess solution and show it’s correct with Mathematical

Induction!

121

59
 9/24/21

T(n) = 2*T(n-1) + 1
• T(n) = 2 * ( 2 * T(n-2) + 1) + 1
• T(n) = (2 ^ 2) * T(n-2) + 2^1 + 2^0
• T(n) = (2^k) * T(n-k) + 2^(k-1) + 2^(k-2) + ... +
2^0
• Solving this the closed from comes out to be
• T(n) = (2^n) - 1 with T(0) = 0

122

Space Complexity:
• Space for parameter for each call is independent of n
i.e., constant. Let it be k . When we do the 2nd
recursive call 1st recursive call is over . So, we can
reuse the space of 1st call for 2nd call . Hence ,
• T(n) = T(n-1) + k
• T(0) = k
• T(1) = 2k
• T(2) = 3k
• T(3) = 4k
• So the space complexity is O(n).

124

60