Różnica między sortowaniem bąbelkowym a sortowaniem wstawianym

Sortowanie bąbelkowe a sortowanie wstawiane

Sortowanie bąbelkowe to algorytm sortowania, który działa poprzez wielokrotne przeglądanie listy, która ma być sortowana, podczas porównywania par sąsiadujących elementów. Jeśli para elementów jest w niewłaściwej kolejności, są one zamieniane, aby umieścić je we właściwej kolejności. To przejście jest powtarzane, dopóki nie są wymagane żadne dalsze zamiany. Sortowanie wstawiania jest również algorytmem sortowania, który działa poprzez wstawienie elementu na liście wejściowej w odpowiednie miejsce na liście, która jest już posortowana. Ten proces jest powtarzany do momentu posortowania listy.

Co to jest Sortowanie bąbelkowe?

Sortowanie bąbelkowe to algorytm sortowania, który działa poprzez wielokrotne przeglądanie listy, która ma być sortowana, podczas porównywania par sąsiadujących elementów. Jeśli para elementów jest w niewłaściwej kolejności, są one zamieniane, aby umieścić je we właściwej kolejności. To przejście jest powtarzane, dopóki nie są wymagane żadne zamiany (co oznacza, że ​​lista jest posortowana). Ponieważ mniejsze elementy na liście znajdują się na górze, gdy bąbelek wychodzi na powierzchnię, nadano mu nazwę sortowania bąbelkowego. Sortowanie bąbelkowe jest bardzo prostym algorytmem sortowania, ale ma średnią złożoność czasu obserwacji wynoszącą O (n2) podczas sortowania listy zawierającej n elementów. Z tego powodu sortowanie bąbelkowe nie nadaje się do sortowania list z dużą liczbą elementów. Ale ze względu na swoją prostotę nauczanie sortowania bąbelkowego odbywa się podczas wprowadzania do algorytmów.

Co to jest Sortowanie wstawiane?

Sortowanie wstawiania to kolejny algorytm sortowania, który działa poprzez wstawienie elementu na liście wejściowej w odpowiednie miejsce na liście (która jest już posortowana). Ten proces jest powtarzany do momentu posortowania listy. W sortowaniu przez wstawianie sortowanie odbywa się na miejscu. Dlatego po i-tej iteracji algorytmu pierwsze pozycje i + 1 na liście zostaną posortowane, a reszta listy nie będzie posortowana. Przy każdej iteracji pierwszy element nieposortowanej części listy będzie pobierany i wstawiany we właściwe miejsce w posortowanej sekcji listy. Sortowanie wstawiania ma średnią złożoność czasu obserwacji wynoszącą O (n2). Z tego powodu sortowanie wstawiane nie nadaje się również do sortowania dużych list.

Jaka jest różnica między sortowaniem bąbelkowym a sortowaniem wstawianym?

Mimo że zarówno algorytmy sortowania bąbelkowego, jak i algorytmy sortowania wstawianego mają średni stopień złożoności wielkości liter O (n2), sortowanie bąbelkowe jest prawie zawsze lepsze niż sortowanie wstawiane. Wynika to z liczby wymian wymaganych przez dwa algorytmy (sortowanie bąbelkowe wymaga większej liczby wymian). Jednak ze względu na prostotę sortowania bąbelkowego jego kod jest bardzo mały. Istnieje również wariant sortowania wstawianego zwany sortowaniem skorupowym, który ma złożoność czasową O (n3 / 2), co pozwoliłoby na jego praktyczne zastosowanie. Ponadto sortowanie wstawiane jest bardzo wydajne w przypadku sortowania list „prawie posortowanych” w porównaniu z sortowaniem bąbelkowym.