Sort the following numbers using Quick sort algorithm. Show all passes of execution also state the following state the time complexity.

65, 70, 75, 80, 60, 55, 50, 45

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.

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