Sortowanie przez wstawianie- InsertSort

Metoda sortowania przez wstawianie używana jest najczęściej przez osoby grające w karty. Polega ona na założeniu, że w danym momencie w ręku trzymamy jednocześnie karty posortowane i nieposortowane. W celu realizacji zadania porządkowania należy pobrać ze sterty kart do posortowania kartę i wstawienia jej na odpowiednie miejsce w obszarze kart posortowanych.

Dane: n - liczba elementów w sortowanym zbiorze, d[ ] – zbiór, który będzie sortowany.
Wynik: Uporządkowany zbiór d[ ]
Algorytm: porządkowanie przez wstawianie– InsertSort

Krok 1. Dla i = 1, 2, ..., n – 1 wykonaj kroki 2 … 4, a następnie zakończ algorytm
Krok 2. x ← d[j];  i ← j + 1
Krok 3. Dopóki ( i ≤ n )  ∧  ( x > d[i] ): wykonuj d[i - 1] ← d[i];  i ← i + 1
Krok 4. d[i - 1] ← x


for(j = n - 2; j >= 0; j--)
{
x = d[j];
i = j + 1;
while((i < n) && (x > d[i]))
{
d[i - 1] = d[i];
i++;
}
d[i - 1] = x;
}


Wnioski:

- algorytm ten jest bardzo kosztownym algorytmem (klasa złożoności obliczeniowej – O(N2)
- nie nadaje się do porządkowania dużych zbiorów
- postać algorytmu przejrzysta
- algorytm krótki

Sortowanie przez wybór - SelectionSort

Metoda porządkowania przez wybór polega na porządkowaniu zbioru w sposób rosnący tzn. element najmniejszy powinien znaleźć się na pierwszej pozycji. Metoda ta polega na znalezieniu w zbiorze elementu najmniejszego i wymienieniu go z elementem na czytanej pozycji zbioru aż do całkowitego jego uporządkowania.

Dane: n - liczba elementów zbioru, d[ ] – zbiór sortowany. Elementy zbioru mają indeksy od 1 do n.
Wynik: Uporządkowany zbiór d[ ]
Algorytm: porządkowanie przez wybór – Selection Sort
Idea: najmniejszy wśród nieuporządkowanych daj na początek

Krok 1. Dla j = 1, 2, ..., n - 1: wykonuj Krok 1 ...Krok 4, a następnie zakończ algorytm
Krok 2. pmin ← j
Krok 3. Dla i = j + 1,  j + 2, ..., n: jeśli d[i] < d[pmin], to pmin ← i
Krok 4. d[j] ↔ d[pmin]


for(j = 0; j < N - 1; j++)
{
pmin = j;
for(i = j + 1; i < N; i++)
{
if(d[i] < d[pmin]) pmin = i;
}
swap(d[pmin], d[j]);
}

Wnioski:

- algorytm ten jest bardzo kosztownym algorytmem (klasa złożoności obliczeniowej – O(N2)
- nie nadaje się do porządkowania dużych zbiorów
- wykonuje taką samą ilość operacji porównania dla zbiorów częściowo uporządkowanych jak i dla zbiorów nieuporządkowanych
- algorytm przejrzysty, zwięzły

Algorytm sortowania bąbelkowego

Metoda porządkowania bąbelkowego swoją nazwę wzięła od pęcherzyków powietrza ulatujących w górę tuby wypełnionej wodą. Metoda ta polega na analizowaniu dwóch sąsiadujących ze sobą elementów, jeśli nie są one uporządkowane następuje ich zamiana.

Dane: n - liczba elementów zbioru, d[ ] – zbiór sortowany. Elementy zbioru mają indeksy od 1 do n.
Wynik: Uporządkowany zbiór d[ ]
Algorytm: porządkowanie przez wybór – Selection Sort
Idea: najmniejszy wśród nieuporządkowanych daj na początek

Krok 1. Dla j = 1, 2, ..., n - 1: wykonuj Krok 1 ...Krok 4, a następnie zakończ algorytm
Krok 2. pmin ← j
Krok 3. Dla i = j + 1,  j + 2, ..., n: jeśli d[i] < d[pmin], to pmin ← i
Krok 4. d[j] ↔ d[pmin]



for(j = N - 1; j > 0; j--)
{
p = 1;
for(i = 0; i < j; i++)
{
if(d[i] > d[i + 1])
{
swap(d[i],
d[i + 1]); p = 0;
}
}
if(p) break;
}


Wnioski:

- algorytm ten jest bardzo kosztownym algorytmem (klasa złożoności obliczeniowej – O(N2)
- bardzo prosta i zrozumiała struktura zapisu
- dość często zdarzają się puste przebiegi (brak wykonania wymiany jeżeli elementu są uporządkowane)

Szybkie sortowanie - quicksort

Rekurencja - jest modą programowania polegająca na wywoływaniu funkcji programu przez samą siebie .

Algorytm ten jak sama nazwa wskazuje, poprzez odpowiednią dekompozycję osiągnął znaczny zysk w szybkości porządkowania zbiorów. Metoda szybkiego sortowania podzielona została na dwie części:

-część służąca do właściwego sortowania polegająca na wywoływaniu samej siebie
-część odpowiadająca za rozdzielenie elementów tablicy wartości osiowej podziału

void qsort(int* d, int left, int right)
{
if (left < right)
{
int m = left;
for(int i = left+1; i <= right; i++)
if (d[i] < d[left]) swap(d[++m],d[i]);
swap(d[left], d[m]);
qsort(d, left, m-1);
qsort(d, m+1, right);
}
}


Wnioski:

- dzięki zastosowaniu metody programowania „dziel i zwyciężaj” algorytm w optymalnie krótkim czasie realizuje zadanie porządkowania zbiory (klasa złożoności obliczeniowej – O(N log N)