Quicksort ایک divide-and-conquer ترتیب ہے جو pivot منتخب کرتا ہے، عناصر کو اس سے چھوٹے اور بڑے میں تقسیم کرتا ہے، پھر ہر طرف کو recursively ترتیب دیتا ہے۔ اوسطاً O(n log n)، بدترین صورتحال O(n²)۔
Partitioning pivot کو اس کی حتمی ترتیب شدہ پوزیشن میں رکھتا ہے؛ بائیں طرف کی ہر چیز چھوٹی ہے، دائیں طرف کی ہر چیز بڑی ہے۔ دونوں طرف سے recurse کریں۔
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 عملی طور پر میموری بچانے کے لیے استعمال کی جاتی ہے۔)
| صورتحال | وقت | وجہ |
|---|---|---|
| بہترین/اوسط | O(n log n) | متوازن partitions |
| بدترین | O(n²) | پہلے سے ترتیب شدہ برا pivot کے ساتھ |
In-place quicksort O(log n) stack space استعمال کرتا ہے۔
عام طور پر عملی طور پر سب سے تیز ہے cache friendliness اور کم overhead کی وجہ سے، اور یہ in-place ہے۔ O(n²) بدترین صورتحال randomized یا median-of-three pivot کے ساتھ ختم کی جاتی ہے۔ یہ stable نہیں ہے۔
Quicksort بہت سی معیاری لائبریریوں میں ڈیفالٹ ہے اس کی بہترین اوسط صورتحال کی رفتار اور کم میموری کے استعمال کی وجہ سے۔
یہ سمجھنا کہ pivot انتخاب O(n²) بدترین صورتحال کا سبب کیوں بنتا ہے، ایک اہم سبق سکھاتا ہے: اوسط اور بدترین صورتحال تیزی سے الگ ہو سکتی ہیں۔
یہ انٹرویو کے موضوع میں پسندیدہ ہے بالکل اسی nuance کی وجہ سے۔