Szybkie porządki

Temat: Szybkie porządki

  1. najlepszy algorytm porządkowania

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).

Źródło: https://pl.wikipedia.org/wiki/Sortowanie_b%C4%85belkowe

Projekt sortowania bąbelkowego w Scratch:

Skrypt zielonej flagi: