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ównania | Sortowanie bąbelkowe | Wybór sortowania |
|---|---|---|
| Podstawowy | Sąsiedni element jest porównywany i zamieniany | Największy element jest wybierany i zamieniany z ostatnim elementem (w przypadku rosnącej kolejności). |
| Najlepsza złożoność czasu sprawy | Na) | O (n 2 ) |
| Wydajność | Nieskuteczny | Poprawiona wydajność w porównaniu do sortowania bąbelkowego |
| Stabilny | tak | Nie |
| metoda | Wymiana | Wybór |
| Prędkość | Powolny | Szybko 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.
Kluczowe różnice między sortowaniem bąbelków i wyborem sortowania
- 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.
- 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.
- Sortowanie bąbelkowe jest stabilnym algorytmem, w przeciwieństwie do sortowania selekcji jest niestabilne.
- 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.
