Quicksort: how to deal with collapse item selection, input and worst case?
From what I understood the posts I read on quicksort
is that the choice of a pivot element has a huge impact on whether it performs the worst performance for a given input or not.
I ask myself
-
the element
randomized
minimizes (but does not eliminate) the ability to run inn^2
-
Which condition should match the value
input
given asdeterministic pivot element
, for example, always selecting the first element as the pivot so that itn^2
becomes reality. -
How will I introduce in such a way that worst-case performance becomes a reality?
Others gave an example of an already sorted array in ascending or descending order as a last resort.
I guess it has something to do with splitting procedure
, pointers to element < pivot
(and vice versa) and how an unfavorable pivot makes the partitioning process more costly.
Perhaps someone can show with a simple example how array
with [1,2,3]
and pivot [0]
how the worst performance is performed so that I can see how it all relates to each other.
source to share
-
Yes, a randomized pivot element just makes the worst case unlikely.
-
A sufficient condition would be that the choice of rotation given by an array of length n always splits it into two arrays of the same O (1) length.
-
Suppose you have some kind of rule that when you call i, the algorithm selects the array element
values
at position v (n, i) as the pivot element (the example you gave is that v (n, i) = 0 always, i.e. the algorithm always looks at the first element). Then install:values_0 [v (n, 0)] = 0
values_1 [v (n, 1)] = 1
values_2 (v (n, 2)] = 2
....
where values_i is an array formed from the original array by omitting elements in v (n, j) for j <i.
Regarding your example [1, 2, 3] and rotation 0, as far as I know, it is undefined. You cannot get a worst-case example using a fixed pivot element, since the recursion will never end.
source to share