1, 2, 5, 3… zaraz, co?-Czyli sortowanie w praktyce

Pisząc program, w którym chcemy umieścić np. ranking zawodników, lub użyć listy posortowanej rosnąco lub malejąco, musimy znać algorytm, który zajmie się odpowiednim uporządkowaniem listy. Oczywiście istnieje wiele różnych różnych sposobów na wykonanie tego samego zadania, jednak różnią się one wydajnością i złożonością. W tym artykule postanowiłem przybliżyć Ci moim zdaniem najprostszy z algorytmów sortujących, który jest zwany bąbelkowym.

Wstępny zarys i objaśnienie

Nasz algorytm działa na zasadzie porównań, to znaczy bierze dwie liczby znajdujące się obok siebie i zamienia je miejscami w zależności od warunku jaki postawimy i ich wartości. Jeśli weźmiemy listę zawierającą liczby: 5, 4, 3, 2, 1, i będziemy chcieli posortować ją rosnąco, liczba ‚5’ znajdzie się na końcu listy. Spróbujmy teraz uruchomić wyobraźnię i obrócić naszą listę do pozycji pionowej. Zobaczymy że ‚5’ początkowo znajduje się na samym dole (czyli początku), a następnie na skutek wielu porównań i zamian miejsc trafia na szczyt listy czyli jej koniec. Stąd też bierze się nazwa tego algorytmu, ponieważ przemieszczająca się liczba ucieka do góry jak bąbelek w kieliszku szampana (lub oranżady, co kto woli). Poniżej przedstawię swoją implementację tego algorytmu z użyciem języka Python i postaram się objaśnić jak program działa.

Działanie kodu

Na samym początku programu tworzymy pustą jeszcze listę, i ustalamy ile elementów ma ona zawierać. Zadeklarowaliśmy też zmienną „swapped”, której przypisaliśmy wartość „true”, przyda się nam ona później. Wprowadzamy teraz wartości do naszej listy w liczbie zgodnej z tą jaką podaliśmy wcześniej. Teraz przyda nam się zmienna „swapped”, jej zadaniem jest obserwowanie, czy podczas iteracji pętli została wykonana jakakolwiek zamiana; jeśli nie ma zamiany, lista jest już posortowana i nic więcej nie trzeba robić. Przypisaliśmy jej na początku wartość „true” aby móc uruchomić pętlę, a następnie, już w pętli zmieniliśmy na „false”. Wartość „false” oznacza, że nie nastąpiła żadna zmiana, a wartość „true”, wręcz przeciwnie. Następnie mamy zagnieżdżoną pętlę „for”, która sprawdza czy pierwszy element listy jest większy od drugiego, jeśli jest to prawda, następuje zamiana i pętla wchodzi w kolejną iterację. Pętla działa dopóki elementy listy nie zostaną posortowane. Jeśli chcemy otrzymać listę uporządkowaną odwrotnie, wystarczy zmienić operator ‚>’ na ‚<‚ w instrukcji warunkowej. Na sam koniec zawartość naszej posortowanej listy zostanie wyświetlona na ekranie. Mam nadzieję, że przedstawiłem temat w zrozumiały i przystępny sposób, oraz, że będziesz potrafił samemu napisać taki program.  

Jedna odpowiedź do “1, 2, 5, 3… zaraz, co?-Czyli sortowanie w praktyce”

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *