Sortowanie przez wstawianie a algorytmy sortowania bąbelkowego

Próbuję zrozumieć kilka algorytmów sortowania, ale staram się dostrzec różnicę w algorytmie sortowania bąbelkowego i sortowania przez wstawianie.

Wiem, że oba są O (n ² ), ale wydaje mi się, że sortowanie bąbelkowe po prostu przesuwa maksymalną wartość tablicy na górę dla każdego przebiegu, podczas gdy sortowanie przez wstawianie po prostu zrzuca najniższą wartość na dół każdego przebiegu. Czy nie robią dokładnie tego samego, ale w różnych kierunkach?

W przypadku sortowania przez wstawianie liczba porównań / potencjalnych zamiany zaczyna się od zera i rośnie za każdym razem (tj. 0, 1, 2, 3, 4, ..., n), ale w przypadku sortowania bąbelkowego dzieje się to samo, ale na końcu sortowanie (tj. n, n-1, n-2, ... 0), ponieważ sortowanie bąbelkowe nie musi już porównywać się z ostatnimi elementami podczas ich sortowania.

Mimo wszystko wydaje się, że konsensus jest co do tego, że sortowanie przez wstawianie jest ogólnie lepsze. Czy ktoś może mi powiedzieć dlaczego.

Edycja: Interesują mnie przede wszystkim różnice w działaniu algorytmów, nie tyle ich wydajność czy asymptotyczna złożoność.

W sortowaniu bąbelkowym w i-tej iteracji masz wewnętrzne iteracje ni-1 (n ^ 2) / 2 łącznie, ale w sortowaniu przez wstawianie masz maksimum i iteracji na i-tym kroku, ale średnio i / 2, ponieważ możesz zatrzymać pętlę wewnętrzną wcześniej, po znalezieniu prawidłowej pozycji dla bieżącego elementu. Więc masz (suma od 0 do n) / 2, czyli (n ^ 2) / 4 łącznie;

Dlatego sortowanie przez wstawianie jest szybsze niż sortowanie bąbelkowe.

Sortowanie przez wstawianie

Po I iteracji pierwszej I elementy są uporządkowane.

W każdej iteracji następny element jest przepuszczany przez posortowaną sekcję, aż osiągnie właściwe miejsce:

sorted  | unsorted
1 3 5 8 | 4 6 7 9 2
1 3 4 5 8 | 6 7 9 2

4 jest wrzucany do posortowanej sekcji

Pseudo kod:

for i in 1 to n
    for j in i downto 2
        if array[j - 1] > array[j]
            swap(array[j - 1], array[j])
        else
            break

Sortowanie bąbelkowe

Po I iteracji ostatnie I elementy są największe i polecił.

W każdej iteracji przejrzyj nieposortowaną sekcję, aby znaleźć maksimum.

unsorted  | biggest
3 1 5 4 2 | 6 7 8 9
1 3 4 2 | 5 6 7 8 9

5 jest wypisywane z nieposortowanej sekcji

Pseudo kod:

for i in 1 to n
    for j in 1 to n - i
         if array[j] > array[j + 1]
             swap(array[j], array[j + 1])

Zwróć uwagę, że typowe implementacje kończą się wcześniej, jeśli podczas jednej z iteracji zewnętrznej pętli nie są dokonywane żadne zamiany (ponieważ oznacza to, że tablica jest posortowana).

Różnica

W sortowaniu przez wstawianie elementy są przepuszczane do posortowanej sekcji, podczas gdy w sortowaniu bąbelkowym wartości maksymalne są wypuszczane z nieposortowanej sekcji.

Kolejna różnica, której tutaj nie widziałem:

Sortowanie bąbelkowe ma 3 przypisania wartości na zamianę : najpierw musisz zbudować zmienną tymczasową, aby zapisać wartość, którą chcesz przesunąć do przodu (nr 1), niż musisz zapisać drugą zmienną wymiany w miejscu, w którym właśnie zapisałeś wartość z (nr 2), a następnie w innym miejscu należy wpisać zmienną tymczasową (nr 3). Musisz to zrobić dla każdego miejsca - chcesz iść do przodu - aby posortować zmienną we właściwym miejscu.

W przypadku sortowania przez wstawianie umieszczasz zmienną do sortowania w zmiennej tymczasowej, a następnie umieszczasz wszystkie zmienne przed tym miejscem o 1 miejsce wstecz, o ile osiągniesz właściwe miejsce dla swojej zmiennej. To daje 1 przypisanie wartości na miejsce . W końcu wpisujesz zmienną tymczasową w to miejsce.

To sprawia, że ​​przypisywanie wartości jest znacznie mniejsze.

Nie jest to największa korzyść związana z szybkością, ale myślę, że można o tym wspomnieć.

Mam nadzieję, że wyraziłem się zrozumiale, jeśli nie, to przepraszam, nie jestem rdzenną Brytanią

Główną zaletą sortowania przez wstawianie jest to, że jest to algorytm online. Nie musisz mieć wszystkich wartości na początku. Może to być przydatne, gdy mamy do czynienia z danymi pochodzącymi z sieci lub jakiegoś czujnika.

