![]() ![]() ![]() We can additionally improve on the quick sort algorithm with a few other modifications: We've already mentioned above that initially shuffling the array helps protect us from the worst-case comparison cost. However, quick sort is faster than merge sort in practice, because there is less data movement during the sort. That means one has about $39$ percent more comparisons than merge sort. Thus, on average the quick sort results in a number of comparisons that is roughly $\sim 1.39 n \log_2 n$. Since the size of each half is $n/2$, the recurrence relation for the cost function (for comparisons) is closely related to the one governing the merge sort: The cost for recursively sorting two half-size arrays The partitioning cost for $n$ items, which is $\sim n$ comparisons (and a smaller number of exchanges), and Then, the overall cost for sorting $n$ items is given by: The best case for the quick sort occurs when each partition splits the array into two equal halves.
0 Comments
Leave a Reply. |