Algorytmy sortowania – przykłady, zastosowania i kod w Pascalu

Sortowanie to jeden z najważniejszych tematów w informatyce. Polega na uporządkowaniu danych według określonego kryterium, najczęściej rosnąco lub malejąco. W praktyce sortuje się liczby, teksty, daty, rekordy baz danych, a także elementy używane w algorytmach wyszukiwania i przetwarzania informacji.

W tym poradniku omawiamy najpopularniejsze algorytmy sortowania, pokazujemy ich działanie na przykładach i prezentujemy gotowe implementacje w Pascalu. Szczególną uwagę poświęcamy metodom najczęściej spotykanym w edukacji: bąbelkowej, przez wstawianie, przez wybieranie, szybkiej i przez scalanie.

Czym jest sortowanie i po co się je stosuje?

Sortowanie to proces ustawiania elementów w określonym porządku, np. od najmniejszego do największego. Dzięki uporządkowaniu łatwiej przeglądać dane, wyszukiwać informacje i wykonywać kolejne operacje na zbiorze.

Najczęstsze zastosowania sortowania to:

• porządkowanie wyników wyszukiwania,
• sortowanie list produktów po cenie,
• układanie kontaktów alfabetycznie,
• przygotowanie danych do szybszego wyszukiwania,
• porządkowanie rekordów w bazach danych,
• tworzenie rankingów i zestawień.

W praktyce algorytm sortowania wybiera się w zależności od wielkości danych, ich początkowego uporządkowania, wymagań pamięciowych oraz tego, czy ważna jest stabilność sortowania.

Najważniejsze pojęcia

Przed przejściem do konkretnych algorytmów warto znać kilka podstawowych terminów:

• stabilność sortowania – jeśli dwa elementy mają taką samą wartość, stabilny algorytm zachowuje ich pierwotną kolejność;
• złożoność czasowa – informuje, jak rośnie czas działania algorytmu wraz z liczbą danych;
• złożoność pamięciowa – określa, ile dodatkowej pamięci potrzebuje algorytm;
• rekurencja – technika, w której funkcja wywołuje samą siebie (częsta w quick sort i merge sort).

1. Sortowanie bąbelkowe

Sortowanie bąbelkowe (bubble sort) jest jednym z najprostszych algorytmów. Działa przez wielokrotne porównywanie dwóch sąsiadujących elementów i zamianę miejscami, jeśli są w złej kolejności. Po każdym przebiegu największy element „wypływa” na koniec tablicy.

Jak działa bubble sort?

Wykonujemy kolejne przebiegi po tablicy. W każdym kroku porównujemy sąsiadujące elementy i, gdy lewy jest większy od prawego, zamieniamy je miejscami. Po pierwszym przebiegu największa liczba jest na końcu, po drugim – druga największa itd.

Przykład

Dla tablicy: [5, 1, 4, 2, 8]

Przebieg 1 (krok po kroku):

• 5 i 1 → zamiana → [1, 5, 4, 2, 8],
• 5 i 4 → zamiana → [1, 4, 5, 2, 8],
• 5 i 2 → zamiana → [1, 4, 2, 5, 8],
• 5 i 8 → brak zamiany.

Po pierwszym przebiegu największy element jest już na końcu tablicy.

Zastosowanie

Bubble sort jest prosty do zrozumienia i świetny dydaktycznie. W praktyce jest rzadko używany do dużych zbiorów, bo działa wolniej niż nowocześniejsze metody.

Złożoność

Podsumowanie złożoności czasowej dla bubble sort:

• najlepszy przypadek: O(n) przy wersji z kontrolą zamian,
• średni przypadek: O(n^2),
• najgorszy przypadek: O(n^2).

Kod w Pascalu

Poniżej przykładowa implementacja w Pascalu:

program BubbleSort;
var
A: array[1..100] of Integer;
n, i, j, temp: Integer;
begin
ReadLn(n);
for i := 1 to n do Read(A[i]);

for i := 1 to n - 1 do
for j := 1 to n - i do
if A[j] > A[j + 1] then
begin
temp := A[j];
A[j] := A[j + 1];
A[j + 1] := temp;
end;

for i := 1 to n do Write(A[i], ' ');
end.

2. Sortowanie przez wstawianie

Insertion sort buduje posortowaną część tablicy element po elemencie. Każdy nowy element jest wstawiany we właściwe miejsce w już uporządkowanym fragmencie.

Jak działa insertion sort?

Algorytm zaczyna od drugiego elementu. Bierze go jako klucz, porównuje z elementami po lewej i przesuwa większe w prawo, aż znajdzie odpowiednie miejsce dla klucza.

Przykład

Tablica: [7, 3, 5, 2]

• start: [7] | 3, 5, 2,
• wstawiamy 3 → [3, 7] | 5, 2,
• wstawiamy 5 → [3, 5, 7] | 2,
• wstawiamy 2 → [2, 3, 5, 7].

