কুইক সর্ট বিশ্লেষণ

কীভাবে কুইক-সর্টে, সবচেয়ে খারাপ ক্ষেত্রে ও সবচেয়ে ভালো ক্ষেত্রের সময় ভিন্ন হয়? চল, সবচেয়ে খারাপ ক্ষেত্রে কি হয় পর্যবেক্ষন করি। ধরি, আমাদের সময় খারাপ এবং ভাগগুলো অসম। বিশেষ করে, ধরি ভাগগুলোযে পিভট দিয়ে নির্বাচন করা হয়েছে তা সবসময় $n$‍ উপাদানের সাবঅ্যারেতে সবচেয়ে ছোট বা বড় হবে। তাহলে এক পাশে কোনো উপাদান থাকবে না এবং অপর পাশে $n-1,$‍ সংখ্যক উপাদান থাকবে— শুধুমাত্র পিভট ছাড়া। তাহলে আমাদের সাবঅ্যারের সাইজ হবে 0 এবং $n-1$‍।

মার্জ-সর্টে, $n$‍-উপাদানের সাবঅ্যারেতে কলের জন্য সময়কাল $\mathrm{\Theta }(n)$‍। মার্জ-সর্টে,এই সময়টুকু সংযুক্তকরনের জন্য কিন্তু কুইক-সর্টে এটা হলো বিভক্তিকরনের সময়।

যখন কুইকসর্ট সবসময়ের জন্য অসম বিভক্তি দেয়, তখন বাস্তব কল $cn$‍ সময় এবং ধ্রুবক $c$‍, পরবর্তী কল $n-1$‍ এবং সময় $c(n-1)$‍, পরবর্তী কল $n-2$‍ এর জন্য সময় $c(n-2)$‍ এবং পরবর্তী কল গুলো একই নিয়ম মেনে চলবে। একটি সাবপ্রবলেম সেট তার সময়ের বিভাজনের উপর নির্ভর করে।

প্রত্যেক স্তরের বিভাগের সময়গুলো একসাথে যোগ করে, আমরা পাই

The last line is because $1+2+3+\cdots +n$‍ is the arithmetic series, as we saw when we analyzed selection sort. (We subtract 1 because for quicksort, the summation starts at 2, not 1.) We have some low-order terms and constant coefficients, but when we use big-Θ notation, we ignore them. In big-Θ notation, quicksort's worst-case running time is $\mathrm{\Theta }(n^2)$‍.

কুইকসর্ট সবচেয়ে ভালো কাজ করে যখন বিভাজনগুলো যথাসম্ভব সমান হয়: তাদের আকার হয় সমান বা 1 এর মত পার্থক্য থাকে। সমান হয় যখন সাবঅ্যারেতে বিজোড় সংখ্যক উপাদান থাকে এবং বিভাজনের পর পিভট এর অবস্থান মাঝখানে হয় এবং প্রত্যেক ভাগে $(n-1)/2$‍ সংখ্যক উপাদান থাকে। অন্য ক্ষেত্রে, যখন সাবঅ্যারেতে জোড় সংখ্যক $n$‍ উপাদান থাকে এবং এক ভাগের উপাদান $n/2$‍, অপর ভাগের উপাদান হয় $n/2-1$‍। এই যেকোনো ক্ষেত্রে, প্রত্যেক ভাগে সর্বোচ্চ $n/2$‍ সংখ্যক উপাদান থাকবে এবং সাবপ্রবলেম এর ট্রি সাইজ হবে অনেকটা মার্জসর্টের সাবপ্রবলেমের মত, আর বিভাজনের সময় হবে মার্জের সময়ের সমান।

Using big-Θ notation, we get the same result as for merge sort: $\mathrm{\Theta }(n{\log }_{2}n)$‍.

Showing that the average-case running time is also $\mathrm{\Theta }(n{\log }_{2}n)$‍ takes some pretty involved mathematics, and so we won't go there. But we can gain some intuition by looking at a couple of other cases to understand why it might be $O(n{\log }_{2}n)$‍. (Once we have $O(n{\log }_{2}n)$‍, the $\mathrm{\Theta }(n{\log }_{2}n)$‍ bound follows because the average-case running time cannot be better than the best-case running time.) First, let's imagine that we don't always get evenly balanced partitions, but that we always get at worst a 3-to-1 split. That is, imagine that each time we partition, one side gets $3n/4$‍ elements and the other side gets $n/4$‍. (To keep the math clean, let's not worry about the pivot.) Then the tree of subproblem sizes and partitioning times would look like this:

The left child of each node represents a subproblem size 1/4 as large, and the right child represents a subproblem size 3/4 as large. Since the smaller subproblems are on the left, by following a path of left children, we get from the root down to a subproblem size of 1 faster than along any other path. As the figure shows, after ${\log }_{4}n$‍ levels, we get down to a subproblem size of 1. Why ${\log }_{4}n$‍ levels? It might be easiest to think in terms of starting with a subproblem size of 1 and multiplying it by 4 until we reach $n$‍. In other words, we're asking for what value of $x$‍ is $4^x=n$‍? The answer is ${\log }_{4}n$‍. How about going down a path of right children? The figure shows that it takes ${\log }_{4/3}n$‍ levels to get down to a subproblem of size 1. Why ${\log }_{4/3}n$‍ levels? Since each right child is 3/4 of the size of the node above it (its parent node), each parent is 4/3 times the size of its right child. Let's again think of starting with a subproblem of size 1 and multiplying the size by 4/3 until we reach $n$‍. For what value of $x$‍ is $(4/3{)}^x=n$‍? The answer is ${\log }_{4/3}n$‍.

