Course Name: CS302-Design an
analysis of Algorithm
Credit Hours: 3
Department of Computer Science | FAST-NU 1
Home Task
Solve T(n) = 2T(n/2) + n2:
Quick sort
Quick Sort
Asits name implies, quicksort is the fastest
known sorting algorithm in practice.
It is very fast, mainly due to a very tight and highly
optimized inner loop
Its average running time is O(n log n)
It has O(n2) worst-case performance,
The quicksort algorithm is simple to understand
and prove correct
Like mergesort, quicksort is a divide-and-conquer
recursive algorithm
Quick Sort
The basic algorithm to sort an array S consists
of the following four easy steps:
If the number of elements in S is 0 or 1, then return
2. Pick any element v in S. This is called the pivot.
3. Partition S - {v} (the remaining elements in S)
into two disjoint groups: S1 = {x ∈ S - {v}| x ≤ v}
and S2 = {x ∈ S - {v}| x ≥ v}
4. Return { quicksort(S1) followed by v followed by
quicksort(S2) }
Quick Sort
Since the partition step ambiguously
describes what to do with elements equal to
the pivot, this becomes a design decision.
Part of a good implementation is handling this
case as efficiently as possible.
Intuitively, we would hope that
about half the keys that are equal to the pivot go
into S1
while the other half into S2, much as we like binary
search trees to be balanced.
Quick Sort –
Selecting
the Pivot
Quick Sort – Selecting the Pivot
1- The popular, uninformed choice:
Use the first element as the pivot
This is acceptable if the input is random
But, if the input is presorted or in reverse order, then the pivot
provides a poor partition, because virtually all the elements go
into S1 or S2
It happens consistently throughout the recursive calls
Quicksort will take quadratic time to do essentially
nothing at all, which is quite embarrassing
2- A Safe Maneuver
A safe course is merely to choose the pivot randomly
This strategy is generally perfectly safe, unless the random
number generator has a flaw
However, random number generation is generally an
expensive commodity and does not reduce the average
running time of the rest of the algorithm at all
Quick Sort – Selecting the Pivot
The best choice of pivot would be the median of the
file.
The median of a group of n numbers is the (n/2)-th
largest number
Unfortunately, this is hard to calculate and would slow
down quicksort considerably
A good estimate can be obtained by picking three
elements randomly and using the median of these
three as pivot.
The randomness turns out not to help much
So, the common course is to use as pivot the
median of the left, right and center elements
A = {8, 1, 4, 9, 6, 3, 5, 2, 7, 0} center = A[left + right)/2]
= A [(0+9)/2] = A[4] = 6
pivot: v= median(8, 6, 0) = 6
QuickSort :Partitioning strategy
Example
8 (0) 1 (1) 4 (2) 9 (3) 6 (4) 3 (5) 5 (6) 2 (7) 7 (8) 0 (9)
i pivot j
The basic algorithm
While i is to the left of j,
we move i right, skipping over elements smaller than the pivot
We move j left, skipping over elements larger than the pivot
When i and j have stopped,
i is pointing at a large element, and
j is pointing at a small element
If i is to the left of j,
those elements are swapped
The effect is to push a large element to the right and a small
element to the left.
In the example above, i would not move and same for the j
QuickSort :Partitioning strategy
Step 1
8 (0) 1 (1) 4 (2) 9 (3) 6 (4) 3 (5) 5 (6) 2 (7) 7 (8) 0 (9)
i j pivot
QuickSort :Partitioning strategy
Step 1
8 (0) 1 (1) 4 (2) 9 (3) 0 (4) 3 (5) 5 (6) 2 (7) 7 (8) 6 (9)
i j pivot
Start by swapping the pivot with the right,
starting j at right -1
A[i] = 8 > pivot
Stop i right over here
QuickSort :Partitioning strategy
Step 1
8 (0) 1 (1) 4 (2) 9 (3) 0 (4) 3 (5) 5 (6) 2 (7) 7 (8) 6 (9)
i j j pivot
A[j] = 7 > pivot
Move Left
A[j] = 2 < pivot
Stop j right over here
Swap A[i] and A[j]
QuickSort :Partitioning strategy
Step 1
2 (0) 1 (1) 4 (2) 9 (3) 0 (4) 3 (5) 5 (6) 8 (7) 7 (8) 6 (9)
i j pivot
A[j] = 7 > pivot
Move Right
A[j] = 2 < pivot
Stop j right over here
Swap A[i] and A[j]
QuickSort :Partitioning strategy
Step 2
2 (0) 1 (1) 4 (2) 9 (3) 0 (4) 3 (5) 5 (6) 8 (7) 7 (8) 6 (9)
i i i i j j pivot
A[i] = 2 < pivot A[j] = 8 > pivot
Move Right Move Left
A[i] = 1 < pivot A[j] = 5 < pivot
Move Right Stop j right over here
A[i] = 4 < pivot
Move Right
A[i] = 9 > pivot
Stop i right over here
QuickSort :Partitioning strategy
Step 2
2 (0) 1 (1) 4 (2) 5 (3) 0 (4) 3 (5) 9 (6) 8 (7) 7 (8) 6 (9)
i j pivot
A[i] = 2 < pivot A[j] = 8 > pivot
Move Right Move Left
A[i] = 1 < pivot A[j] = 5 < pivot
Move Right Stop j right over here
A[i] = 4 < pivot
Move Right Swap A[i] and A[j]
A[i] = 9 > pivot
Stop i right over here
QuickSort :Partitioning strategy
Step 3
2 (0) 1 (1) 4 (2) 5 (3) 0 (4) 3 (5) 9 (6) 8 (7) 7 (8) 6 (9)
i i i j i pivot
A[i] = 5 < pivot
Move Right
A[i] = 0 < pivot
Move Right
A[i] = 3 < pivot
Move Right
A[i] = 9 > pivot
Stop i right over here
QuickSort :Partitioning strategy
Step 3
2 (0) 1 (1) 4 (2) 5 (3) 0 (4) 3 (5) 9 (6) 8 (7) 7 (8) 6 (9)
j j i pivot
A[i] = 5 < pivot A[j] = 9 > pivot
Move Right Move Left
A[i] = 0 < pivot A[j] = 3 < pivot
Move Right Stop j right over here
A[i] = 3 < pivot i and j have crossed
Move Right So no swap for A[i] and A[j]
A[i] = 9 > pivot Instead Swap A[i] and A[pivot]
Stop i right over here
QuickSort :Partitioning strategy
Step 3
2 (0) 1 (1) 4 (2) 5 (3) 0 (4) 3 (5) 6 (6) 8 (7) 7 (8) 9 (9)
j i
pivot
A[i] = 5 < pivot A[j] = 9 > pivot
Move Right Move Left
A[i] = 0 < pivot A[j] = 3 < pivot
Move Right Stop j right over here
A[i] = 3 < pivot i and j have crossed
Move Right So no swap for A[i] and A[j]
A[i] = 9 > pivot Instead Swap A[i] and A[pivot]
Stop i right over here
QuickSort : Recursive calls
2 (0) 1 (1) 4 (2) 5 (3) 0 (4) 3 (5) 6 (6) 8 (7) 7 (8) 9 (9)
pivot
2 (0) 1 (1) 4 (2) 5 (3) 0 (4) 3 (5) 6 (6) 8 (7) 7 (8) 9 (9)
i
0 i -1 i+1 N -1
QuickSort : Left Recursive call
2 (0) 1 (1) 4 (2) 5 (3) 0 (4) 3 (5)
Always select pivot in one manner.
If you select pivot as
first/middle/Last element always
select that element as pivot in
recursive calls
Better approach. Select pivot as
Array[(L+R)/2] as pivot
QuickSort : Left Recursive call
An example to select last element as
pivot
2 (0) 1 (1) 4 (2) 5 (3) 0 (4) 3 (5)
i j pivot
QuickSort : Left Recursive call
Movements
2 (0) 1 (1) 4 (2) 5 (3) 0 (4) 3 (5)
i j pivot
QuickSort : Left Recursive call
Swap
2 (0) 1 (1) 4 (2) 5 (3) 0 (4) 3 (5)
i j pivot
QuickSort : Left Recursive call
Step 1: Swap
2 (0) 1 (1) 0 (2) 5 (3) 4(4) 3 (5)
i j pivot
QuickSort : Left Recursive call
Movements
2 (0) 1 (1) 0 (2) 5 (3) 4(4) 3 (5)
i j pivot
i & j crossed
QuickSort : Left Recursive call
Swap with the pivot
2 (0) 1 (1) 0 (2) 5 (3) 4(4) 3 (5)
i pivot
QuickSort : Left Recursive call
Swap with the pivot
2 (0) 1 (1) 0 (2) 3 (3) 4(4) 5 (5)
i
pivot
QuickSort :Recursive Calls
2 (0) 1 (1) 0 (2) 3 (3) 4(4) 5 (5)
i
pivot
pivot
2 (0) 1 (1) 0 (2) 3 (3) 4(4) 5 (5)
i
0 i -1 i+1 Right
QuickSort
void quick_sort( input_type a[ ], unsigned int n )
{
q_sort( a, 0, n-1 );
}
QuickSort: Core Function
void q_sort( input_type a[], int left, int right )
{
int i, j; int pivot;
if( left + CUTOFF <= right )
{
pivot = median3( a, left, right );
i = left; j = right - 1;
for ( ; ; )
{
while( a[++i] < pivot );
while( a[--j] > pivot );
if( i < j )
swap( &a[i], &a[j] );
else
break;
} //end for loop
swap( &a[i], &a[right-1] ); /*restore pivot*/
q_sort( a, left, i -1 ); // left recursive call
q_sort( a, i +1, right ); // lright recursive call
}
}
QuickSort: Medians
/* Return median of left, center, and right. */
/* Order these and hide pivot */
int median3( input_type a[], int left, int right )
{
int center;
center = (left + right) / 2;
if ( a[left] > a[center] )
swap( &a[left], &a[center] );
if ( a[left] > a[right] )
swap( &a[left], &a[right] );
if ( a[center] > a[right] )
swap( &a[center], &a[right] );
/* a[left] <= a[center] <= a[right] */
swap( &a[center], &a[right-1] );
return a[right-1]; /* return pivot */
}
QuickSort: Medians
/* Return median of left, center, and right. */
/* Order these(2)and hide pivot */ (5)
8 (0) 1 (1) 4 9 (3) 6 (4)
(4) 3 5 (6) 2 (7) 7 (8) 0 (9)
int median3( input_type a[], int left, int right )
{
int
leftcenter; center right
center = (left + right) / 2;
if ( a[left] > a[center] ) 8>6
swap( &a[left], &a[center] );
if ( a[left] > a[right] ) 6>0
swap( &a[left], &a[right] );
if ( a[center] > a[right] ) 8>6
swap( &a[center], &a[right] );
/* a[left] <= a[center] <= a[right] */
swap( &a[center], &a[right-1] );
return a[right-1]; /* return pivot */
}
QuickSort: Core Function
void q_sort( input_type a[], int left, int right )
8 {(0)
0 1 (1) 4 (2) 9 (3) 6 (4)
7 (4) 3 (5) 5 (6) 2 (7) 6 (8) 0
8 (9)
int i, j; int pivot;
if( left + CUTOFF <= right ) j = right -1
i = {left center
pivot = median3( a, left, right ); pivot
i=left; j=right-1;
for ( ; ; ) /* while i is to the left of j,
{ move i right, skipping over elements
while ( a[++i] < pivot ); smaller than the pivot
while ( a[--j] > pivot ); move j left, skipping over elements
if ( i < j ) larger than the pivot. */
swap( &a[i], &a[j] ); /* If i is to the left of j,
else those elements are swapped */
break;
} //end for loop
swap( &a[i], &a[right-1] );
q_sort( a, left, i-1 );
q_sort( a, i+1, right );
}
}
QuickSort: Core Function
void q_sort( input_type a[], int left, int right )
8 {(0)
0 1 (1) 4 (2) 2 (3) 5 (4) 3 (5) 7 (6)
(4) 9 (7) 6 (8) 0
8 (9)
int i, j; int pivot;
if( left + CUTOFF <= right ) right -1 right
left{ j i
pivot = median3( a, left, right ); pivot
i=left; j=right-1;
for ( ; ; )
{
while ( a[++i] < pivot );
while ( a[--j] > pivot );
if ( i < j )
swap( &a[i], &a[j] );
else /* loop terminated when ( i > j ) i.e., i and j
break; have crossed so no swap is performed */
} //end for loop
swap( &a[i], &a[right-1] ); /*restore pivot*/
q_sort( a, left, i-1 ); // left recursive call
q_sort( a, i+1, right ); // lright recursive call
}
}
QuickSort Analysis
2 cases of Quick sort
Best/average case
where the partition of array is in middle like merge sort
Worst case (Imaginary)
Array is partition into two parts ( 1 items & n-1 items) in
division
For best/Average case mathematical function?
𝑛
𝑇 𝑛 =2𝑇 2 + 𝑐𝑛
For worst case mathematical function?
𝑇 𝑛 = 𝑇 𝑛 − 1 + 𝑇(0) + 𝑐𝑛
QuickSort Analysis
For best/Average case mathematical function
𝑛
𝑇 𝑛 =2𝑇 2
+ 𝑐𝑛
This is exactly same as merge sort algorithm
Try to solve is again by al of the three method
discuss last week
Complexity?
QuickSort Analysis Worst case
For worst case mathematical equation will be
𝑇 𝑛 = 𝑇 𝑛 − 1 + 𝑇(0) + 𝑐𝑛
By iterative method
𝑇 𝑛 = 𝑇 𝑛 − 1 + 𝑐𝑛
𝑇 𝑛 − 1 = 𝑇 𝑛 − 2 + (𝑛 − 1)
𝑇 𝑛 − 2 = 𝑇 𝑛 − 3 + (𝑛 − 2)
𝑇 𝑛−3 =𝑇 𝑛−4 + 𝑛−3
.
.
.
.
QuickSort Analysis Worst case
𝑇 𝑛 = 𝑇 𝑛 − 1 + 𝑐𝑛
𝑇 𝑛 = [𝑇 𝑛 − 1 ] + 𝑛
𝑇 𝑛 = [𝑇 𝑛 − 2 + (𝑛 − 1)] + 𝑛
𝑇 𝑛 = 𝑇 𝑛 − 2 + [(𝑛 − 1) + 𝑛 ]
𝑇 𝑛 = [𝑇(𝑛 − 3) + (𝑛 − 2)] + [(𝑛 − 1) + 𝑛 ]
𝑇 𝑛 = 𝑇 𝑛 − 3 + [(𝑛 − 2) + (𝑛 − 1) + 𝑛 ]
𝑇 𝑛 = 𝑇(𝑛 − 4) + [ 𝑛 − 3 + (𝑛 − 2) + (𝑛 − 1) + 𝑛 ]
𝑇 𝑛 = 𝑇 𝑛 − 𝑘 + [ 𝒏 − 𝒌 + 𝟏 + 𝒏 − 𝒌 + 𝟐 +..
… + 𝒏 − 𝟑 + (𝒏 − 𝟐) + (𝒏 − 𝟏) + 𝒏 ]
Put k = n
this will make series 1+2+3 … + n
