Quick Sort Algorithm and Partitioning Methods

Quick Sort computer science ke sabse widely used sorting algorithms me se ek hai. Merge sort ki tarah yeh bhi Divide and Conquer paradigm follow karta hai, lekin iska main computational work partitioning phase me hota hai na ki merging phase me.

Core Concept: Pivot and Partitioning

Quick sort array me se kisi ek element ko Pivot choose karta hai. Fir array ko aise partition kiya jata hai ki:

• Pivot se chhote sabhi elements pivot ke left side chale jayein.
• Pivot se bade sabhi elements pivot ke right side chale jayein.
• Iske baad pivot apni final sorted position par aa jata hai. Fir left aur right subarrays ko recursively sort kiya jata hai.

Array: [ 10, 80, 30, 90, 40, 50, 70 ]  (Pivot = 70)

Partitioning Step:
Elements < 70 move to Left | PIVOT (70) | Elements > 70 move to Right
[ 10, 30, 40, 50 ]         |     70     | [ 90, 80 ]

Recursively call QuickSort on Left and Right subarrays!

Lomuto Partitioning Algorithm

PARTITION_LOMUTO(A, low, high)
1. Set pivot = A[high]
2. Set i = low - 1
3. For j = low to high - 1 do:
4.     If A[j] <= pivot then:
5.         i = i + 1
6.         Swap(A[i], A[j])
7. End For
8. Swap(A[i + 1], A[high])
9. Return i + 1 [Pivot index]

Complexity and Worst-case Analysis

• Best-case Time: O(n log n) jab pivot hamesha array ko two equal halves me divide kare: T(n) = 2T(n/2) + O(n).
• Average-case Time: O(n log n) expected time over random distributions.
• Worst-case Time: O(n^2) tab hota hai jab array already sorted ho aur hum extreme element (first ya last) ko pivot choose karein. Recurrence ban jati hai: T(n) = T(n-1) + O(n) = O(n^2).
• Worst-case Prevention: Randomized QuickSort (random pivot) ya Median-of-Three pivot strategy use karne se worst-case practical scenarios me avoid ho jata hai.
• Space Complexity: O(log n) call stack space in best/average case; O(n) in worst case. Quick sort In-place sorting algorithm hai.

Agli post me hum non-comparison sorting cover karenge: Counting Sort Algorithm (Non-Comparison Sorting).