Quicksort একটি divide-and-conquer সর্টিং অ্যালগরিদম যা একটি pivot বেছে নেয়, এলিমেন্টগুলিকে এটির চেয়ে ছোট এবং বড় তাদের মধ্যে বিভক্ত করে, তারপর প্রতিটি পক্ষকে পুনরাবৃত্তিমূলকভাবে সর্ট করে। গড় O(n log n), সবচেয়ে খারাপ ক্ষেত্র O(n²)।
পার্টিশনিং pivot কে এর চূড়ান্ত সর্টেড অবস্থানে স্থাপন করে; বাম দিকে সবকিছু ছোট, ডান দিকে সবকিছু বড়। উভয় পক্ষে পুনরাবৃত্তি করুন।
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]
(ইন-প্লেস পার্টিশনিং মেমরি সাশ্রয়ের জন্য অনুশীলনে ব্যবহৃত হয়।)
| ক্ষেত্র | সময় | কারণ |
|---|---|---|
| সেরা/গড় | O(n log n) | ভারসাম্যপূর্ণ পার্টিশন |
| সবচেয়ে খারাপ | O(n²) | ইতিমধ্যে সর্টেড খারাপ pivot সহ |
ইন-প্লেস quicksort O(log n) স্ট্যাক স্থান ব্যবহার করে।
ক্যাশ বান্ধবতা এবং কম ওভারহেডের কারণে সাধারণত অনুশীলনে দ্রুততম, এবং এটি ইন-প্লেস। O(n²) সবচেয়ে খারাপ ক্ষেত্রটি একটি র্যান্ডমাইজড বা median-of-three pivot দিয়ে এড়ানো হয়। এটি স্থিতিশীল নয়।
Quicksort অনেক মানক লাইব্রেরিতে ডিফল্ট কারণ এর চমৎকার গড় ক্ষেত্রের গতি এবং কম মেমরি ব্যবহার।
পিভট পছন্দ কেন O(n²) সবচেয়ে খারাপ ক্ষেত্র সৃষ্টি করে তা বোঝা একটি মূল শিক্ষা প্রদান করে: গড় এবং সবচেয়ে খারাপ ক্ষেত্র তীব্রভাবে বিচ্ছিন্ন হতে পারে।
ইট ইন্টারভিউ প্রশ্নে প্রিয় বিষয় ঠিক এই সূক্ষ্মতার কারণে।