Sortowanie bąbelkowe a sortowanie przez wybór
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 wybór to również algorytm sortowania, który rozpoczyna się od znalezienia minimalnego elementu na liście i zamienienia go na pierwszy element. Ten proces jest powtarzany 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 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 wyboru?
Sortowanie przez wybór to także kolejny algorytm sortowania, który rozpoczyna się od znalezienia minimalnego elementu na liście i zamienienia go na pierwszy element. Następnie element minimum jest znajdowany z pozostałej części listy (od drugiego elementu do ostatniego elementu na liście) i zamieniany na drugi element. Ten proces jest powtarzany dla pozostałej części listy, umieszczając zamienione elementy w kolejności. Tak więc w sortowaniu przez selekcję, na każdym etapie algorytmu, lista jest dzielona na dwie części, z których jedna zawiera elementy posortowane, a druga zawiera elementy nieposortowane. W miarę postępu algorytmu posortowana lista rośnie od lewej do prawej. Sortowanie przez wybór ma również średnią złożoność czasu przypadku O(n2). Dlatego nie nadaje się również do sortowania dużych list.
Jaka jest różnica między sortowaniem bąbelkowym a sortowaniem przez wybór?
Mimo że zarówno algorytmy sortowania bąbelkowego, jak i sortowania przez selekcję mają średnią złożoność czasu przypadku wynoszącą O(n2), sortowanie bąbelkowe jest prawie zawsze lepsze od sortowania przez selekcję. 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. Stabilność to kolejna różnica w tych dwóch algorytmach. Stabilny algorytm sortowania to algorytm sortowania, który zachowuje kolejność rekordów, jeśli lista zawiera elementy o równej wartości. W tym sensie sortowanie przez selekcję nie jest stabilnym algorytmem, podczas gdy sortowanie bąbelkowe jest stabilnym algorytmem.
