Quicksort ਇਕ divide-and-conquer sort ਹੈ ਜੋ ਇਕ pivot ਚੁਣਦਾ ਹੈ, ਤੱਤਾਂ ਨੂੰ ਇਸ ਨਾਲੋਂ ਛੋਟੇ ਅਤੇ ਵੱਡੇ ਵਿਚ ਵੰਡਦਾ ਹੈ, ਫਿਰ ਹਰੇਕ ਪਾਸੇ ਨੂੰ ਵਾਰ-ਵਾਰ sort ਕਰਦਾ ਹੈ। ਔਸਤ O(n log n), worst case O(n²)।
Partitioning pivot ਨੂੰ ਇਸ ਦੀ ਅੰਤਿਮ sorted position ਵਿਚ ਰਖਦਾ ਹੈ; ਸਭ ਕੁਝ ਖੱਬੇ ਪਾਸੇ ਛੋਟਾ ਹੈ, ਸਭ ਕੁਝ ਸੱਜੇ ਪਾਸੇ ਵੱਡਾ ਹੈ। ਦੋਨਾਂ ਪਾਸਿਆਂ ਉੱਤੇ ਵਾਰ-ਵਾਰ।
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # pick a pivot
left = [x for x in arr if x < pivot] # smaller
mid = [x for x in arr if x == pivot] # equal
right = [x for x in arr if x > pivot] # larger
return quicksort(left) + mid + quicksort(right)
quicksort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
(In-place partitioning ਵਿਹਾਰ ਵਿੱਚ ਮੈਮੋਰੀ ਬਚਾਉਣ ਲਈ ਵਰਤੀ ਜਾਂਦੀ ਹੈ।)
| Case | Time | ਕਾਰਨ |
|---|---|---|
| Best/Average | O(n log n) | balanced partitions |
| Worst | O(n²) | already-sorted with bad pivot |
In-place quicksort O(log n) stack space ਵਰਤਦਾ ਹੈ।
ਆਮ ਤੌਰ ਉੱਤੇ cache friendliness ਅਤੇ ਘੱਟ overhead ਦੀ ਵਜ਼ਾ ਨਾਲ ਵਿਹਾਰ ਵਿਚ ਸਭ ਤੋਂ ਤੇਜ਼, ਅਤੇ ਇਹ in-place ਹੈ। O(n²) worst case ਨੂੰ ਇਕ randomized ਜਾਂ median-of-three pivot ਨਾਲ ਬਚਾਇਆ ਜਾਂਦਾ ਹੈ। ਇਹ stable ਨਹੀਂ ਹੈ।
Quicksort ਬਹੁਤ ਸਾਰੀਆਂ standard libraries ਵਿੱਚ ਪੂਰਵ-ਨਿਰਧਾਰਤ ਹੈ ਕਿਉਂਕਿ ਇਸ ਦੀ ਬੁਰਿਆ ਔਸਤ-case speed ਅਤੇ ਘੱਟ memory use।
ਸਮਝਣਾ ਕਿ pivot choice ਕਿਵੇਂ O(n²) worst case ਬਣਾਉਂਦਾ ਹੈ ਇਕ ਮੁੱਖ ਪਾਠ ਸਿਖਾਉਂਦਾ ਹੈ: average ਅਤੇ worst case ਧਾਰਾ ਨਾਲ ਭਿੰਨ ਹੋ ਸਕਦੇ ਹਨ।
ਇਹ ਬਿਲਕੁਲ ਉਸ nuance ਦੀ ਵਜ਼ਾ ਨਾਲ ਇੱਕ ਮਨਪਸੰਦ interview topic ਹੈ।