Quick Sort : Step-by-Step
Initial Value in Quick Sort Algorithm
In the Quick Sort Algorithm, the initial values typically refer to the indices that define the current subarray and the pivot element. These guide the recursive partitioning and sorting process.
Key Initial Values in Quick Sort
- Low Index (
low): Starting index of the array or subarray, initially set to0. - High Index (
high): Ending index of the array or subarray, initially set ton - 1. - Pivot Element (
pivot): Typically chosen as the last element in the subarray, though other strategies exist.
Example Initialization
For an array like [7,2,1,8,6,3,5,4], the initial call would be:
quickSort(arr, 0, 7);This leads to:
pivot = 4(last element)- Array is partitioned around the pivot: elements less than pivot to the left, greater to the right
- Recursive calls sort the left and right partitions
Why These Initial Values Matter
- They define the boundaries for recursive partitioning.
- They ensure elements are correctly placed relative to the pivot.
- They help maintain the algorithm’s average time complexity of O(n log n).
References
Explanation will appear here...