0
34kviews
Apply Quick Sort Algorithm to sort the list E, X, A, M, P, L, E

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.

1 Answer
2
2.5kviews

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 E, X, A, M, P, L, E


  • 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)$

Please log in to add an answer.