মূল বিষয়বস্তু
কম্পিউটার বিজ্ঞান
কুইক সর্ট সম্পর্কে আলোচনা
মার্জসর্টের মত কুইকসর্টও বিভক্তি এবং জয়(ডিভাইড অ্যান্ড কনকার) ব্যবহার করে, আর তাই এটাও রিকার্সিভ অ্যালগোরিদম। কুইকসর্ট যেভাবে বিভক্তি এবং জয় ব্যবহার করে সেটা মার্জসর্ট যেভাবে করে তার থেকে আলাদা। মার্জসর্টে, বিভক্তিকরণ(ডিভাইড) ধাপে তেমন কিছুই হয় না এবং আসল সব কাজ হয় একত্রকরণ(কমবাইন) ধাপে। কুইকসর্ট হল এর বিপরীত: আসল সব কাজ হয়ে থাকে বিভক্তিকরণ ধাপে। প্রকৃতপক্ষে, কুইকসর্টে একত্রকরণ ধাপে একেবারেই কিছু হয় না।
Quicksort has a couple of other differences from merge sort. Quicksort works in place. And its worst-case running time is as bad as selection sort's and insertion sort's: . But its average-case running time is as good as merge sort's: . So why think about quicksort when merge sort is at least as good? That's because the constant factor hidden in the big-Θ notation for quicksort is quite good. In practice, quicksort outperforms merge sort, and it significantly outperforms selection sort and insertion sort.
এখানে দেখব কীভাবে কুইকসর্ট বিভক্তি এবং জয় ব্যবহার করে। মার্জসর্টে, ধরি এই সাবঅ্যারেটি সাজাবো
array[p..r]
, যেখানে প্রাথমিকভাবে সাবঅ্যারেটি হচ্ছে array[0..n-1]
।- Divide by choosing any element in the subarray
array[p..r]
. Call this element the pivot. Rearrange the elements inarray[p..r]
so that all elements inarray[p..r]
that are less than or equal to the pivot are to its left and all elements that are greater than the pivot are to its right. We call this procedure partitioning. At this point, it doesn't matter what order the elements to the left of the pivot are in relation to each other, and the same holds for the elements to the right of the pivot. We just care that each element is somewhere on the correct side of the pivot.As a matter of practice, we'll always choose the rightmost element in the subarray,array[r]
, as the pivot. So, for example, if the subarray consists of [9, 7, 5, 11, 12, 2, 14, 3, 10, 6], then we choose 6 as the pivot. After partitioning, the subarray might look like [5, 2, 3, 6, 12, 7, 14, 9, 10, 11]. Letq
be the index of where the pivot ends up. - Conquer by recursively sorting the subarrays
array[p..q-1]
(all elements to the left of the pivot, which must be less than or equal to the pivot) andarray[q+1..r]
(all elements to the right of the pivot, which must be greater than the pivot). - Combine by doing nothing. Once the conquer step recursively sorts, we are done. Why? All elements to the left of the pivot, in
array[p..q-1]
, are less than or equal to the pivot and are sorted, and all elements to the right of the pivot, inarray[q+1..r]
, are greater than the pivot and are sorted. The elements inarray[p..r]
can't help but be sorted!Think about our example. After recursively sorting the subarrays to the left and right of the pivot, the subarray to the left of the pivot is [2, 3, 5], and the subarray to the right of the pivot is [7, 9, 10, 11, 12, 14]. So the subarray has [2, 3, 5], followed by 6, followed by [7, 9, 10, 11, 12, 14]. The subarray is sorted.
বেস কেস হল দুইয়ের চেয়ে কম উপাদানের সাবঅ্যারে, যেমনটা হয় মার্জসর্টে। মার্জসর্টে, তুমি কখনোই উপাদানবিহীন সাবঅ্যারে পাবে না, কিন্তু কুইকসর্ট পাবে, যদি সাবঅ্যারের বাকি সব উপাদান পিভটের ছোট হয় বা পিভটের চেয়ে বড় হয়।
Let's go back to the conquer step and walk through the recursive sorting of the subarrays. After the first partition, we have subarrays of [5, 2, 3] and [12, 7, 14, 9, 10, 11], with 6 as the pivot.
সাবঅ্যারে [5, 2, 3] কে সাজাতে, আমরা 3 কে পিভট হিসেবে নিলাম। বিভক্তিকরণের পর আমরা পাই [2, 3, 5]। সাবঅ্যারে [2], পিভটের বামপাশে, হল বেস কেস যখন আমরা পুনরাবৃত্তি করি, আর সাবঅ্যারে [5], হল পিভটের ডানপাশে।
সাবঅ্যারে [12, 7, 14, 9, 10, 11] কে সাজাতে, আমরা পিভট নিলাম 11, আর পেলাম [7, 9, 10] পিভটের বামপাশে এবং [14, 12] ডানপাশে। এই সাবঅ্যারেগুলোকে সাজানোর পর, আমরা পেলাম [7, 9, 10], তারপর 11, তারপর হবে [12, 14]।
এখানে দেখানো হয়েছে কীভাবে পুরো কুইকসর্ট অ্যালগরিদম কাজ করে। নীল রঙের অ্যারে অবস্থানগুলো পূর্ববর্তী ধাপে পিভট হিসেবে নেওয়া হয়েছে, আর তাই এই মানগুলোর অবস্থান পরিবর্তন হবে না:
এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।
আলোচনায় অংশ নিতে চাও?
কোন আলাপচারিতা নেই।