Zalecane, 2019

Wybór Redakcji

Różnica między sortowaniem bąbelków a sortowaniem bąbelków

Sortowanie jest jednym z głównych zadań w programach komputerowych, w których elementy tablicy są ułożone w określonej kolejności. Sortowanie ułatwia wyszukiwanie. Sortowanie bąbelkowe i Sortowanie selekcji to algorytmy sortowania, które można rozróżnić za pomocą metod używanych do sortowania. Sortowanie bąbelkowe zasadniczo wymienia elementy, a sortowanie selekcji wykonuje sortowanie, wybierając element.

Inną znaczącą różnicą między tymi dwoma jest to, że sortowanie bąbelkowe jest stabilnym algorytmem, podczas gdy sortowanie selekcji jest niestabilnym algorytmem. Algorytm jest uważany za stały elementy z tym samym kluczem występującym w tej samej kolejności, w jakiej występowały przed sortowaniem na liście lub tablicy. Ogólnie rzecz biorąc, najbardziej stabilne i szybkie algorytmy wykorzystują dodatkową pamięć.

Wykres porównania

Podstawa do porównaniaSortowanie bąbelkowe
Wybór sortowania
PodstawowySąsiedni element jest porównywany i zamienianyNajwiększy element jest wybierany i zamieniany z ostatnim elementem (w przypadku rosnącej kolejności).
Najlepsza złożoność czasu sprawyNa)O (n 2 )
WydajnośćNieskutecznyPoprawiona wydajność w porównaniu do sortowania bąbelkowego
StabilnytakNie
metodaWymianaWybór
PrędkośćPowolnySzybko w porównaniu do sortowania bąbelkowego

Definicja sortowania bąbelkowego

Sortowanie bąbelkowe to najprostszy algorytm iteracyjny, który polega na porównaniu każdego elementu lub elementu z elementem obok i zamiany ich w razie potrzeby. W prostych słowach porównuje pierwszy i drugi element listy i zamienia go, chyba że są poza określoną kolejnością. Podobnie, drugi i trzeci element są porównywane i zamieniane, a porównywanie i zamiana następują na końcu listy. Liczba porównań w pierwszej iteracji to n-1, gdzie n jest liczbą elementów w tablicy. Największy element będzie na n-tym miejscu po pierwszej iteracji. Po każdej iteracji liczba porównań maleje iw końcu następuje tylko jedno porównanie.

Algorytm ten jest najwolniejszym algorytmem sortowania. Najlepsza złożoność przypadku (gdy lista jest w kolejności) sortowania bąbelkowego jest rzędu n ( O (n) ), a najgorsza złożoność to O (n2) . W najlepszym przypadku jest to zamówienie n, ponieważ po prostu porównuje elementy i nie zamienia ich. Ta technika wymaga również dodatkowej przestrzeni do przechowywania zmiennej tymczasowej.

Definicja sortowania

Sortowanie selekcji osiągnęło nieco lepszą wydajność i jest wydajniejsze niż algorytm sortowania bąbelkowego. Załóżmy, że chcemy uporządkować tablicę w porządku rosnącym, a następnie działa ona, znajdując największy element i wymieniając go z ostatnim elementem, i powtórz następujący proces na pod-tablicach, aż cała lista zostanie posortowana.

W sortowaniu selekcji sortowana i nieposortowana tablica nie robi żadnej różnicy i zużywa kolejność n2 ( O (n2) ) zarówno w najlepszym, jak iw najgorszym przypadku złożoności. Sortowanie zaznaczeń jest szybsze niż sortowanie bąbelkowe.

Kluczowe różnice między sortowaniem bąbelków i wyborem sortowania

  1. W sortowaniu bąbelków każdy element i jego sąsiedni element są porównywane i wymieniane, jeśli jest to wymagane. Z drugiej strony sortowanie selekcji działa, wybierając element i zamieniając ten element z ostatnim elementem. Wybrany element może być największy lub najmniejszy w zależności od kolejności, tj. Rosnącej lub malejącej.
  2. Najgorszy przypadek jest taki sam w obu algorytmach, tj. O (n2), ale najlepsza złożoność jest inna. Sortowanie bąbelkowe zajmuje czas rzędu n, podczas gdy sortowanie zaznaczone zajmuje czas rzędu n2.
  3. Sortowanie bąbelkowe jest stabilnym algorytmem, w przeciwieństwie do sortowania selekcji jest niestabilne.
  4. Algorytm sortowania jest szybki i efektywny w porównaniu do sortowania bąbelkowego, który jest bardzo powolny i nieefektywny.

Wniosek

Algorytm sortowania bąbelkowego jest uważany za najbardziej prosty i nieefektywny algorytm, ale algorytm sortowania sortowania jest skuteczny w porównaniu do sortowania bąbelkowego. Sortowanie bąbelkowe zajmuje również dodatkowe miejsce do przechowywania zmiennych tymczasowych i wymaga większej liczby zamian.

Top