|
|
Sortowanie bąbelkowe |
Ważne definicje:
Algorytmy sortowania:
|
Algorytm sortowania bąbelkowego polega na porównywaniu par elementów leżących obok siebie i, jeśli jest to potrzebne, zmienianiu ich kolejności. Czyli w pierwszym przebiegu porównujemy (i ewentualnie zamieniamy):
Po pierwszym przebiegu ciąg nie musi być jeszcze uporządkowany, ale na pozycji n znajdzie się maksymalny element ciągu. Zatem w drugim przebiegu można porządkować ciąg krótszy, czyli tylko elementy na pozycjach od 1 do n-1. Po drugim przebiegu, dwa ostatnie elementy są na swoich miejscach, czyli pozostaje posortować ciąg o dwa elementy krótszy, itd. Można jeszcze bardziej usprawnić ten algorytm. Jeżeli w pewnym przebiegu algorytmu ostatnia zamiana nastąpiła na pozycji i, to w następnym przebiegu wystarczy porządkować tylko elementy na pozycjach od 1 do i-1. W takiej wersji ten algrytm jest zrealizowany w demonstracji. Jeżeli dane wejściowe są uporządkowane, to algorytm wykonuje tylko jeden przebieg (nie jest wykonywana żadna zamiana).
|
Sortowanie bąbelkowe
Strona główna Sortowanie bąbelkowe Sortowanie przez wstawianie Sortowanie przez binarne wstawianie Sortowanie przez wybór Sortowanie przez scalanie Sortowanie przez scalanie - rozszerzone Sortowanie szybkie Sortowanie stogowe Sortowanie stogowe rozszerzone Porównanie algorytmów