প্রত্যেক প্রথম ${\log }_{4}n$‍ ধাপে, $n$‍ নোড বিদ্যমান(আবার, অনেক পিভট আছে যা বিভক্ত হয় না) এবং বিভক্ত করনের মোট সময় প্রত্যেক ধাপের জন্য $cn$‍। কিন্তু বাকি ধাপ গুলোর কি হবে? প্রত্যেকের কাছে n নোডের কম আছে এবং বিভাজনের সময় প্রত্যেক ধাপের জন্য সর্বোচ্চ $cn$‍। সবমিলিয়ে, ${\log }_{4/3}$‍ ধাপ সমূহ বিদ্যমান এবং বিভাজনের মোট সময় $O(n{\log }_{4/3}n)$‍। এখন, এখানে একটি গাণিতিক তথ্য আছে

সকল ধনাত্মক সংখার জন্য $a$‍, $b$‍ এবং $n$‍। ধরি $a=4/3$‍ এবং $b=2$‍, তাহলে, আমরা পাই

and so ${\log }_{4/3}n$‍ and ${\log }_{2}n$‍ differ by only a factor of ${\log }_2(4/3)$‍, which is a constant. Since constant factors don't matter when we use big-O notation, we can say that if all the splits are 3-to-1, then quicksort's running time is $O(n{\log }_{2}n)$‍, albeit with a larger hidden constant factor than the best-case running time.

কত বার আমরা 3-থেকে-1 বা ভালো বিভাজন দেখতে আশা করতে পারি? এটা নির্ভর করে কীভাবে আমরা পিভট নির্বাচন করছি তার উপরে। ধরি বিভক্তিকরণের পর পিভট $n$‍ উপাদানের সাবঅ্যারেতে কোন একটি স্থানে থাকবে। তারপর 3-থেকে-1 বা ভালো বিভাজন পেতে পিভটকে অবশ্যই "মাঝের অর্ধেক" এর আশেপাশে থাকতে হবে:

তাহলে, বিভক্তিকরণের পর পিভট যদি সাবঅ্যারের কোথাও থাকে, 3-থেকে-1 বিভাজন পাওয়ার সম্ভাবনা 50% হবে। অন্যভাবে বললে, আমরা অর্ধেক সময় 3-থেকে-1 বিভাজন বা এর চেয়ে ভাল আশা করতে পারি।

The other case we'll look at to understand why quicksort's average-case running time is $O(n{\log }_{2}n)$‍ is what would happen if the half of the time that we don't get a 3-to-1 split, we got the worst-case split. Let's suppose that the 3-to-1 and worst-case splits alternate, and think of a node in the tree with $k$‍ elements in its subarray. Then we'd see a part of the tree that looks like this:

[[☃ image 1]-এর পরিবর্তে এভাবে:

Therefore, even if we got the worst-case split half the time and a split that's 3-to-1 or better half the time, the running time would be about twice the running time of getting a 3-to-1 split every time. Again, that's just a constant factor, and it gets absorbed into the big-O notation, and so in this case, where we alternate between worst-case and 3-to-1 splits, the running time is $O(n{\log }_{2}n)$‍.

Bear in mind that this analysis is not mathematically rigorous, but it gives you an intuitive idea of why the average-case running time might be $O(n{\log }_{2}n)$‍.

মনে কর তোমার সবচেয়ে খারাপ শত্রু তোমাকে একটি অ্যারে সাজাতে বলেছে কুইকসর্ট দিয়ে এবং সে এটা জানে যে তুমি পিভট হিসেবে সব সময় প্রতিটি সাবঅ্যারের একেবারে ডানদিকের উপাদান নির্বাচন কর, আর অ্যারেটিকে এমনভাবে সাজিয়েছে যাতে তুমি সব সময় সবচেয়ে বাজে বিভাজন পাও। কীভাবে তুমি তোমার শত্রুকে পরাস্ত করতে পারবে?

You could not necessarily choose the rightmost element in each subarray as the pivot. Instead, you could randomly choose an element in the subarray, and use that element as the pivot. But wait—the partition function assumes that the pivot is in the rightmost position of the subarray. No problem—just swap the element that you chose as the pivot with the rightmost element, and then partition as before. Unless your enemy knows how you choose random locations in the subarray, you win!

In fact, with a little more effort, you can improve your chance of getting a split that's at worst 3-to-1. Randomly choose not one, but three elements from the subarray, and take median of the three as the pivot (swapping it with the rightmost element). By the median, we mean the element of the three whose value is in the middle. We won't show why, but if you choose the median of three randomly chosen elements as the pivot, you have a 68.75% chance (11/16) of getting a 3-to-1 split or better. You can go even further. If you choose five elements at random and take the median as the pivot, your chance of at worst a 3-to-1 split improves to about 79.3% (203/256). If you take the median of seven randomly chosen elements, it goes up to about 85.9% (1759/2048). Median of nine? About 90.2% (59123/65536). Median of 11? About 93.1% (488293/524288). You get the picture. Of course, it doesn't necessarily pay to choose a large number of elements at random and take their median, for the time spent doing so could counteract the benefit of getting good splits almost all the time.

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।