22.03.2022
Sortowanie bąbelkowe
Cześć!
Przedstawię Wam dzisiaj bardzo ciekawy algorytm. Choć w rozwiązywaniu zadań przydaje się niezwykle rzadko, to według mnie jest zdecydowanie warty uwagi. Jest to mianowicie sortowanie bąbelkowe.
Oto podstawowe dane:
Nazwa: sortowanie bąbelkowe
Złożoność czasowa: O(n^2)
Złożoność pamięciowa: O(1)
Na czym polega sortowanie bąbelkowe?
Mamy ciąg n liczb, na przykład:
5 //n
5 4 1 3 2 //liczby
Naszym zadaniem jest posortować ten ciąg np. rosnąco. Jak to zrobimy, używając sortowania bąbelkowego?
Najpierw przechodzimy po całym ciągu, zamieniając te pary liczb, które są uporządkowane w sposób niepoprawny. Po zamianach ciąg będzie wyglądał w ten sposób:
4 5 1 3 2 //zamieniamy 5 z 4
4 1 5 3 2 //zamieniamy 5 z 1
4 1 3 5 2 //zamieniamy 5 z 3
4 1 3 2 5 //zamieniamy 5 z 2
Zauważmy, że liczba 5 trafiła już na właściwe miejsce. Spróbujmy jeszcze raz przejść się po tym ciągu.
1 3 2 4 5 //zamieniamy 4 z 1, 3, 2 i 5
Jeszcze raz:
1 2 3 4 5
Dwójka i jedynka są już na swoim miejscu. Sortowanie skończone!
A więc dlaczego musimy wykonać (pesymistycznie) n^2 operacji?
Przyjrzyjmy się kolejnym krokom. Najpierw przechodzimy przez wszystkie miejsca (n), przy okazji umieszczając największą liczbę na swoim miejscu.
Potem przez n-1 miejsc (ponieważ nie musimy już zamieniać żadnej liczby z największą).
I tak dalej...
Dlatego wykonamy (n*(n+1))/2 operacji (czyli sumę liczb od 1 do n). W związku z tym, że złożoność zapisujemy w sposób dosyć przybliżony, będzie to O(n^2).
Mam nadzieję, że wszystko jest zrozumiałe, a w razie czego zachęcam do poczytania o tym algorytmie w innych źródłach :)
Przedstawię Wam dzisiaj bardzo ciekawy algorytm. Choć w rozwiązywaniu zadań przydaje się niezwykle rzadko, to według mnie jest zdecydowanie warty uwagi. Jest to mianowicie sortowanie bąbelkowe.
Oto podstawowe dane:
Nazwa: sortowanie bąbelkowe
Złożoność czasowa: O(n^2)
Złożoność pamięciowa: O(1)
Na czym polega sortowanie bąbelkowe?
Mamy ciąg n liczb, na przykład:
5 //n
5 4 1 3 2 //liczby
Naszym zadaniem jest posortować ten ciąg np. rosnąco. Jak to zrobimy, używając sortowania bąbelkowego?
Najpierw przechodzimy po całym ciągu, zamieniając te pary liczb, które są uporządkowane w sposób niepoprawny. Po zamianach ciąg będzie wyglądał w ten sposób:
4 5 1 3 2 //zamieniamy 5 z 4
4 1 5 3 2 //zamieniamy 5 z 1
4 1 3 5 2 //zamieniamy 5 z 3
4 1 3 2 5 //zamieniamy 5 z 2
Zauważmy, że liczba 5 trafiła już na właściwe miejsce. Spróbujmy jeszcze raz przejść się po tym ciągu.
1 3 2 4 5 //zamieniamy 4 z 1, 3, 2 i 5
Jeszcze raz:
1 2 3 4 5
Dwójka i jedynka są już na swoim miejscu. Sortowanie skończone!
A więc dlaczego musimy wykonać (pesymistycznie) n^2 operacji?
Przyjrzyjmy się kolejnym krokom. Najpierw przechodzimy przez wszystkie miejsca (n), przy okazji umieszczając największą liczbę na swoim miejscu.
Potem przez n-1 miejsc (ponieważ nie musimy już zamieniać żadnej liczby z największą).
I tak dalej...
Dlatego wykonamy (n*(n+1))/2 operacji (czyli sumę liczb od 1 do n). W związku z tym, że złożoność zapisujemy w sposób dosyć przybliżony, będzie to O(n^2).
Mam nadzieję, że wszystko jest zrozumiałe, a w razie czego zachęcam do poczytania o tym algorytmie w innych źródłach :)