Apply Quick Sort Algorithm to sort the list E, X, A, M, P, L, E in alphabetical order. Analyze the best case, worst case and average case complexities of Quick Sort.

Quick Sort

• This algorithm follows the Divide and Conquer approach.
• Divide and conquer is a technique of breaking down the algorithms into subproblems, then solving the subproblems, and combining the results back together to solve the original problem.
• Quick Sort is a Recursive algorithm.
• It divides the given array into two sections using a partitioning element called a pivot.
• The division performed is such that
  • All the elements to the left side of the pivot are smaller than the pivot.
  • All the elements to the right side of the pivot are greater than the pivot.
• Picking a good pivot is necessary for the fast implementation of quicksort.
• Some of the ways of choosing a pivot are as follows:
  • Pivot can be random, i.e. select the random pivot from the given array.
  • Pivot can either be the rightmost element or the leftmost element of the given array.
  • Select median as the pivot element.

Algorithm of Quick Sort -

Step 1 − Choose the high-index Pivot.

Step 2 − Take two variables to point Left and Right of the list excluding Pivot.

Step 3 − Left points to the low index.

Step 4 − Right points to the high index.

Step 5 − If the value at the Left is less than the pivot move in the right direction.

Step 6 − If the value at the Right is greater than the pivot move in the left direction.

Step 7 − If both step 5 and step 6 do not match SWAP Left and Right.

Step 8 − If left ≥ right, the point where they met is a new pivot. Checks the value of old and new Pivots whether there is a need for Swapping or not.

Let's solve the given example using Quick Sort:

• Quick Sort is sensitive to the order of input data.
• It gives the worst performance when elements are already in ascending or descending order.

Best Case Time Complexity -

• In Quicksort, the best case occurs when the pivot element is the middle element or near to the middle element. The best-case time complexity of quicksort is

$$O(n^*log\ n)$$

Average Case Complexity -

• If array elements are not in properly ascending and not properly descending order. The average case time complexity of quicksort is

$$O(n^*log\ n)$$

Worst-Case Complexity -

• In quick sort, the worst case occurs when the pivot element is either the greatest or smallest element.
• It divides the array into sections of 1 and (n-1) elements in each call.
• Then, there are (n-1) divisions in all.
• Therefore, here total comparisons required are

$$f(n) = n \times (n-1) = O(n^2)$$

Space Complexity of Quick Sort - $O(n^*log\ n)$