Sortowanie bąbelkowe a sortowanie przez wstawianie
Sortowanie bąbelkowe to algorytm sortowania, który działa poprzez przechodzenie przez listę w celu wielokrotnego sortowania podczas porównywania par sąsiadujących ze sobą elementów. Jeśli para elementów jest w złej kolejności, są one zamieniane w celu umieszczenia ich we właściwej kolejności. To przechodzenie jest powtarzane, dopóki nie są wymagane żadne dalsze wymiany. Sortowanie przez wstawianie to również algorytm sortowania, który działa poprzez wstawienie elementu z listy wejściowej we właściwej pozycji na liście, która jest już posortowana. Ten proces jest powtarzany, dopóki lista nie zostanie posortowana.
Co to jest sortowanie bąbelkowe?
Sortowanie bąbelkowe to algorytm sortowania, który działa poprzez przechodzenie przez listę w celu wielokrotnego sortowania podczas porównywania par sąsiadujących ze sobą elementów. Jeśli para elementów jest w złej kolejności, są one zamieniane w celu umieszczenia ich we właściwej kolejności. To przechodzenie jest powtarzane, dopóki nie są wymagane żadne dalsze wymiany (co oznacza, że lista jest posortowana). Ponieważ mniejsze elementy na liście pojawiają się na górze, gdy bąbelek wynurza się na powierzchnię, nadano mu nazwę sortowanie bąbelkowe. Sortowanie bąbelkowe jest bardzo prostym algorytmem sortowania, ale ma średnią złożoność czasu przypadku 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ę, sortowanie bąbelkowe jest nauczane podczas wprowadzania do algorytmów.
Co to jest sortowanie przez wstawianie?
Sortowanie przez wstawianie to kolejny algorytm sortowania, który działa poprzez wstawienie elementu na liście wejściowej we właściwej pozycji na liście (która jest już posortowana). Ten proces jest powtarzany, dopóki lista nie zostanie posortowana. W sortowaniu przez wstawianie sortowanie odbywa się na miejscu. Dlatego po iteracji algorytmu pierwsze wpisy i+1 na liście zostaną posortowane, a reszta listy nie będzie sortowana. W każdej iteracji pierwszy element z nieposortowanej części listy zostanie pobrany i wstawiony we właściwe miejsce w posortowanej części listy. Sortowanie przez wstawianie ma średnią złożoność czasu przypadku O(n2). Z tego powodu sortowanie przez wstawianie nie nadaje się również do sortowania dużych list.
Jaka jest różnica między sortowaniem bąbelkowym a sortowaniem przez wstawianie?
Mimo że zarówno algorytmy sortowania bąbelkowego, jak i sortowania przez wstawianie mają średnią złożoność czasu przypadku wynoszącą O(n2), sortowanie bąbelkowe jest prawie przez cały czas lepsze niż sortowanie przez wstawianie. Wynika to z liczby zamian wymaganych przez oba algorytmy (sortowanie bąbelkowe wymaga większej liczby zamian). Jednak ze względu na prostotę sortowania bąbelkowego jego rozmiar kodu jest bardzo mały. Istnieje również wariant sortowania przez wstawianie, zwany sortowaniem powłokowym, który ma złożoność czasową O(n3/2), co pozwoliłoby na jego praktyczne zastosowanie. Co więcej, sortowanie przez wstawianie jest bardzo wydajne w przypadku sortowania „prawie posortowanych” list w porównaniu z sortowaniem bąbelkowym.
