Przestrzeganie zachowania kwadratowego za pomocą quicksort - O (n^2)

Question

Algorytm quicksort ma średnią złożoność czasową O (n * log (n)) i złożoność najgorszego przypadku O (n^2).

Przyjmując niektóre warianty algorytmu quicksort Hoare, jakie dane wejściowe spowodują, że algorytm quicksort będzie wykazywał najgorszy przypadek?

Proszę podać wszelkie założenia dotyczące szczegółów implementacji dotyczących konkretnego algorytmu Quicksort, takie jak wybór osi przeglĘ ... dowej itp. Lub czy pochodzą one z powszechnie dostę pnej biblioteki, takiej jak libc.

Niektóre literatura:

1. A Killer Adversary for Quicksort
2. Quicksort Is Optimal
3. Engineering a Sort Function
4. Introspective Sorting and Selection Algorithms

Answer 1

W Quick sort wykonuje najgorszym czyli w O (N^2), kiedy wszystkie wartości wybrany obrót jest największy lub najmniejszy z t Zestaw aken. Rozważ ten przykład.

Czop wybrany znaczy 1, wówczas trzeba 4 elementy po prawej stronie osi i ma elementy po lewej stronie. Stosując tę ​​samą logikę rekursywnie, a wybrany oś wynosi odpowiednio 2, 3, 4, 5, osiągnęliśmy sytuację, w której ten rodzaj wykonywał się w najgorszym możliwym momencie.

Zalecono i udowodniono, że Quicksort działa dobrze, jeśli dane wejściowe są dobrze tasowane.

Co więcej, wybór rodzaju sortowania zwykle zależy od jasnej wiedzy na temat domeny wejściowej. Na przykład, jeśli dane wejściowe są ogromne, istnieje coś, co można nazwać sortowaniem zewnętrznym, który może korzystać z pamięci zewnętrznej. Jeśli rozmiar wejściowy jest bardzo mały, możemy wybrać sortowanie scalone, ale nie dla średnich i dużych zestawów wejściowych, ponieważ używa dodatkowej pamięci. Główną zaletą szybkiego sortowania jest znaczenie "na miejscu", nie ma dodatkowej pamięci dla danych wejściowych. Najgorszy czas na papierze to O (n^2), ale nadal jest szeroko preferowany i używany. Chodzi mi o to, że algorytmy sortowania mogą być zmieniane w oparciu o wiedzę na temat zestawu wejściowego i jego kwestię preferencji.

Answer 2

Aby rozwinąć na co Bragboy powiedział, zamiast tylko uruchomiony:

quicksort(array); 

Run:

shuffle(array); 
quicksort(array); 

Jeżeli definicja shuffle() mogą być:

shuffle(array){ 
    for(int i = array.length; i > 0; i--){ 
     r= random number % i; 
     swap(array[i], array[r]); 
    } 
} 

Robi tak będzie , prawdopodobnie, radzimy sobie z przypadkiem uzyskania wejścia, które spowalnia działanie quicksort().

Answer 3

Algorytm Hoare's Quicksort wybiera losowy pivot. Aby uzyskać powtarzalne wyniki, sugerowałbym modyfikację Scowen, która między innymi wybiera środkową pozycję z danych wejściowych.W tym wariancie wzór piłokształtny z najmniejszym trzpieniem wydaje się być najgorszym przypadkiem:

starting with   { j i h g f a e d c b } 
compare 1 to 6   { (j) i h g f (a) e d c b } 
compare 6 to 10   { j i h g f (a) e d c (b) } 
compare 6 to 9   { j i h g f (a) e d (c) b } 
compare 6 to 8   { j i h g f (a) e (d) c b } 
compare 6 to 7   { j i h g f (a) (e) d c b } 
swap 1<=>6    { (a) i h g f (j) e d c b } 
compare 1 to 5   { (a) i h g (f) j e d c b } 
compare 1 to 4   { (a) i h (g) f j e d c b } 
compare 1 to 3   { (a) i (h) g f j e d c b } 
compare 1 to 2   { (a) (i) h g f j e d c b } 
compare 2 to 6   { a (i) h g f (j) e d c b } 
compare 3 to 6   { a i (h) g f (j) e d c b } 
compare 4 to 6   { a i h (g) f (j) e d c b } 
compare 5 to 6   { a i h g (f) (j) e d c b } 
compare and swap 6<=>10 { a i h g f (b) e d c (j) } 
compare 7 to 10   { a i h g f b (e) d c (j) } 
compare 8 to 10   { a i h g f b e (d) c (j) } 
compare 9 to 10   { a i h g f b e d (c) (j) } 
compare 2 to 6   { a (i) h g f (b) e d c j } 
compare 6 to 9   { a i h g f (b) e d (c) j } 
compare 6 to 8   { a i h g f (b) e (d) c j } 
compare 6 to 7   { a i h g f (b) (e) d c j } 
swap 2<=>6    { a (b) h g f (i) e d c j } 
compare 2 to 5   { a (b) h g (f) i e d c j } 
compare 2 to 4   { a (b) h (g) f i e d c j } 
compare 2 to 3   { a (b) (h) g f i e d c j } 
compare 3 to 6   { a b (h) g f (i) e d c j } 
compare 4 to 6   { a b h (g) f (i) e d c j } 
compare 5 to 6   { a b h g (f) (i) e d c j } 
compare and swap 6<=>9 { a b h g f (c) e d (i) j } 
compare 7 to 9   { a b h g f c (e) d (i) j } 
compare 8 to 9   { a b h g f c e (d) (i) j } 
compare 3 to 6   { a b (h) g f (c) e d i j } 
compare 6 to 8   { a b h g f (c) e (d) i j } 
compare 6 to 7   { a b h g f (c) (e) d i j } 
swap 3<=>6    { a b (c) g f (h) e d i j } 
compare 3 to 5   { a b (c) g (f) h e d i j } 
compare 3 to 4   { a b (c) (g) f h e d i j } 
compare 4 to 6   { a b c (g) f (h) e d i j } 
compare 5 to 6   { a b c g (f) (h) e d i j } 
compare and swap 6<=>8 { a b c g f (d) e (h) i j } 
compare 7 to 8   { a b c g f d (e) (h) i j } 
compare 4 to 6   { a b c (g) f (d) e h i j } 
compare 6 to 7   { a b c g f (d) (e) h i j } 
swap 4<=>6    { a b c (d) f (g) e h i j } 
compare 4 to 5   { a b c (d) (f) g e h i j } 
compare 5 to 6   { a b c d (f) (g) e h i j } 
compare and swap 6<=>7 { a b c d f (e) (g) h i j } 
compare and swap 5<=>6 { a b c d (e) (f) g h i j }