Zastosowanie

Dla małych zbiorów lub danych prawie posortowanych insertion sort bywa bardzo efektywny i często służy jako składnik bardziej złożonych algorytmów.

Złożoność

Podsumowanie złożoności czasowej dla insertion sort:

• najlepszy przypadek: O(n),
• średni przypadek: O(n^2),
• najgorszy przypadek: O(n^2).

Kod w Pascalu

Poniżej przykładowa implementacja w Pascalu:

program InsertionSort;
var
A: array[1..100] of Integer;
n, i, j, key: Integer;
begin
ReadLn(n);
for i := 1 to n do Read(A[i]);

for i := 2 to n do
begin
key := A[i];
j := i - 1;
while (j >= 1) and (A[j] > key) do
begin
A[j + 1] := A[j];
Dec(j);
end;
A[j + 1] := key;
end;

for i := 1 to n do Write(A[i], ' ');
end.

3. Sortowanie przez wybieranie

Selection sort wybiera najmniejszy element z nieposortowanej części tablicy i umieszcza go na początku tej części.

Jak działa selection sort?

W każdym kroku przeglądamy resztę tablicy, znajdujemy minimum i zamieniamy je z pierwszym elementem nieposortowanego fragmentu.

Przykład

Tablica: [64, 25, 12, 22, 11]

• minimum w całej tablicy to 11 → [11, 25, 12, 22, 64],
• minimum z pozostałych to 12 → [11, 12, 25, 22, 64],
• minimum z pozostałych to 22 → [11, 12, 22, 25, 64],
• minimum z pozostałych to 25 → [11, 12, 22, 25, 64].

Zastosowanie

Selection sort jest prosty i wykonuje mało zamian, ale ma kwadratową złożoność czasową, więc stosuje się go głównie w nauczaniu.

Złożoność

Podsumowanie złożoności czasowej dla selection sort:

• najlepszy przypadek: O(n^2),
• średni przypadek: O(n^2),
• najgorszy przypadek: O(n^2).

Kod w Pascalu

Poniżej przykładowa implementacja w Pascalu:

program SelectionSort;
var
A: array[1..100] of Integer;
n, i, j, minIndex, temp: Integer;
begin
ReadLn(n);
for i := 1 to n do Read(A[i]);

for i := 1 to n - 1 do
begin
minIndex := i;
for j := i + 1 to n do
if A[j] < A[minIndex] then
minIndex := j;

temp := A[i];
A[i] := A[minIndex];
A[minIndex] := temp;
end;

for i := 1 to n do Write(A[i], ' ');
end.

4. Sortowanie szybkie

Quick sort to jeden z najszybszych i najczęściej używanych algorytmów. Działa metodą „dziel i zwyciężaj”: wybiera element osiowy (pivot), dzieli tablicę na dwie części i rekurencyjnie sortuje obie strony.

Jak działa quick sort?

Wybieramy pivot (np. pierwszy, ostatni, środkowy lub losowy element). Elementy mniejsze trafiają na lewo od pivota, a większe na prawo, po czym sortujemy rekurencyjnie powstałe podtablice.

Przykład

Tablica: [9, 3, 7, 1, 8, 2, 5]

Jeśli pivotem jest 5, podział wygląda tak:

• lewa strona: [3, 1, 2],
• pivot: [5],
• prawa strona: [9, 7, 8].

Następnie każda z tych części jest sortowana osobno.

Zastosowanie

Quick sort jest bardzo popularny w praktyce, ponieważ w średnim przypadku działa wyjątkowo szybko. Jest dobrym wyborem dla dużych zbiorów danych, choć w najgorszym przypadku może działać wolniej niż merge sort.

Złożoność

Podsumowanie złożoności czasowej dla quick sort:

• najlepszy przypadek: O(n log n),
• średni przypadek: O(n log n),
• najgorszy przypadek: O(n^2).

Kod w Pascalu

Poniżej przykładowa implementacja w Pascalu:

program QuickSort;
var
A: array[1..100] of Integer;

procedure Swap(var x, y: Integer);
var
t: Integer;
begin
t := x; x := y; y := t;
end;

procedure QuickSort(L, R: Integer);
var
i, j, pivot: Integer;
begin
i := L; j := R;
pivot := A[(L + R) div 2];
repeat
while A[i] < pivot do Inc(i);
while A[j] > pivot do Dec(j);
if i <= j then
begin
Swap(A[i], A[j]);
Inc(i); Dec(j);
end;
until i > j;

if L < j then QuickSort(L, j);
if i < R then QuickSort(i, R);
end;

var
n, i: Integer;
begin
ReadLn(n);
for i := 1 to n do Read(A[i]);
QuickSort(1, n);
for i := 1 to n do Write(A[i], ' ');
end.

5. Sortowanie przez scalanie

