Algorytmy sortowania

Poniższy materiał to część cyklu „Algorytmy dla uczniów”, czyli algorytmy dla początkujących. Zapraszam do zapoznania się z całością cyklu.

ALGORYTMY SORTOWANIA (PORZĄDKOWANIA)

Sortowanie (porządkowanie) – proces ustawienia zbioru obiektów w określonym porządku

Metody sortowania:

przez zamianę (sortowanie bąbelkowe)
przez wybieranie
przez wstawianie

ALGORYTM SORTOWANIA BĄBELKOWEGO

Jedną z popularnych metod sortowania jest sortowanie przez prostą zamianę (sortowanie bąbelkowe). W metodzie tej porównujemy sąsiednie elementy. W celu uporządkowania elementów od najmniejszego do największego, jeśli drugi element jest mniejszy od poprzedniego, to zamieniamy go miejscami. Następnie element, który stał się drugim, porównujemy z trzecim i przestawiamy, jeśli jest mniejszy itd.

Sortowanie bąbelkowe polega na porównywaniu parami kolejnych liczb i przestawianiu, jeśli są ustawione w niewłaściwej kolejności.

Zadanie. Sortowanie bąbelkowe

Uporządkuj liczby: 7 6 1 9 5 w kolejności od najmniejszej do największej.

Przebieg pierwszy:
7 6 1 9 5    – porównujemy 7 i 6 ( przestawiamy, bo 6 < 7)
6 7 1 9 5    – porównujemy 7 i 1 ( przestawiamy, bo 1 < 7)
6 1 7 9 5    – porównujemy 7 i 9 ( nie przestawiamy, bo 10 > 7)
6 1 7 9 5    – porównujemy 9 i 5 ( przestawiamy, bo 5 < 10)
6 1 7 5 9         – 9 na właściwym miejscu

Przebieg drugi:
6 1 7 5 9    – porównujemy 6 i 1 ( przestawiamy, bo 1 < 6)
1 6 7 5 9    – porównujemy 6 i 7 ( nie przestawiamy, bo 7 > 6)
1 6 7 5 9   – porównujemy 7 i 5 ( przestawiamy, bo 5 < 7)
1 6 7 5 9    – porównujemy 7 i 5 ( przestawiamy, bo 5 < 7)
1 6 5 7 9         – 7 i 9 na właściwym miejscu

Przebieg trzeci:
1 6 5 7 9    – porównujemy 1 i 6 ( nie przestawiamy, bo 6 > 1)
1 6 5 7 9    – porównujemy 6 i 5 ( przestawiamy, bo 5 < 6)
1 5 6 7 9         – 6, 7, 9 na właściwym miejscu

Przebieg czwarty:
1 5 6 7 9 – porównujemy 1 i 5 nie przestawiamy, bo 5 > 1
…

Spójrz wyżej. Czy ciąg po pierwszym przebiegu jest już uporządkowany? Ponieważ nie jest, należy wykonywać kolejne przebiegi. Powinniśmy to robić, aż liczby zostaną uporządkowane, a więc do momentu, aż nie trzeba będzie przestawiać miejscami żadnego elementu.

w czwartym przebiegu nie są zamieniane żadne elementy, czyli nie ma potrzeby dalszego porównywania. Można zakończyć algorytm, liczby są uporządkowane w żądanej kolejności

Zadanie do samodzielnego wykonania
Ułóż 5 książek w przypadkowej kolejności na stole. Uporządkuj je według wysokości (od najwyższej do najniższej), stosując algorytm sortowania bąbelkowego.

ALGORYTM SORTOWANIA PRZEZ WYBIERANIE

Jeśli chcemy uporządkować elementy jakiegoś zbioru np. w kolejności od najmniejszego do największego to możemy wybrać najmniejszy element i umieścić go na początku. Następnie wybieramy najmniejszy element z pozostałego zbioru i umieszczamy go po poprzednio wybranym elemencie (czyli jako drugi) itd.Taka metoda porządkowania nazywa się sortowaniem przez wybór. Polega na wyszukaniu największej liczby, przestawieniu jej na początek ciągu elementów (czyli zamienieniu jej z pierwszą liczbą ciągu) i takim samym postępowaniu dalszym z pominięciem pierwszego elementu.

Zadanie. Sortowanie bąbelkowe

Uporządkuj liczby: 7 6 1 9 5 w kolejności od najmniejszej do największej.

7 6 1 9 5    – 1 na pierwszą pozycję, 7 w miejsce 1
1 6 7 9 5    – 5 na drugą pozycję, 6 w miejsce 5
1 5 7 9 6    – 6 na trzecią pozycję, 7 w miejsce 6
1 5 6 9 7    – 7 na czwartą pozycję, 9 w miejsce 7
1 5 6 7 9    – 9 na właściwym miejscu (piątym)

Zadanie do samodzielnego wykonania
Wykonaj zadanie z ćwiczenia drugiego, stosując algorytm sortowania przez wstawianie.

ALGORYTM SORTOWANIA PRZEZ WSTAWIANIE

Metoda porządkowania przez wybór polega na wstawianiu elementu we właściwe miejsce, jest ona powszechnie stosowana przez osoby grające w karty.

7| 6 1 9 5
6 7| 1 9 5
1 6 7| 9 5
1 6 7 9| 5
1 6 7 5 9|

Na schemacie kreska oddziela posortowaną lewą część liczb od nieposortowanej prawej części.

Jeśli pragniemy ustawić liczby w kolejności od najmniejszego do największego, to bierzemy element drugi i jeśli jest on mniejszy od pierwszego to wstawiamy przed nim. Następnie bierzemy element trzeci i wstawiamy również w odpowiednie miejsce, a więc jeśli jest mniejszy od pierwszego to przed pierwszy, jeśli mniejszy od drugiego to przed drugi.