Podręcznik

1. Elementarne algorytmy sortowania

Pierwszą grupą algorytmów, którą omówimy w tym rozdziale, są tzw. metody sortowania elementarnego. Są to proste, intuicyjne algorytmy sortujące, które choć nie należą do najbardziej wydajnych, odgrywają istotną rolę w nauce podstaw algorytmiki. Charakteryzują się łatwą implementacją i przejrzystą logiką działania, dzięki czemu często stanowią punkt wyjścia do zrozumienia bardziej zaawansowanych metod sortowania. Do sortowania elementarnego zalicza się:

• sortowanie przez wybieranie (ang. SelectionSort), 
• sortowanie przez wstawianie (ang. InsertionSort),
• sortowanie bąbelkowe (ang. BubbleSort).

Sortowanie przez wybieranie (ang. SelectionSort)

Sortowanie przez wybieranie, znane również jako SelectionSort, polega na wyszukiwaniu najmniejszego elementu z nieposortowanej części tablicy i zamianie go z pierwszym elementem tej części. Proces ten jest powtarzany dla kolejnych pozycji aż do momentu, gdy cała tablica zostanie uporządkowana. Choć liczba porównań pozostaje stała niezależnie od rozkładu danych, metoda ta nie wymaga dodatkowej pamięci i może być efektywna dla bardzo małych zbiorów danych.

Sortowanie przez wstawianie (ang. InsertionSort)

Sortowanie przez wstawianie, czyli InsertionSort, działa w sposób przypominający układanie kart w ręku podczas gry. Każdy kolejny element tablicy jest porównywany z elementami już posortowanymi i wstawiany w odpowiednie miejsce, przesuwając większe elementy w prawo. Metoda ta dobrze sprawdza się w przypadku prawie posortowanych danych, ponieważ w takim przypadku liczba przesunięć jest minimalna.

Sortowanie bąbelkowe (ang. BubbleSort)

Trzecią klasyczną metodą sortowania elementarnego jest sortowanie bąbelkowe, znane jako BubbleSort. Działa ono na zasadzie porównywania sąsiadujących ze sobą elementów i zamieniania ich miejscami, jeśli znajdują się w złej kolejności. W wyniku kolejnych przebiegów największe elementy „wypływają” na koniec tablicy, stąd nazwa bąbelkowe. Choć jest to najwolniejszy z opisywanych algorytmów, jego koncepcja jest bardzo łatwa do zrozumienia i często wykorzystywana w celach edukacyjnych.