Mam wrażenie, że byłoby to szybsze niż inne konwencjonalne n log(n)algorytmy. Ponieważ złożoność polegałaby n*(n log(n))np. Na odczytaniu / przechowywaniu każdej wartości ze stream ( O(n)), a następnie sortowaniu wszystkich wartości ( O(n log(n))), co skutkowałobyO(n^2 log(n))

Wręcz przeciwnie, użycie Sortowania Wstawiania wymaga O(n)odczytania wartości ze strumienia i O(n)umieszczenia wartości we właściwym miejscu, więc jest to O(n^2)tylko. Inną zaletą jest to, że nie potrzebujesz buforów do przechowywania wartości, sortujesz je w miejscu docelowym.

Funkcja Bubble Sort nie działa w trybie online (nie może sortować strumienia danych wejściowych bez wiedzy o liczbie elementów), ponieważ tak naprawdę nie śledzi globalnego maksimum posortowanych elementów. Po włożeniu elementu należy rozpocząć bulgotanie od samego początku

cóż, sortowanie bąbelkowe jest lepsze niż sortowanie przez wstawianie tylko wtedy, gdy ktoś szuka górnych k elementów z dużej listy, np. w sortowaniu bąbelkowym po k iteracjach otrzymasz k górnych elementów. Jednak po k iteracjach w sortowaniu przez wstawianie zapewnia tylko, że te k elementów są posortowane.

Chociaż oba rodzaje są O (N ^ 2). Ukryte stałe są znacznie mniejsze w sortowaniu przez wstawianie. Ukryte stałe odnoszą się do rzeczywistej liczby wykonanych operacji pierwotnych.

Kiedy sortowanie przez wstawianie ma lepszy czas działania?

1. Array jest prawie posortowany - zauważ, że sortowanie przez wstawianie wykonuje w tym przypadku mniej operacji niż sortowanie bąbelkowe.
2. Tablica ma stosunkowo mały rozmiar: sortowanie przez wstawianie przenosi elementy dookoła, aby umieścić bieżący element. Jest to lepsze tylko niż sortowanie bąbelkowe, jeśli liczba elementów jest niewielka.

Zauważ, że sortowanie przez wstawianie nie zawsze jest lepsze niż sortowanie bąbelkowe. Aby uzyskać to, co najlepsze z obu światów, możesz użyć sortowania przez wstawianie, jeśli tablica ma mały rozmiar, i prawdopodobnie sortowanie przez scalanie (lub szybkie sortowanie) dla większych tablic.

Sortowanie bąbelkowe jest prawie bezużyteczne w każdych okolicznościach. W przypadkach użycia, gdy sortowanie przez wstawianie może mieć zbyt wiele zamian, można użyć sortowania przez wybór, ponieważ gwarantuje mniej niż N razy zamiany. Ponieważ sortowanie przez wybór jest lepsze niż sortowanie bąbelkowe, sortowanie bąbelkowe nie ma przypadków użycia.

Liczba wymiany w każdej iteracji

• Sortowanie przez wstawianie wykonuje co najwyżej 1 zamianę w każdej iteracji .
• Bubble-sort wykonuje zamiany od 0 do n w każdej iteracji.

Dostęp i zmiana posortowanej części

• Sortowanie przez wstawianie umożliwia dostęp (i zmienia w razie potrzeby) posortowaną część w celu znalezienia prawidłowego położenia rozważanej liczby.
• Po optymalizacji, sortowanie bąbelkowe nie ma dostępu do tego, co już zostało posortowane.

Online czy nie

• Sortowanie przez wstawianie jest online. Oznacza to, że sortowanie przez wstawianie przyjmuje po jednym wejściu na raz, zanim ustawi się w odpowiedniej pozycji. Nie musi tylko porównywaćadjacent-inputs .
• Sortowanie bąbelkowe nie jest dostępne online. Nie obsługuje jednego wejścia na raz. Obsługuje grupę danych wejściowych (jeśli nie wszystkie) w każdej iteracji. Sortowanie bąbelkowe porównuje i zamienia tylkoadjacent-inputs w każdej iteracji.

sortowanie przez wstawianie:

W przypadku sortowania przez wstawianie zamiana nie jest wymagana.

2. złożoność czasowa sortowania przez wstawianie wynosi Ω (n) dla najlepszego przypadku i O (n ^ 2) dla najgorszego przypadku.

3. mniej złożone w porównaniu z sortowaniem bąbelkowym.

4. przykład: włóż książki do biblioteki, ułóż karty.

sortowanie bąbelkowe: 1.Wymagane podmiany w sortowaniu bąbelkowym.

2. złożoność czasowa sortowania bąbelkowego wynosi Ω (n) dla najlepszego przypadku i O (n ^ 2) dla najgorszego przypadku.

3. bardziej złożone w porównaniu z sortowaniem przez wstawianie.

Sortowanie przez wstawianie można wznowić w następujący sposób: „ Poszukaj elementu, który powinien znajdować się na pierwszej pozycji (minimum), zrób trochę miejsca przesuwając kolejne elementy i umieść go na pierwszej pozycji. Dobrze. Spójrz teraz na element, który powinien być na drugim. ... ”i tak dalej ...

Sortowanie bąbelkowe działa inaczej i można je wznowić, jeśli tylko znajdę dwa sąsiednie elementy, które są w złej kolejności, zamieniam je .