Geek Answers Handbook

Quicksort - How do rotation strategies affect Big-oh's overall quick-sort behavior?

I came up with several strategies, but I'm not quite sure how they affect overall behavior. I know the middle case is O (NlogN), so I would suggest that it would be somewhere in the answer. I want to just put NlogN + 1 if I just select the 1st element in the array as a hinge for sorting, but I don’t know if it is either correct and not acceptable? If someone could enlighten me on this, that would be great. Thank!

Possible strategies:

a) Array random: select the first element, as this is the most economical option.

b) The array is basically sorted: select the middle element so that we are most likely to compliment the binary split recursion in half each time.

c) The array is relatively large: select the first, middle, and last indices in the array and compare them, choosing the smallest number, to avoid the worst case.

d) Run 'c' with randomly generated indices to make the choice less deterministic.

+5
source share
3 answers

An important fact that you should know is that in an array of individual elements in O (n lg n), quicksort will work with a random selection of a partition. There is a lot of good evidence of this, and the one on Wikipedia, . , , . , , , "" , 75%/25% - ; , , 25% 75% . , , . , k , . (3/4) k n, . , k = log 3/4 (1/n) = log 4/3 n, k 1, . , O (lg n) , . , ? , , 50%, 50% , , , . O (n), O (n) , . O (lg n) , O (n lg n) .

, 75%/25% - , (100 - k%)/k% split - -. , quicksort , , O (n lg n).

, , , , . , , O (n lg n). , , , , , O (n lg n) .

, . (), , , , , , ( .. ) , (b), , , . , , "" , , , , O (n lg n ) , . ( " " , , , ).

(c) (d), , (d) O (n lg n) . , , O (n 2). , " Quicksort" McIlroy , . quicksort, DoS- , , , , . , (d) , , .

, , (d), , . , , O (n lg n) . , , , quicksort & Omega; (n lg n), , , , .

, - , quicksort.: -)

+5

, , O (nlog (n)). O (nlog (n)) , .

O (nlog (n)), , "" . . , , .

0

The best core is one that can split an array into exactly two halves. The median of the array is a great choice. I will propose this approach: -
select some random indexes
calculate median of these elements
Use this as pivot element

From the O (n) median search algorithm, I think 5 random indexes should be sufficient.

-1
source

More articles: