Data Structure (KCS-301)
Unit 3
Prepared By
N. U. Khan
Computer Science And Engineering Department
IMS Engineering College, Ghaziabad
N U Khan 1
Quick Sort
In Insertion sort the key ‘X’ currently controlling the insertion is placed
into the right spot with respect to the sorted sub array
Sorted (All No <= ‘X’) Sorted (All No > ‘X’) X Unsorted Array
Pivot
Quick sort differ from insertion sort, in that the key ‘X’ controlling the
insertion is placed at the right spot with respect to the whole array
X Unsorted Array ( All No < ‘X’ ) Unsorted Array (All No > ‘X’ )
Pivot
Hence after this positioning has been made, the original array is
partitioned into two sub arrays
Left sub array contains all elements smaller than pivot value
Right sub array contains all elements greater than pivot value
N U Khan 2
0 1 2 3 4 5 6 7 8 9 10 11
44 33 11 55 77 90 40 60 99 22 88 66
After one pass, Insertion of ‘44’ placed at the right spot (i.e. index number 4) with
respect to the whole array
0 1 2 3 4 5 6 7 8 9 10 11
40 33 11 22 44 90 77 60 99 55 88 66
All No < 44 All No > 44
0 1 2 3 4 5 6 7 8 9 10 11
11 22 33 40 44 55 60 66 77 88 90 99
N U Khan 3
Quick Sort
A quick sort first selects a value, which is called the pivot value. Although
there are many different ways to choose the pivot value, we will simply use
the first number in the array.
X Unsorted Array
The role of the pivot value is to assist with splitting the array.
The partition process will find the split point by moving other elements to
the appropriate side of the list w.r.t. pivot value,
Moving larger values to the right side of array and
Smaller values to left side of array.
X Unsorted Array ( All No <Unsorted
‘X’ ) Array
Unsorted Array (All No > ‘X’ )
Pivot
After finding the right position of pivot element, Insert it into this location
Hence after this positioning has been made, the original array is
partitioned into two sub arrays
N U Khan 4
Quick Sort
• Quick sort is highly unstable algorithm
• It is recursive algorithm.
• It uses the idea of divide and conquer.
• This algorithm finds the element, called pivot, that partitions the
array into two halves in such a way that
• the elements in the left subarray are less than the partitioning
element (pivot)
• and the elements in the right sub array are greater than the
partitioning element (pivot).
• Then these two subarrays are sorted separately.
• This procedure is recursive in nature with base criteria “the number
of elements in the array are not more than one”.
• This algorithm is also called partition-exchange sort
• This sorting technique has the best average behaviour among all the
sorting methods
N U Khan 5
LB For better understanding you can watch recorded video UB
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
44 33 11 22 77 90 40 60 99 55 88 66
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
44 33 11 22 77 90 40 60 99 55 88 66
up=4
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
44
40 33 11 22 40 90 77 60 99 55 88 66
LB up-1 up+1 UB
up=4
A[0] A[1] A[2] A[3] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
Now: down > up
40 33 11 22 44 90 77 60 99 55 88 66
Pivot N U Khan
Quick Sort
int partition(int A[], int LB, int UB)
{
int pivot, down, up;
down = LB;
up = UB + 1;
void Q_Sort( int A[], int LB, int UB )
pivot = A[LB]; {
while(down<=up) int u;
{
do
{ if( LB < UB )
down = down+1;
} while( A[down] < pivot); {
do u = partition(A, LB, UB);
{
up = up – 1; Q_Sort(A, LB, u-1);
} while(A[ up ] > pivot); Q_Sort(A, u+1, UB);
if( down < up ) }
{ }
swap( A[down], A[up] );
}
}
swap( A[LB], A[up]);
return(up);
}
N U Khan 7
Time complexity analysis of Quick Sort
int partition(int A[], int LB, int UB)
{
int pivot, down, up;
down = LB;
up = UB + 1;
pivot = A[LB];
while(down<=up)
{
do
{
down = down+1;
} while( A[down] < pivot);
Time complexity is directly proportional to total
do number of comparison in whole
{
up = up – 1; Time complexity = Total No of Compression
} while(A[ up ] > pivot);
(depend upon the data size )
if( down < up )
{ Time complexity = c’ * N
swap( A[down], A[up] );
}
}
swap( A[LB], A[up]); Time complexity of partition function = O( N )
return(up);
}
N U Khan 8
Quick sort time complexity
• Best Case behaviour (Balanced partition):
• Quicksort's best case occurs when the pivot (partitioning
element) are always right in the middle after partitioning of
array.
• If N is odd, then left and right sub array contain (N-1)/2
elements in each array
• If N is even, then one part contain N/2 elements and
another one will contain N/2 – 1 elements
• Worst Case behaviour (Unbalanced partitioned):
• In this case numbers are already sorted, so if we select the
first element as pivot then
• One partition contains no (zero) element and another
contain (N-1) elements
N U Khan 9
Best case ( In this, partitioning element are always right in the middle after
partitioning of array. )
8 15 3 14 6 11 7 12 4 9 5 10 2 13 1
4 1 3 2 6 5 7 8 12 9 11 10 14 13 15
2 1 3 4 6 5 7 10 9 11 12 14 13 15
1 2 3 5 6 7 9 10 11 13 14 15
N U Khan 10
Time complexity analysis in best case
void Q_Sort( int A[], int LB, int UB ) T(N)
{
int u; 1
if( LB < UB ) 1
{
u = partion(A, LB, UB); c’ * N
Q_Sort(A, LB, u-1); T ( N/2 )
Q_Sort(A, u+1, UB); T ( N/2 )
}
}
T ( N ) = 2 + c’N + T(N/2) + T(N/2)
T ( N ) = cN + 2*T(N/2)
N U Khan 11
For better understanding you can watch recorded video
Time complexity analysis in best case
T (N) cN
T (N/2) O( N log2N ) T (N/2) cN
T (N/4) T (N/4) T (N/4) T (N/4) cN
T (N/23) T (N/23) T (N/23) T (N/23) T (N/23) T (N/23) T (N/23) T (N/23) cN
• . • . • . • . • . • . • . • .
• . • . • . • . • . • . • . • .
• . • . • . • . • . • . • . • .
T (N/2k) T (N/2k) T (N/2k) T (N/2k) T (N/2k) T (N/2k) T (N/2k) T (N/2k) cN
Size of array at k’th step = N/2k = 1 Total # of comp=(k+1)cN
N U Khan 2k = N k = log2N =(log2N+1)cN
1 2 3 4 5 6 7 8
Worst case In this case numbers
are already sorted, so if we select
the first element as pivot then,
One partition contains no
2 3 4 5 6 7 8
element and another contain
(N-1) elements
3 4 5 6 7 8
4 5 6 7 8
5 6 7 8
6 7 8
7 8
N U Khan 8 13
Time complexity analysis in worst case
void Q_Sort( int A[], int LB, int UB ) T(N)
{
int u; 1
if( LB < UB ) 1
{
u = partion(A, LB, UB); c’ * N
Q_Sort(A, LB, u-1); T(0)
Q_Sort(A, u+1, UB); T ( N-1 )
}
}
T ( N ) = 2 + c’N + T(0) + T(N-1)
T ( N ) = cN + T(0)+T(N-1)
N U Khan 14
Time complexity analysis in worst case
T (N) cN
T (0) T (N-1) c(N-1)
T (0) T (N-2) c(N-2)
T (0) T (N-3) c(N-3)
• .
• .
• .
T (1) c (1)
Total # of comp=c[ N + (N-1) + (N-2) + (N-3)+ ……. +3 + 2 + 1 ]
=c[ N * (N+1)/2 ]
N U Khan Time complexity = O( N2 )
For better understanding you can watch recorded video
Space Complexity
• Quick Sort is in-place Algorithm:
• It is in-place sorting algorithm as it uses extra space only for
storing recursive function calls but not for manipulating the
input. Array is remain in main function and in each call of
recursive function right spot of pivot is reflected in array (main
body)
• Space complexity depends upon the height of recursion tree.
• Space complexity in best case = max depth of recursion tree k + 1
• = O(k)
• here k = log2N
• = O(log2N)
• Space complexity in worst case = depth of recursive calls
• = O(N)
N U Khan 16
Space complexity analysis in best case
HEAP
Q (15) AREA
Q (7) Q (7)
Q(1)
Q (3) Q (3) Q (3) Q (3)
Q(3)
Q(7)
Q (1) Q(1) Q(1) Q(1) Q(1) Q(1) Q(1) Q(1) Q(15)
Q(int A[], int L, int U) main()
main() { Max memory consumption
Global
{ if( L < U ) = depth of recursion
variable
….. { …… =k
Q(A, L, u-1); = log2N Code
Q(A, 0, N-1);
Q(A, u+1, U); =O(log2N)
} section
}
N U Khan
}