Wybieranie, sortowanie
Temat: Wybieranie, sortowanie
- na czym polega sortowanie przez wybieranie,
- jak rozbić algorytm sortowania na procedury,
- jak zrealizować algorytm porządkowania bąbelkowego Scratchu.
Sortowanie bąbelkowe
Sortowanie bąbelkowe jest jednym z najprostszych w implementacji algorytmów porządkujących dane.
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):
Element pierwszy i drugi
Element drugi i trzeci
…
Element (n-1)-wszy i n-ty
Każdy element jest tak długo przesuwany w ciągu, aż napotkany zostanie element większy od niego, wtedy w następnych krokach przesuwany jest ten większy element.
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.
Jeżeli dane wejściowe są uporządkowane, to algorytm wykonuje tylko jeden przebieg (nie jest wykonywana żadna zamiana).
Projekt sortowania bąbelkowego w Scratch:
Skrypt zielonej flagi:
