Sortowanie

Sortowaniem nazywamy porządkowanie elementów w pewien ustalony sposób.

Istnieje wiele metod sortowania, różniących się zarówno sposobem działania, jak i efektywnością. W związku z tym algorytmy sortujące, w zależności od swojej złożoności algorytmicznej, różnią się czasem rozwiązywania danego problemu. W tym e‑materiale poznamy jeden z najprostszych algorytmów sortowania – przez wybieranie (wybór). W ten sposób sortować możemy np. wydania czasopism (chronologicznie), książki (alfabetycznie) etc.

Do czego służy sortowanie?

Sortowanie to inaczej porządkowanie danych uwzględniające jakąś ich cechę. Jeżeli sortujemy liczby, taką cechą jest zazwyczaj ich wartość, więc sortujemy je rosnąco, nierosnąco, malejąco oraz niemalejąco. Sortować możemy nie tylko liczby, ale również litery czy ciągi znaków.

Sortowanie przez wybieranie

Metoda sortowania przez wybieranie w porządku rosnącym polega na znalezieniu najmniejszego elementu zbioru i umieszczeniu go na pierwszym miejscu. Obiekt, który się tam wcześniej znajdował, trafia na miejsce zajmowane dotychczas przez element o najmniejszej wartości klucza.

Następnie wśród pozostałych (jeszcze nieposortowanych) elementów znowu wyszukuje się ten o najmniejszej wartości klucza i umieszcza go na drugim miejscu (ponownie dokonując zamiany z dotychczasowym obiektem) itd.

W każdym cyklu zmniejsza się liczba nieposortowanych elementów. Opisane czynności wykonuje się aż do momentu, w którym pozostanie tylko jeden element w części nieposortowanej – na pewno wartość jego klucza jest największa w całym zbiorze.

Kiedy sortujemy tablicę malejąco, rozpoczynamy od znalezienia elementu największego. Zamieniamy go miejscami z elementem, który znajdował się na pierwszej pozycji.

Kolorem zielonym zaznaczono miejsce przeznaczone dla pierwszego elementu. Ponieważ sortujemy zbiór malejąco, powinna się tu znaleźć największa liczba.

R1Dm91lmIEDDk

Ilustracja przedstawia sześć okręgów z liczbami: 5, 2, 8, 1, 9, 4.
Zielonym kolorem zaznaczono okrąg z liczbą: 5

Jest nią zaznaczony kolorem czerwonym element o wartości 9. Zamieniamy go miejscami z będącą na pierwszej pozycji liczbą 5.

RzyLZ4eGpPJ3d

Ilustracja przedstawia sześć okręgów z liczbami: 5, 2, 8, 1, 9, 4.
Zielonym kolorem zaznaczono okrąg z liczbą: 5, a kolorem czerwonym z liczbą: 9.

Na razie umieściliśmy jeden element we właściwym miejscu. Elementy już posortowane oznaczymy barwą żółtą. Teraz musimy znaleźć obiekt o największej wartości klucza w nieposortowanej części i zamienić go miejscami z liczbą 2 (pole to ma obecnie barwę zieloną).

RogX1CwwaYTN3

Ilustracja przedstawia sześć okręgów z liczbami: 9, 2, 8, 1, 5, 4.
Zielonym kolorem zaznaczono okrąg z liczbą: 2, a kolorem żółtym z liczbą: 9.

Element o wartości 8 zamieniamy miejscami z liczbą 2. Rozpoczynamy szukanie wartości, która powinna znaleźć się na trzeciej pozycji.

R18pUWBg1i5g3

Ilustracja przedstawia sześć okręgów z liczbami: 9, 8, 2, 1, 5, 4.
Zielonym kolorem zaznaczono okrąg z liczbą: 2, a kolorem żółtym z liczbą: 9.
Czerwonym kolorem oznaczono okrąg z liczbą 8.

RdWVzeAuD84F6

Ilustracja przedstawia sześć okręgów z liczbami: 9, 8, 2, 1, 5, 4.
Zielonym kolorem zaznaczono okrąg z liczbą: 2, a kolorem żółtym z liczbami: 9 oraz 8.

Cały proces trwa aż do odnalezienia przedostatniego elementu. Ostatnia wartość na pewno jest najmniejsza:

RBsTRR4QHiZ4l

