Dlaczego wybór sortuje się szybciej niż sortowanie bąbelkowe?

28

Na Wikipedii napisano, że „... sortowanie selekcji prawie zawsze przewyższa sortowanie bąbelkowe i sortowanie gnomów”. Czy ktoś może mi wyjaśnić, dlaczego sortowanie jest uważane za szybsze niż sortowanie bąbelkowe, mimo że oba mają:

  1. Złożoność najgorszego przypadku :O(n2)

  2. Liczba porównań : O(n2)

  3. Najlepsza złożoność czasu sprawy :

    • Sortowanie bąbelkowe:O(n)
    • Wybór sortowania:O(n2)
  4. Średnia złożoność czasu sprawy :

    • Sortowanie bąbelkowe:O(n2)
    • Wybór sortowania:O(n2)
RYO
źródło

Odpowiedzi:

32

Wszystkie podane przez Ciebie złożoności są prawdziwe, jednak podane są w notacji Big O , więc wszystkie wartości addytywne i stałe są pomijane.

Aby odpowiedzieć na twoje pytanie, musimy skoncentrować się na szczegółowej analizie tych dwóch algorytmów. Analizę tę można wykonać ręcznie lub znaleźć w wielu książkach. Wykorzystam wyniki z Knuth's Art of Computer Programming .

Średnia liczba porównań:

  • Sortowanie bąbelkowe :12(N2NlnN(γ+ln21)N)+O(N)
  • Sortowanie wstawek :14(N2N)+NHN
  • Sortowanie wyboru :(N+1)HN2N

Teraz, jeśli wykreślisz te funkcje, otrzymasz coś takiego: wątek działka 2

Jak widać, sortowanie bąbelkowe jest znacznie gorsze wraz ze wzrostem liczby elementów, mimo że obie metody sortowania mają tę samą asymptotyczną złożoność.

Ta analiza opiera się na założeniu, że dane wejściowe są losowe - co może nie być prawdą przez cały czas. Jednak zanim zaczniemy sortowanie, możemy losowo permutować sekwencję wejściową (dowolną metodą), aby uzyskać średnią wielkość liter.

Pominąłem analizę złożoności czasu, ponieważ zależy to od implementacji, ale można zastosować podobne metody.

Bartosz Przybylski
źródło
Mam problem z „możemy losowo permutować sekwencję wejściową, aby uzyskać przypadek średniej”. Dlaczego można tego dokonać szybciej niż czas potrzebny na sortowanie?
Sasho Nikolov
1
Możesz permutować dowolną sekwencję liczb, zajmie to czasu, gdzie jest długością sekwencji. Oczywiste jest, że każdy algorytm sortowania oparty na porównaniach musi mieć co najmniej złożoność więc nawet jeśli dodasz do jego złożoności, nie zmieni się ona tak bardzo. W każdym razie mówimy o porównaniu, a nie o czasie, złożoność czasu zależy od implementacji i uruchomienia maszyny, jak wspomniałem w odpowiedzi. N O ( N log N ) NNNO(NlogN)N
Bartosz Przybylski
Myślę, że byłem śpiący, masz rację, sekwencję można permutować w czasie liniowym.
Sasho Nikolov
Ponieważ , czy twoje porównanie jest poprawne dla sortowania selekcji? Wygląda na to, że sugerujesz, że średnio dokonuje porównań O (n log n). HN=Θ(logN)
templatetypedef
Gamma = 0,577216 jest stałą Eulera-Mascheroniego. Odpowiednim rozdziałem jest „Sztuka programowania” tom 3 sekcja 5.2.2 str. 109 i 129. W jaki sposób wykreśliłeś przypadek sortowania bąbelkowego, a zwłaszcza wyraz O (sqrt (N))? Po prostu to zaniedbałeś?
mxmlnkn
11

Koszt asymptotyczny, czyli matematyczna adnotacja , opisuje ograniczające zachowanie funkcji, ponieważ jej argument dąży do nieskończoności, tj. Jej tempa wzrostu.O

Sama funkcja, np. Liczba porównań i / lub swapów, może być inna dla dwóch algorytmów o tym samym koszcie asymptotycznym, pod warunkiem, że będą rosły z tą samą szybkością.

Mówiąc dokładniej, sortowanie bąbelkowe wymaga średnio zamian na wpis (każdy wpis jest przenoszony elementarnie z pozycji początkowej do końcowej, a każda zamiana obejmuje dwa wpisy), podczas gdy sortowanie selekcji wymaga tylko (raz minimalna / maksymalna została znaleziona, jest zamieniana raz na koniec tablicy).1n/41

Pod względem liczby porównań sortowanie bąbelkowe wymaga porównań , gdzie jest maksymalną odległością między pozycją początkową pozycji a jej pozycją końcową, która jest zwykle większa niż dla równomiernie rozłożonych wartości początkowych. Sortowanie selekcji wymaga jednak zawsze porównań .k n / 2 ( n - 1 ) × ( n - 2 ) / 2k×nkn/2(n1)×(n2)/2

Podsumowując, limit asymptotyczny daje dobre wyobrażenie o tym, jak rosną koszty algorytmu w stosunku do wielkości wejściowej, ale nie mówi nic o względnej wydajności różnych algorytmów w tym samym zestawie.

Pedro
źródło
1
to jest nawet bardzo dobra odpowiedź
Grijesh Chauhan,
którą książkę wolisz?
Grijesh Chauhan
@GrijeshChauhan: Książki są kwestią gustu, więc weź każde zalecenie z odrobiną soli. Osobiście lubię „Wprowadzenie do algorytmów” Cormena, Leisersona i Rivesta, które dają dobry przegląd wielu tematów, oraz serię „Sztuka programowania komputerowego” Knutha, jeśli potrzebujesz więcej / wszystkich szczegółów na dowolny temat. Możesz sprawdzić, czy pytanie o książki zostało już wcześniej zadane, lub opublikować to pytanie, jeśli nie zostało zadane.
Pedro
Dla mnie trzeci akapit w twojej odpowiedzi jest faktyczną odpowiedzią. Nie wykresy dla dużych danych wejściowych, podane w innej odpowiedzi.
nadmierna wymiana
3

Sortowanie bąbelkowe wykorzystuje więcej czasów zamiany, podczas gdy sortowanie selekcyjne pozwala tego uniknąć.

Podczas korzystania z wyboru sortowania zamienia się nco najwyżej razy. ale przy użyciu sortowania bąbelkowego prawie zamienia się n*(n-1). Oczywiście czas czytania jest krótszy niż czas pisania, nawet w pamięci. Czas porównania i inny czas działania można zignorować. Czasy wymiany są więc kluczowym wąskim gardłem problemu.

simonmysun
źródło
Myślę, że druga odpowiedź Bartka jest bardziej rozsądna, ale nie mogę głosować ani komentować ... BTW nadal uważam, że czas pisania wpływa na większy czas i mam nadzieję, że może wziąć to pod uwagę, jeśli to zobaczy i wyrazi zgodę.
simonmysun
Nie można po prostu zignorować liczby porównań, ponieważ istnieją przypadki użycia, w których czas poświęcony na porównanie dwóch elementów może znacznie przekroczyć czas spędzony na zamianie dwóch elementów. Rozważ połączoną listę bardzo długich ciągów (powiedzmy 100 000 znaków). Czytanie w każdym łańcuchu zajęłoby znacznie więcej czasu niż ponowne przypisanie wskaźnika.
Irvin Lim
@IrvinLim Myślę, że masz rację, ale być może będę musiał zobaczyć dane statystyczne, zanim zmienię zdanie.
simonmysun 30.04.16