Sortowanie – przypomnienie

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.

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.

Algorytmy stabilne i niestabilne

Algorytmy stabilne to takie, w których elementy o takiej samej wartości nie zmienią pozycji względem siebie, natomiast algorytmy niestabilne mogą zmienić ich kolejność. Jeżeli algorytm niestabilny napotka dwa elementy o wartości 7, nie musi zamieniać ich miejscami, aby uzyskać posortowany zbiór. W zależności od implementacji, może to jednak zrobić.

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.

Algorytm w pseudokodzie

Zanim przejdziemy do przełożenia opisanego algorytmu na  język C++, przedstawimy go w postaci pseudokodu. Załóżmy, że sortujemy zbiór liczb w porządku rosnącym.

Użyjemy przy tym mechanizmu pętli zagnieżdżonychzagnieżdżona pętlapętli zagnieżdżonych. Pierwsza z nich, zewnętrzna, będzie odpowiadać za wskazywanie kolejnych pozycji w tablicy. Zapełnimy je liczbami o coraz większych wartościach.

O tym, która liczba powinna znaleźć się w miejscu wskazanym przez zewnętrzną pętlę, poinformuje nas pętla wewnętrzna. Dzięki niej wyszukamy najmniejsze liczby w nieposortowanej części tablicy.

Zaczniemy od zdefiniowania zmiennych. Będzie nam potrzebna tablica zawierająca elementy do posortowania:

zbior[] = tablica o rozmiarze n

Następnie tworzymy pierwszą, zewnętrzną pętlę. Wskaże ona kolejne elementy tablicy oprócz ostatniego. Jeżeli poprzednie liczby zostaną ułożone we właściwym porządku, to ostatnia na pewno znajdzie się tam, gdzie być powinna.

zbior[] = tablica o rozmiarze n

dla i = 0, 1, ..., długość(zbior) - 1 wykonuj
   

Dla każdej wartości i należy przeszukać nieposortowaną część tablicy i znaleźć element, który powinien zostać umieszczony w miejscu wskazywanym przez zmienną i. W pierwszym cyklu będzie to pierwsze miejsce tablicy, w drugim drugie itd.

Zdefiniujemy teraz zmienną tymczasową  najmniejszyIndeks. Ma ona wskazywać najmniejszy odnaleziony element; wstępnie przypiszemy jej wartość i. Zrobimy tak, ponieważ najmniejsza liczba od razu może znajdować się w miejscu wskazywanym przez zmienną i (w przypadku omówionej wcześniej przykładowej tablicy liczba 5 była tam, gdzie powinna zostać umieszczona).

Pora uruchomić pętlę wewnętrzną. Posłuży ona do odnalezienia najmniejszej liczby w nieposortowanej jeszcze części tablicy. Poszukiwania zaczną się od elementu o indeksie i + 1:

zbior[] = tablica o rozmiarze n

dla i = 0, 1, ..., długość(zbior) - 1 wykonuj
	najmniejszyIndeks = i
    
	dla j = i + 1, i + 2, ..., długość(zbior) wykonuj
   

Aby znaleźć najmniejszy element, musimy porównać każdy obiekt w nieposortowanej części tablicy z najmniejszą odszukaną dotychczas liczbą:

zbior[] = tablica o rozmiarze n

dla i = 0, 1, ..., długość(zbior) - 1 wykonuj
	najmniejszyIndeks = i
    
	dla j = i + 1, i + 2, ..., długość(zbior) - 1 wykonuj
		jeżeli zbior[j] < zbior[najmniejszyIndeks] to
			najmniejszyIndeks = j

Jeżeli okaże się, że sprawdzany właśnie element jest jeszcze mniejszy, uznajemy go za najmniejszą obecnie liczbę. Przenosimy ją na miejsce wskazane przez zmienną i. Oto gotowy algorytm zapisany w pseudokodzie:

zbior[] = tablica o rozmiarze n

dla i = 0, 1, ..., długość(zbior) - 1 wykonuj
	najmniejszyIndeks = i
    
	dla j = i + 1, i + 2, ..., długość(zbior) - 1 wykonuj
		jeżeli zbior[j] < zbior[najmniejszyIndeks] to
			najmniejszyIndeks = j
    
	zamienMiejscami(zbior[i], zbior[najmniejszyIndeks])

Gdybyśmy chcieli natomiast posortować zbiór w porządku malejącym, należałoby wyszukiwać największe liczby w nieposortowanej części zbioru.

Słownik