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

Sortowanie bąbelkowe a sortowanie selekcyjne

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 selekcji to także algorytm sortowania, który rozpoczyna się od znalezienia minimalnego elementu na liście i zamiany go z pierwszym elementem. Proces ten powtarza się dla pozostałej części listy, umieszczając zamienione elementy w kolejności.

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 selekcji?

Sortowanie selekcji to także kolejny algorytm sortowania, który rozpoczyna się od znalezienia minimalnego elementu na liście i zamiany go z pierwszym elementem. Następnie minimalny element jest znajdowany od reszty listy (od drugiego elementu do ostatniego elementu na liście) i zamieniany z drugim elementem. Proces ten powtarza się dla pozostałej części listy, umieszczając zamienione elementy w kolejności. Tak więc w sortowaniu selekcyjnym na każdym etapie algorytmu lista jest podzielona na dwie części, w których jedna część zawiera posortowane elementy, a druga część zawiera nieposortowane elementy. W miarę postępowania algorytmu posortowana lista rośnie od lewej do prawej. Sortowanie selekcji ma również średnią złożoność czasu obserwacji wynoszącą O (n2). Dlatego nie nadaje się również do sortowania dużych list.

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

Mimo że zarówno algorytmy sortowania bąbelkowego, jak i algorytmy sortowania selekcji mają średnią złożoność przypadków (O2), sortowanie bąbelkowe jest prawie zawsze lepsze niż sortowanie selekcyjne. 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. Stabilność to kolejna różnica w tych dwóch algorytmach. Stabilny algorytm sortowania to algorytm sortowania, który zachowuje porządek rekordów, jeśli lista zawiera elementy o równej wartości. W tym sensie sortowanie selekcyjne nie jest algorytmem stabilnym, podczas gdy sortowanie bąbelkowe jest algorytmem stabilnym.