written 6.7 years ago by | modified 2.5 years ago by |
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
written 6.7 years ago by | modified 2.5 years ago by |
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
written 2.5 years ago by |
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 -
Best Case Time Complexity -
$$O(n^*log\ n)$$
Average Case Complexity -
$$O(n^*log\ n)$$
Worst-Case Complexity -
$$f(n) = n \times (n-1) = O(n^2)$$
Space Complexity of Quick Sort - $O(n^*log\ n)$