Sortowanie bąbelkowe
Sortowanie bąbelkowe jest to jeden z najprostszych algorytmów sortowania. Warty poznania, jednak ze względu na dużą złożoność nie wykorzystywany w kodzie produkcyjnym. Sortowanie to polega na przejściu po tablicy poprzez porównywanie dwóch kolejnych elementów i za każdym razem sprawdzanie czy elementy są w poprawnej kolejności. Jeżeli elementy nie będą w dobrej kolejności zostaną zamienione. Operację tę wykonuje się dotąd, aż cały zbiór nie będzie posortowany.
Wyobraź sobie że grasz w wojnę(karty). Zabawa polega na tym że przetasowane karty dzieli się na dwie części, rozdaje graczom i kładzie koszulkami do góry. Gracze w jednym momencie wykładają po jednej karcie i porównują ich wartości. Gracz mający kartę o wyższej wartości wygrywa. Chodzi tu bardziej o przykład że porównuje się dwie wartości np. ‘Król’ z ‘8’.
Przykład:
Sortowanie rozpoczyna się od pierwszych dwóch elementów, porównując je, sprawdzając który z nich jest większy:
PIERWSZE PRZEJŚCIE
1.Czerwona para została zmieniona ponieważ 7>3.
2.Czerwona para została zmieniona ponieważ 7>1.
3.Czerwona para została zmieniona ponieważ 7>2.
4.Czerwona para została zmieniona ponieważ 7>5.
Po każdej iteracji największy element spośród nieposortowanych elementów zostaje umieszczony na końcu.
DRUGIE PRZEJŚCIE
1.Czerwona para została zmieniona ponieważ 3>1.
2.Czerwona para została zmieniona ponieważ 3>2.
3.Zielona para w dobrej kolejności.
4.Zielona para w dobrej kolejności.
Przykładowy kod w Pythonie:
elements = [7, 3, 1, 2, 5]
size = len(elements)
print("Before sorting:", elements)
for i in range(size):
for j in range(0, size-i-1):
if elements[j] > elements[j+1]:
elements[j], elements[j+1] = elements[j+1], elements[j]
print(elements)
print("After sorting:", elements)
W 6 linii- wykonuje wygenerowanie sekwencji liczb z określonego zakresu.
W 7 linii – po każdej iteracji i-ty największy element znajduje się we właściwym miejscu. Tak więc po pierwszej iteracji największy element znajduje się po prawej stronie. W następnej rundzie ten element już nie musi być porównywany. Po drugiej iteracji drugi co do wielkości element będzie się znajdować po prawej stronie -1(czyli nasz największy element).
Złożoność sortowania bąbelkowego to O(n2)
Istnieją 2 pętle więc złożoność jest n*n=n2
Jak można zoptymalizować sortowanie?
Aby zoptymalizować sortowanie można wprowadzić zmienna np.: ”has_changed” która będzie informować że po każdej iteracji jeżeli elementy się nie zmieniły nie ma potrzeby wykonywać do końca pętli.
Przykład:
elements = [7, 3, 1, 2, 5]
size = len(elements)
print("Before sorting:", elements)
for i in range(size):
has_changed = True
for j in range(0, size-i-1):
if elements[j] > elements[j+1]:
elements[j], elements[j+1] = elements[j+1], elements[j]
has_changed = False
print(elements)
if has_changed:
break
print("After sorting:", elements)
Do sortowania listy w Python można użyć zarówno opcji takich jak sorted() i sort().
FUNKCJA SORTED()
Metoda sorted() zwraca nową posortowaną listę. Nasz 'elements’ nie zostaje zmieniony. Zapewnia posortowane dane wyjściowe:
elements = [7, 3, 1, 2, 5]
print("Before sorting:", elements)
print("After sorting:", sorted(elements))
print(elements)
FUNKCJA LIST.SORT()
Metoda sort() nie zwraca żadnej wartości. Zmienia oryginalną listę czyli nasz 'elements’ został posortowany i nadpisany.
elements = [7, 3, 1, 2, 5]
print("Before sorting:", elements)
elements.sort()
print("After sorting:", elements)
Te funkcje sortowania sorted() oraz sort() implementują algorytm Tim Sort .Został on stworzony w 2002r przez Tima Petersa w celu użycia jako standardowy algorytm sortowania języka Python. Jest to połączenie dwóch innych technik sortowania – sortowania przez wstawianie i sortowania przez scalanie. Cechą tego algorytmu jest to, że wykorzystuje on już posortowane elementy, które istnieją w większości rzeczywistych zbiorów danych. Następnie algorytm wykonuje iteracje po liście, zbierając elementy w serie i łącząc je w jedna posortowaną listę.
PODSUMOWANIE:
W praktyce sortowanie bąbelkowe jest rzadko używane , ale łatwe do zrozumienia.
Zaletą tego sortowania jest prostota algorytmu. Natomiast wadą jest to że
wielokrotnie musi przechodzić przez cały zestaw elementów, porównując jednocześnie tylko dwa sąsiednie elementy, sortowanie bąbelkowe nie jest optymalne dla bardziej obszernych zbiorów danych. Ale może działać dobrze przy sortowaniu tylko niewielkiej liczby elementów lub zbiorów danych, które już w większości są uporządkowane.
