### Quick Sort

Quick Sort is partial application of divide and conquer algorithm design technique. It is partial application because there is no step for combining.

## Quick Sort

- It is an in-place sorting technique. This means sorting of the array takes place within the same array.
- It is an unstable sorting algorithm as the relative ordering of same elements changes during sorting.
- Quick Sort uses partition algorithm.Array is sorted recursively.

### Partition Algorithm

**Algorithm:**

This algorithm takes array of ‘n’ elements as input along with starting and ending index.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
partition(A,i,j) { x=A[i]; //setting pivot point as first element in array l=i; // left iterator initialized to starting index. for(int r=i+1;r<=j;r++) //iterate for i+1 to ending index { if(A[r]<=x) // check is element at 'r' index is less than equal to element at pivot { l=l+1; // if condition validates increment left iterator swap(A[r],A[l]); // swapping elements } } swap(A[i],A[l]); return l; //return position of left iterator i-e partition point } |

**Time complexity:**

Time complexity of partition algorithm depends on number of swaps and comparisons made.

In **best case** number of swaps = 1 where the array is in ascending order and number of comparisons = n-1. Therefore, **TC=n-1 + 1 =O(n)**.

In **worst case** number of swaps = n-1 where the array is in decreasing order and number of comparisons = n-1. Therefore, **TC=n-1 + n-1 =O(n)**.

### Quick Sort algorithm:

**Algorithm: **

1 2 3 4 5 6 7 8 9 10 11 |
quciksort(A,i,j) { if(i==j) // only 1 element in array return A[i]; -----> O(1) else { x=partition(A,i,j); ---->O(n) quicksort(A,i,x-1) ----> T(x-i) //conquer quicksort(A,x+1,j) ----> T(j-x) //conquer return A; --->O(1) } |

**Time complexity:**

Let T(n) be the time complexity of quick sort algorithm for array of ‘n’ elements then,

**T(n) = T(x-i)+T(j-x)+n **

In best case, partition algorithm divides the array into exactly two parts.

1 2 3 4 5 |
T(n)=T(n/2)+T(n/2-1)+n =2T(n/2)+n solving recurrence relation T(n)= n + nlogn =O(nlogn) |

In worst case, partition algorithm divides the array into two parts of size 1 and n-1.

1 2 3 4 5 6 7 8 |
T(n)=T(n-1)+n =T(n-2)+n-1+n | | n-1 times | =T(1)+2+3......+n-2+n-1+n =n(n+1)/2 =O(n^2) |