Merge sort także korzysta z zasady „dziel i zwyciężaj”. Tablica jest dzielona na połowy, każda połowa sortowana osobno, a potem obie części są scalane w jeden uporządkowany ciąg.

Jak działa merge sort?

Algorytm dzieli tablicę aż do jednoelementowych fragmentów. Następnie scala je, tak by w każdym kroku powstawała posortowana część większego zbioru.

Zastosowanie

Merge sort zapewnia przewidywalną złożoność O(n log n) i jest stabilny, dlatego sprawdza się przy dużych danych i tam, gdzie stabilność ma znaczenie.

Złożoność

Podsumowanie złożoności czasowej dla merge sort:

• najlepszy przypadek: O(n log n),
• średni przypadek: O(n log n),
• najgorszy przypadek: O(n log n).

Kod w Pascalu

Poniżej przykładowa implementacja w Pascalu:

program MergeSort;
var
A, Temp: array[1..100] of Integer;

procedure Merge(L, M, R: Integer);
var
i, j, k: Integer;
begin
i := L; j := M + 1; k := L;

while (i <= M) and (j <= R) do
begin
if A[i] <= A[j] then
begin
Temp[k] := A[i]; Inc(i);
end
else
begin
Temp[k] := A[j]; Inc(j);
end;
Inc(k);
end;

while i <= M do
begin
Temp[k] := A[i]; Inc(i); Inc(k);
end;

while j <= R do
begin
Temp[k] := A[j]; Inc(j); Inc(k);
end;

for i := L to R do A[i] := Temp[i];
end;

procedure MergeSort(L, R: Integer);
var
M: Integer;
begin
if L < R then
begin
M := (L + R) div 2;
MergeSort(L, M);
MergeSort(M + 1, R);
Merge(L, M, R);
end;
end;

var
n, i: Integer;
begin
ReadLn(n);
for i := 1 to n do Read(A[i]);
MergeSort(1, n);
for i := 1 to n do Write(A[i], ' ');
end.

Porównanie najpopularniejszych algorytmów

Poniżej zestawienie najważniejszych cech i złożoności poszczególnych metod:

Algorytm	Najlepszy przypadek	Średni przypadek	Najgorszy przypadek	Pamięć dodatkowa	Stabilność
Bubble sort	O(n)	O(n^2)	O(n^2)	O(1)	tak
Insertion sort	O(n)	O(n^2)	O(n^2)	O(1)	tak
Selection sort	O(n^2)	O(n^2)	O(n^2)	O(1)	zwykle nie
Quick sort	O(n log n)	O(n log n)	O(n^2)	O(log n)	zwykle nie
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)	tak

Dane w tabeli odpowiadają standardowym omówieniom algorytmów sortowania w materiałach edukacyjnych.

Który algorytm wybrać?

W praktyce wybór zależy od sytuacji:

• do nauki podstaw najlepiej nadaje się bubble sort lub insertion sort;
• dla małych lub prawie posortowanych danych często wystarcza insertion sort;
• gdy zależy nam na prostocie i małej liczbie zamian, można użyć selection sort;
• dla dużych danych i dobrego średniego czasu działania często wybiera się quick sort;
• gdy potrzebna jest stabilność i przewidywalny czas działania, dobrym wyborem jest merge sort.

Jak testować kod w Pascalu?

Jeśli publikujesz poradnik na stronie internetowej, warto dodać krótką instrukcję uruchamiania przykładów:

1. Skopiuj wybrany kod do środowiska Pascal, np. Free Pascal lub Turbo Pascal.
2. Wprowadź dane wejściowe zgodnie z założeniem programu: najpierw liczbę elementów, potem same elementy tablicy.
3. Uruchom program i sprawdź wynik.
4. Porównaj wynik z oczekiwanym uporządkowaniem rosnącym.

Przykładowe dane wejściowe (liczba elementów i wartości):

5
9 3 7 1 8

Wynik po sortowaniu rosnącym powinien wyglądać tak:

1 3 7 8 9

Najczęstsze błędy przy implementacji

Podczas pisania algorytmów sortowania w Pascalu początkujący często popełniają podobne błędy:

• używają błędnych granic pętli,
• mylą indeksowanie od 0 i od 1,
• zapominają o warunku końcowym w rekurencji,
• źle implementują zamianę elementów,
• nie uwzględniają, że tablica może być już posortowana lub odwrotnie – posortowana w odwrotnej kolejności.

Gdzie sortowanie jest szczególnie ważne w internecie?

Na stronie poświęconej internetowi temat sortowania łatwo powiązać z realnymi zastosowaniami:

• listy artykułów i wpisów blogowych według daty,
• katalogi produktów według ceny,
• wyniki wyszukiwania według trafności,
• komentarze według popularności,
• logi systemowe i dane analityczne,
• tabele rankingowe i statystyki.

To pokazuje, że sortowanie nie jest tylko szkolnym ćwiczeniem, ale jednym z fundamentów działania nowoczesnych serwisów internetowych.