Ilustracja przedstawia sześć okręgów z liczbami: 9, 8, 5, 4, 2, 1.
Zielonym kolorem zaznaczono okrąg z liczbą: 1, a kolorem żółtym z liczbami: 9, 8, 5, 3, 2.

Sortowanie przez zliczanie

Algorytm sortowania przez zliczanie polega na zliczeniu wystąpień kluczykluczkluczy w danym zbiorzezbiórzbiorze. W przypadku tego typu sortowania domyślnie operujemy na samych liczbach, choć po dostosowaniu algorytmu możliwe jest również sortowanie znaków.

Za pomocą omawianego algorytmu nie można posortować liczb rzeczywistych. Wynika to z faktu, że pomiędzy dwiema dowolnymi liczbami całkowitymi występuje nieskończenie wiele liczb rzeczywistych.

Warto również podkreślić, że algorytm sortowania przez zliczanie może być używany dla zbiorów, w których znajdują się liczby ujemne.

Omówmy algorytm na przykładzie.

Załóżmy, że chcemy niemalejąco posortować następujący zbiór danych:

{ 2, 7, 5, 2, 3, 9, 1, 2, 1, 5, 1, 9, 4, 8, 7 }.

Jego największa wartość to $9$, a najmniejsza to $1$. Dla tego zbioru k (różnica między wartością maksymalną a minimalną powiększoną o $1$) wynosi 9 - 1 + 1 = 9, zatem k = 9.

Tworzymy zatem dziewięcioelementową tablicę pomocniczą, którą wypełnimy zerami – dla każdej wartości w zbiorze przygotujemy licznik, a jego wartość ustawimy na $0$.

Dla czytelności przedstawimy to w formie tabeli.

Sprawdzamy elementy zbioru. W następnym kroku zliczamy ich wystąpienia w odpowiednich licznikach, np.: zliczenie elementu o wartości $1$ powoduje zwiększenie o $1$ wartości licznika elementu o indeksie $0$, a zliczenie elementu o wartości $2$ powoduje zwiększenie o $1$ wartości licznika elementu o indeksie $1$.

W poszczególnych licznikach znajdują się liczby wystąpień każdej wartości.

W zbiorze znajdują się trzy elementy o wartości $1$:

{ 2, 7, 5, 2, 3, 9, 1, 2, 1, 5, 1, 9, 4, 8, 7 }

W kolumnie licznik wpisujemy zatem wartość $3$ dla wiersza, w którym zliczamy liczbę wystąpień elementu zbioru o wartości $1$. Podobnie postępujemy w przypadku pozostałych elementów zbioru.

Dla podanego przykładu tabela zliczeń wygląda następująco:

W następnym kroku, zaczynając od drugiego licznika, sumujemy zawartość danego licznika oraz jego poprzednika. Dzięki tej operacji dokładnie wiemy, gdzie w tablicy wynikowej umieścić każdy z elementów tablicy wejściowej.

Gdy zliczamy wystąpienia poszczególnych liczb w tablicy wejściowej, otrzymujemy tablicę, która mówi nam, ile razy występuje każda liczba. Jednak aby posortować tablicę wejściową, potrzebujemy wiedzieć, gdzie dokładnie umieścić każdy element w tablicy wynikowej.

Sumując wartość licznika z jego poprzednikiem, przekształcamy tablicę pomocniczą w taki sposób, że każda wartość w tej tablicy będzie przechowywać informację, ile elementów o wartości mniejszej lub równej danej liczbie znajduje się w tablicy wejściowej.

W zaprezentowanej tabeli możemy zobaczyć, ile liczb mniejszych lub równych danej wartości (kolumna element zbioru) znajduje się w zbiorze (kolumna licznik).

Zatem w zbiorze wejściowym znajdują się trzy wartości równe $1$ lub mniejsze od $1$. Oznacza to, że w posortowanej tablicy liczby mniejsze niż $1$ lub równe $1$ zajmują trzy pierwsze miejsca (czyli indeksy od $0$ do $2$ włącznie). Wiedząc to, możemy umieścić wszystkie elementy o wartości $1$ na odpowiednich miejscach tablicy wynikowej.

Oto posortowany zbiór danych:

{ 1, 1, 1, 2, 2, 2, 3, 4, 5, 5, 7, 7, 8, 9, 9 }

Słownik