# Quick Sort Algorithm for BCA & MCA

## Quick Sort Algorithm for BCA

Based On Partitioning of array of data into smaller arrays.

** Uses The concept of divide & Conquer Approach.
** Finds an elements called “Pivot” ( Point of division of array )

In This form we sort an unsorted array in quick sort alogorithm..

Here Left Half Contains those elements which are smaller than pivot, and Right half contains those elements which are greater than pivot.

# Important Facts About Quick Sort Algorithm :-

( 1 ) Efficient For large size data sets
( 2 ) Average and worst case complexity = O(nlogn)

# Now we see some recursive steps :-

( 1 ) Find pivot that divides the array into two halves.
( 2 ) Quick Sort Left Half.
( 3 ) Quick Sort Right Half

# Simple Example to understand quick Sort easily :-

# Pseudo Code for recursive quick sort Function :-

quicksort ( arr[], low, high )
{
if ( low<high )
{
pi = partition( arr, low, high );
quicksort ( arr, low, pi-1 );
quicksort ( arr, pi+1, high );
}
}

# Partition Algorithm :-

quicksort ( arr[], low, high )
{
if ( low<high )
{
pi = partition( arr, low, high );
quicksort ( arr, low, pi-1 );
quicksort ( arr, pi+1, high );
}
}

# Pseudo Code for Partition() :-

partition ( arr[], low, high )
{
pivot = arr[high];
i=( low-1 );
for ( j=low; j<=(high-1); j++ )
{
if ( arr[j] < pivot )
{
i++;
swap arr[i] and arr[j]
}
}
swap arr[i+1] and arr[high]
return (i+1)
}

# Analysis Of Quick Sort :-

Time Taken by quick sort in general can be written as following :-
T( n ) = T( k ) + T ( n-k-1 ) + n

The first two terms for recursive calls, the last term is for the partition process . k is the number of elements which are smaller than pivot. The time taken by quick sort depends upon the input array and partition strategy. Following are three cases :-

( 1 ) Worst case :- worst case occurs when the partition process picks greatest or smallest element as pivot.
Following is the recurrence for worst case :-
T ( n ) = T ( 0 ) + T ( n-1 ) + n
Which is equivalent to
T ( n ) = T ( n-1 ) + n

The Solution of above recurrence is O ( n2 )

( 2 ) Best Case :- it occurs when the partition process picks the middle element as pivot element. Following is the recurrence for best case :-
T ( n ) = 2*T( n/2 ) + n
The solution of the above recurrence is O ( nlogn )

( 3 ) Average Case :- Recurrence for average case👇👇
T ( n ) = T ( n/9 ) + T ( 9n/10 ) + n
Solution of above recurrence is O ( nlogn )

Although the worst case complexity for quick sort is O ( n2 ) which is more than heap sort or merge sort. Quick Sort is faster in practice, because the inner loop can be efficiently implemented on most.

# Quick Sort Worst Case time complexity derivation :-

T ( n ) = T ( n-1 ) + n – (1)
Put ( n-1 ) in the place of n :-
T ( n-1 ) = T ( n-2 ) + n-1 – ( 2 )
Put the value of T ( n-1 ) in equation (1) :-
T ( n ) = T ( n-2 ) + ( n-1 ) + n – ( 3 )
Put ( n-2 ) in the place of n in equation ( 1 ) :-
T ( n-2 ) = T ( n-3 ) + (n-2)
Put The Value of T ( n-2 ) in equation ( 2 ) :-
T ( n-1 ) = T ( n-3 ) + ( n-2 ) + ( n-1 )
Put the value Of T ( n-1 ) in equation ( 1 ) :-
T ( n ) = T ( n-3 ) + ( n-2 ) + ( n-1 ) + n
||
||
||
||
T ( n ) = T ( 1 ) + 2 + 3 + 4 + ——– + n
As we know T ( 1 ) = 1
T ( n ) = 1 + 2 + 3 + ——- + n
T ( n ) = (n*( n+1 ))/2
T ( n ) = ( n2 + n )/2
Here Dominating Term is n2, So Complexity will be O ( n2 )

# Quick Sort best case time complexity derivation :-

T ( n ) = 2*T ( n/2 ) + n — ( 1 )
put n/2 in place of n :-
T ( n/2 ) = 2 * T ( n/4 ) + n/2 — ( 2 )
Put value of T ( n/2 ) in equation ( 1 ) :-
T ( n ) = 2 * ( 2*T( n/4 ) +n/2 ) + n
T ( n ) = 22 * T ( n/4 ) + n + n — ( 3 )
Put n/4 in equation ( 1 ) :-
T ( n/4 ) = 2*T ( n/8 ) +n/4
Put Value Of T ( n/4 ) in equation ( 3 ) :-
T ( n ) = 22 * ( 2* T ( n/8 ) + n/4 ) + n + n
T ( n ) = 23 * T ( n/8 ) + n + n + n
||
||
||
||
T ( n ) = 2i * T ( n/2i ) + n*i
As We Know T ( 1 ) = 1 So let’s we take n/2i = 1
We take log both sides :-
logn = log2i
logn = i*log2 — As we Know log2=1
logn = i
i = logn
T ( n ) = n * T ( 1 ) + nlogn
T ( n ) = n + nlogn
So Here Complexity Will be O ( nlogn )