Algorytmy sortowania – podstawy

1.Algorytm sortowania

Sposób uporządkowania elementów zbioru według ustalonego kryterium, np. rosnąco lub malejąco. Celem jest ustawienie danych w odpowiedniej kolejności.

2.Porządek rosnący

Ułożenie elementów od najmniejszego do największego, np. liczby od wartości najmniejszej do największej lub słowa alfabetycznie od A do Z.

3.Porządek malejący

Ułożenie elementów od największego do najmniejszego. To odwrotność porządku rosnącego.

4.Klucz sortowania

Cecha, według której porządkujemy dane. Dla liczb jest to wartość liczby, a dla rekordów może to być np. nazwisko, wiek lub cena.

5.Sortowanie bąbelkowe

Algorytm porównujący sąsiednie elementy i zamieniający je miejscami, gdy są w złej kolejności. Po kolejnych przebiegach największe elementy „wypływają” na koniec.

6.Sortowanie przez wybieranie

Algorytm, który w każdej rundzie wyszukuje najmniejszy element z nieuporządkowanej części i wstawia go na właściwe miejsce na początku.

7.Sortowanie przez wstawianie

Algorytm budujący uporządkowany fragment tablicy. Każdy kolejny element jest wstawiany w odpowiednie miejsce w już posortowanej części.

8.Porównanie elementów

Sprawdzenie, który z dwóch elementów jest większy, mniejszy albo czy są równe. To podstawowa operacja w wielu algorytmach sortowania.

9.Zamiana miejsc

Operacja polegająca na przestawieniu dwóch elementów w tablicy lub liście. W sortowaniu często wykonuje się ją po wykryciu złej kolejności.

10.Złożoność czasowa

Opisuje, jak liczba operacji algorytmu rośnie wraz z rozmiarem danych. Dla prostych metod sortowania często wynosi około $O(n^2)$, gdzie $n$ to liczba elementów.

11.Stabilność sortowania

Cecha algorytmu mówiąca, czy elementy o jednakowym kluczu zachowują swoją wcześniejszą kolejność. Ma znaczenie np. przy sortowaniu rekordów.

12.Tablica

Struktura danych przechowująca elementy w kolejnych pozycjach. W szkolnych przykładach algorytmy sortowania najczęściej działają właśnie na tablicach.