Dlaczego sortowanie przez wybór jest szybsze niż sortowanie bąbelkowe?

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

Aby odpowiedzieć na Twoje pytanie, potrzebujemy d skupić się na szczegółowej analizie tych dwóch algorytmów. Tę analizę można przeprowadzić ręcznie lub znaleźć w wielu książkach. Wykorzystam wyniki z Sztuki programowania komputerowego Knutha .

Średnia liczba porównań:

• Sortowanie bąbelkowe : $ \ frac {1} {2} (N ^ 2-N \ ln N – (\ gamma + \ ln2 -1) N) + \ mathcal O (\ sqrt N) $
• Sortowanie przez wstawianie : $ \ frac {1} {4} (N ^ 2-N) + N – H_N $
• Sortowanie przez wybór : $ (N + 1) H_N – 2N $

Jeśli narysujesz te funkcje, otrzymasz coś takiego:

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 sortować, możemy losowo permutować sekwencję wejściową (używając dowolnej metody), aby uzyskać średni przypadek.

Pominąłem analizę złożoności czasowej, ponieważ zależy to od implementacji, ale można użyć podobnych metod.

Komentarze

• Mam problem z ” możemy losowo permutować sekwencję wejściową, aby uzyskać średnią wielkość liter „. Dlaczego można to zrobić szybciej niż czas potrzebny do sortowania?
• Możesz permutować dowolną sekwencję liczb, która zajmie $ N $ czasu, gdzie $ N $ jest długością sekwencji. Jest ' oczywiste, że każdy algorytm sortowania oparty na porównaniu musi mieć złożoność co najmniej $ \ mathcal O (N \ log N) $, więc nawet jeśli dodasz do niego $ N $ ' nie zmienił się tak bardzo '. Zresztą mówimy o porównaniu, a nie o czasie, złożoność czasowa zależy od implementacji i uruchomionej maszyny, jak wspomniałem w odpowiedzi.
• Myślę, że byłem śpiący, masz rację, sekwencja może być permutowana w czasie liniowym .
• Od $ H_N = \ Theta (log N) $, czy twoje porównanie jest poprawne dla sortowania przez wybór? Wygląda na to, że ' sugerujesz, że wykonuje on średnio O (n log n) porównań.
• Gamma = 0,577216 to Euler-Mascheroni ' s stała. Odpowiedni rozdział to ” Sztuka programowania ” tom 3 sekcja 5.2.2 str. 109 i 129. Jak dokładnie wykreśliłeś przypadek sortowania bąbelkowego, szczególnie termin O (sqrt (N))? Czy po prostu to zaniedbałeś?

Asymptotyczny koszt, czyli $ \ mathcal O $ -notacja, opisuje ograniczające zachowanie funkcji, gdy jej argument dąży do nieskończoności, tj. jej tempo wzrostu.

Sama funkcja, np. liczba porównań i / lub swapów może być różna dla dwóch algorytmów o tym samym asymptotycznym koszcie, pod warunkiem, że rosną w tym samym tempie.

Dokładniej rzecz biorąc, sortowanie bąbelkowe wymaga średnio n / 4 USD $ swapy na wpis (każdy wpis jest przenoszony elementowo z pozycji początkowej do pozycji końcowej, a każda zamiana obejmuje dwa wpisy), podczas gdy sortowanie przez wybór wymaga tylko 1 $ (po znalezieniu minimum / maksimum jest wymieniane raz do końca tablicy).

Jeśli chodzi o liczbę porównań, sortowanie bąbelkowe wymaga $ k \ razy n $ porównań, gdzie $ k $ to maksymalna odległość między początkową pozycją wpisu a jego końcowa pozycja, która jest zwykle większa niż $ n / 2 $ dla równomiernie rozłożonych wartości początkowych. Sortowanie przez wybór zawsze wymaga jednak porównań $ (n-1) \ times (n-2) / 2 $.

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

Komentarze

• to jest nawet bardzo dobra odpowiedź
• którą książkę preferujesz?
• @GrijeshChauhan: Książki to kwestia gustu, więc każdą rekomendację traktuj z przymrużeniem oka. Osobiście lubię Cormena, Leisersona i Rivesta ' s ” Wprowadzenie do algorytmów „, co daje dobry przegląd wielu tematów, a Knuth ' s ” Sztuka programowania komputerowego „, jeśli potrzebujesz więcej / wszystkich szczegółów na dowolny temat. Możesz zechcieć sprawdzić, czy pytanie o książki nie zostało tu zadane wcześniej, lub opublikować to pytanie, jeśli nie ' t.
• Dla mnie trzeci akapit Twoja odpowiedź jest właściwą odpowiedzią. Nie wykresy dla dużych danych wejściowych podane w innej odpowiedzi.

Sortowanie bąbelkowe wykorzystuje więcej czasów wymiany, podczas gdy sortowanie przez wybór pozwala tego uniknąć.

Wybierając sortowanie, zamienia się co najwyżej n razy. ale podczas sortowania bąbelkowego zamienia prawie n*(n-1). I oczywiście czas czytania to mniej niż czas pisania nawet w pamięci. Czas porównania i inny czas działania można zignorować. Tak więc czas wymiany jest krytycznym wąskim gardłem problemu.

Komentarze

• Myślę, że druga odpowiedź Bartka jest bardziej rozsądna, ale mogę ' t głosować lub komentarz … Nawiasem mówiąc, nadal uważam, że czas pisania ma większy wpływ i mam nadzieję, że on to weźmie pod uwagę, jeśli zobaczy to i zgodzi się.
• Nie można po prostu ignorować 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 poświęcony na zamianę dwóch elementów. Rozważ połączoną listę bardzo długich ciągów (powiedzmy 100 000 znaków każdy). Odczytanie każdego ciągu zajęłoby znacznie więcej czasu niż zmiana przypisania wskaźnika.
• @IrvinLim Myślę, że możesz mieć rację, ale być może będę musiał zobaczyć dane statystyczne, zanim zmienię zdanie.