Design an algorithm for performing quick sorting. Apply the same to solve the following set of numbers: 5 3 1 9 8 2 4 7
Answer:-
Apply the Quick sort to solve the following set of numbers: 5 3 1 9 8 2 4 7
Quick Sort is an efficient, in-place sorting algorithm that follows the divide-and-conquer paradigm.
- Choose a pivot element:
- Select a pivot element from the array. For simplicity, we’ll choose the last element in this case: 7.
- Partition the array:
- Rearrange the elements in the array such that all elements less than the pivot are to its left, and all elements greater than the pivot are to its right.
[5, 3, 1, 2, 4] | [7] | [9, 8]
- Recursively sort subarrays:
- Apply the same process to the subarrays on the left and right of the pivot. Sort left subarray:
[1, 2, 3, 4, 5] | [7] | [9, 8]
Sort right subarray:
[1, 2, 3, 4, 5] | [7] | [8, 9]
- Merge the sorted subarrays:
- The entire array is now sorted. Merge the subarrays:
[1, 2, 3, 4, 5, 7, 8, 9]
The time complexity of the average case for Quick Sort is O(n log n). In the worst-case scenario, Quick Sort has a time complexity of O(n^2), but with proper implementation (choosing a good pivot), this is highly unlikely to occur.