Quck Sort

Introduction:

Quick Sort is based on the concept of Divide and Conquer algorithm, which is also the concept used in Merge Sort. The difference is that in quick sort the most important or significant work is done while dividing the array into subarrays. For quick sort, the combining step is insignificant.

The quicksort algorithm has a worst-case running time of O(n²) on an input array of n numbers, and worst case happens when the array is sorted in descending order. Despite a worst-case running time, quicksort is often the best practical choice for sorting. Its average expected running time is O(n log n), and it has an advantage of sorting in place.

Quick Sort is also called partition-exchange sort. This algorithm divides the given array of numbers into three main parts:

i. Elements less than the pivot element

ii. Pivot element

iii. Elements greater than the pivot element

Pivot element can be chosen from the given numbers in many different ways:

i. Choosing the first element

ii. Choosing the last element

iii. Choosing any random element

iv. Choosing the median

How does it work?

1. A pivot element is chosen from the array. You can choose any element from the array as the pivot element.
   Here, we have taken the rightmost (i.e., the last element) of the array as the pivot element.

Select a pivot element.

2. The elements smaller than the pivot element are put on the left and the elements greater than the pivot element are put on the right.

Put all the smaller elements on the left and greater on the right of pivot element

The above arrangement is achieved by the following steps.

a. A pointer is fixed at the pivot element. The pivot element is compared with the elements beginning from the first index. If the element greater than the pivot element is reached, a second pointer is set for that element.

b. Now, the pivot element is compared with the other elements (a third pointer). If an element smaller than the pivot element is reached, the smaller element is swapped with the greater element found earlier.

Comparison of pivot element with other elements.

c. The process goes on until the second last element is reached.
Finally, the pivot element is swapped with the second pointer.

Swap pivot element with the second pointer.

d. Now the left and right subparts of this pivot element are taken for further processing in the steps below.

1. Pivot elements are again chosen for the left and the right sub-parts separately. Within these sub-parts, the pivot elements are placed at their right position. Then, step 2 is repeated.

Select pivot element of in each half and put at correct place using recursion.

1. The sub-parts are again divided into smaller sub-parts until each subpart is formed of a single element.
2. At this point, the array is already sorted.

Quicksort algorithm implementation-C Program:

Output:

Complexities:

Best Case Time Complexity: Ω(n*log n)

Average Time Complexity: Θ(n*log n)

Worst Case Time Complexity: O(n2)

If partitioning leads to nearly equal subarrays, then the running time is the best, with time complexity as O(n*log n). Worst case happens for arrays with cases where the elements are already sorted, and pivot is chosen as the last element. Here the partitioning gives unbalanced subarrays, where all elements are already smaller than the pivot and hence on its left side, and no elements on the right side.

Space Complexity (considering recursion stack): O(n*log n)

Conclusion:

Quicksort is a comparison-based algorithm, and it is not stable. A small optimization that can be done, is to call the recursive QuickSort() function for the smaller subarray first and then the larger subarray.

Overall, Quick Sort is a highly efficient sorting technique that can give better performance than Merge Sort in the case of smaller arrays.