Quick Sort

Quick Sort is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. It was invented by C.A.R. Hoare. it is still a very commonly used algorithm for sorting. it is a divide and conquer algorithm.

Algorithm:

The steps are as follows:

1. Pick an element, say P (the pivot).
2. Re-arrange the elements into 3 sub-blocks:
• Less than or equal to P say S1.
• P (the only element in the middle-block).
• Greater than or equal to P say S2.
3. Repeat the process recursively for S1 and S2.

Example:

Choosing Pivot:

1. Always pick first element as pivot.
2. Always pick last element as pivot.
3. Pick a random element as pivot.(Recommended)
4. Pick median as pivot.

Why is Quick Sort preferred for arrays?

Quick Sort in its general form is an in-place sort  whereas merge sort requires O(n) extra storage. Allocating and de-allocating the extra space used for merge sort increases the running time of the algorithm. Comparing average complexity we find that both type of sorts have O(nlogn) average complexity but the constants differ. For arrays, merge sort loses due to the use of extra O(n) storage space.

Implementation:

//Using random element as pivot

int partition(int arr[], int l, int r)

{

srand(time(NULL));

int pivot = rand() % (r - l + 1) + l;

std::swap(arr[l], arr[pivot]);

int j = l + 1;

for(int i = l+1; i <= r; ++i)

{

if(arr[i] < arr[l])

std::swap(arr[j++], arr[i]);

}

std::swap(arr[--j], arr[l]);

return j;

}

void quick_sort(int arr[], int l, int r)

{

if(l < r)

{

int p = partition(arr, l, r);

quick_sort(arr, l, p-1);

quick_sort(arr, p+1, r);

}

}

Complexity: O(nlogn)