Algorytm sortowania przez wstawianie połówkowe rozpoczynamy od podzielenia ciągu porównywanych elementów:

a1 , a2 , ..., an

na dwa ciągi:

a) wynikowy a1 , a2 , ..., ai−1 ,

b) źródłowy ai , ai + 1 , ..., an .

W ka dym kroku, począwszy od i = 2, 3, … , n, i – ty element ciągu źródłowego przenosimy do ciągu wynikowego wstawiając w odpowiednie miejsce (czyli w takie miejsce, aby wszystkie elementy ciągu wynikowego pozostawały ułożone w odpowiedniej kolejności od wartości najmniejszej do największej). Zauważmy,

e ciąg wynikowy, do którego należy wstawić nowy element, jest ju uporządkowany. W związku z tym możemy zastosować szybszą (ni w przypadku algorytmu sortowania przez proste wstawianie) metodę ustalania

miejsca wstawienia nowego elementu. Możemy zastosować metodę przeszukiwania połówkowego, w której próbkuje się ciąg wynikowy w środku i dzieli do dalej znowu na połowę, a nie znajdziemy miejsca w którym

należy wstawić nowy obiekt.

for (i=2; i<=n; i++)

{

Ustaw x = a[i];

Wstaw x w odpowiednim miejscu ciągu wynikowego (miejsce, w którym

należy wstawić x znajdujemy metodą przeszukiwania połówkowego).

}

Algorytm (w języku C++)

for (i=2; i<=n; i++)

{

x= a[i];

k= 1;

p= i - 1;

while (k <= p) {

// dzielenie całkowitoliczbowe – całkowita część z dzielenia

m = (k + p) / 2;

if (x < a[m])

p = m - 1;

else

k = m + 1;

};

for (j=i-1; j>=k; j--)

a[j+1] = a[j];

a[k] = x;

}

Pomysł Shella polegał na tym, że sortowany ciąg jest dzielony na podciągi, których elementy są odległe od siebie w sortowanym zbiorze o pewien odstęp h. Każdy z tych podzbiorów jest sortowany jakimś innym algorytmem; Shell używał sortowania przez wstawianie. Z każdym krokiem odstęp h jest zmniejszany, do czasu osiągnięcia wartości 1. Wraz ze zmianą h zmniejsza się liczba podciągów, lecz rośnie ich długość, jednak ciąg jest coraz bardziej uporządkowany.

Efektywność sortowania zależy w dużym stopniu od wybranych odległości. Odstępy powinny być dobierane tak, aby w skład podciągów wchodziły elementy z jak największej liczby podciągów z kroków wcześniejszych - aby porównywać jak najwięcej par elementów z tablicy wejściowej. Dlatego zaleca się unikania odległości będących wielokrotnością jakieś liczby (np. dla 2: [8,4,2,1], czy 3: [12,9,6,3,1]). Pierwotnie Shell proponował pierwszy odstęp równy połowie liczby elementów w sortowanym zbiorze, kolejne odstępy otrzymuje się dzieląc odstęp przez 2 (dzielenie całkowitoliczbowe).

void shell_sort_with_gap(int tab[], unsigned max, unsigned h) {

//Dla każdego n wewnątrz przedziału

//n jest indeksem wewnątrz każdego z przedziałów

for (unsigned n=0; n<h; n++)

for (unsigned i=n+h; i<max; i+=h)

for(int j=i-h; j>=0 && tab[j]>tab[j+h]; j-=h)

std::swap(tab[j+h],tab[j]);

}

void shell_sort(int tab[], unsigned max) {

//Szukanie początkowego "skoku" dla przedziału

unsigned h = 1;

while (h<=max)

h = h*3+1;

h /= 9;

//Sortujemy z coraz mniejszymi przedziałami dopóki są większe niż 0

while (h>0) {

shell_sort_with_gap(tab, max, h);

h /= 3;

}

}

Sortowanie przez zliczanie – metoda sortowania danych, która polega na sprawdzeniu ile wystąpień kluczy mniejszych od danego występuje w sortowanej tablicy.

Algorytm zakłada, że klucze elementów należą do skończonego zbioru (np. są to liczby całkowite z przedziału 0..100), co ogranicza możliwości jego zastosowania.

Istnieją dwie implementacje algorytmu:

prostsza – sortująca in situ (w miejscu), zakłada, że elementy o równych kluczach są nierozróżnialne, nie mogą zatem być to klucze danych (każdy z nich jest bowiem powiązany z przenoszoną wartością – zatem, mimo iż są one równe, muszą pozostawać rozróżnialne);

standardowa – gwarantuje stabilność i nie wymaga dodatkowego założenia. Potrzebuje natomiast O(n) więcej pamięci;

Przykładowa implementacja w języku C++:

const int k = 77; // elementami tablicy T są liczby całkowite z

// z przedziału 0..76

const int n = 1000;

int T[n]; // tablica zawierająca elementy do posortowania

int Tp[n]; // tablica zawierająca elementy posortowane

int TPom[k]; // zawiera liczbę elementów o danej wartości

int i; // zmienna pomocnicza

for(i = 0 ; i < k ; ++i)

TPom[i] = 0; // zerowanie tablicy

for(i = 0 ; i < n ; ++i)

++TPom[T[i]]; // po tych operacjach TPom[i] będzie zawierała

// liczbę wystąpień elementów o kluczach mniejszych od i

for(i = 1 ; i < k ; ++i)

TPom[i] += TPom[i-1]; // teraz TPom[i] zawiera pozycje w posortowanej

// tablicy ostatniego elementu o kluczu i

for(i = n-1 ; i >= 0 ; --i)

Tp[--TPom[T[i]]] = T[i]; // wstawienie elementu na odpowiednią pozycję

// i aktualizacja Tpom

Sortowanie pozycyjne (ang. radix sort) to algorytm sortowania porządkujący stabilnie ciągi wartości (liczb, słów) względem konkretnych cyfr, znaków itp, kolejno od najmniej znaczących do najbardziej znaczących pozycji. Złożoność obliczeniowa jest równa O(d(n + k)), gdzie k to liczba różnych cyfr, a d liczba cyfr w kluczach. Wymaga O(n + k) dodatkowej pamięci.

Przewagą sortowania pozycyjnego nad innymi metodami jest fakt, iż nie wykonuje ono żadnych operacji porównania na danych wejściowych. Załóżmy że mamy dużą liczbę bardzo długich liczb, bardzo do siebie podobnych – w tym sensie, że większość z nich ma takie same cyfry na początkowych pozycjach. Nie jest łatwo powiedzieć która jest większa, gdyż za każdym razem musimy porównać dużo cyfr zanim trafimy na różnicę. Czas porównania takich liczb jest zatem proporcjonalny do ich długości. Gdybyśmy do posortowania tych liczb zastosowali algorytm porównujący liczby, np. sortowanie szybkie, otrzymalibyśmy dla niego złożoność O(dnlogn) gdzie d to liczba cyfr w liczbach.

Algorytmy pozycyjne sprawdzają się także w roli algorytmów sortujących listy.

Implementacja w pseudo języku programowania:

tab[] – tablica ciagów (cyfr, liter itp.) gdzie pozycja 1 oznacza najbardziej znaczącą pozycje ciągu

d – długość ciągów

procedure RadixSort(tab[],d)

begin

for i:=d downto 1 do

posortuj stabilnie ciągi według i-tej pozycji;

end;

Przykład działania algorytmu sortowania pozycyjnego

^ oznacza aktualną pozycję.

523 472 523 266

266 523 349 349

783 --> 783 --> 266 --> 472

472 266 472 523

349 349 783 783

^ ^ ^ ^

Sortowanie kubełkowe (ang. bucket sort) – jeden z algorytmów sortowania. Jest on najczęściej stosowany, gdy liczby w zadanym przedziale są rozłożone jednostajnie, ma on wówczas złożoność Θ(n). W przypadku ogólnym pesymistyczna złożoność obliczeniowa tego algorytmu wynosi O(n²).

Sposób działania

1. Podziel zadany przedział liczb na n podprzedziałów (kubełków) o równej długości.

2. Przypisz liczby z sortowanej tablicy do odpowiednich kubełków.

3. Sortuj liczby w niepustych kubełkach.

4. Wypisz po kolei zawartość niepustych kubełków.

Zazwyczaj przyjmuje się, że sortowane liczby należą do przedziału od 0 do 1. Jeśli tak nie jest, to można podzielić każdą z nich, przez największą możliwą (jeśli znany jest przedział) lub wyznaczoną. Należy tu jednak zwrócić uwagę, że wyznaczanie największej możliwej liczby w tablicy m-elementowej ma złożoność obliczeniową O(m).

Pseudokod

function bucket-sort(array, n) is

buckets ← new array of n empty lists

for i = 0 to (length(array)-1) do

insert array[i] into buckets[msbits(array[i], k)]

for i = 0 to n - 1 do

next-sort(buckets[i])

return the concatenation of buckets[0], ..., buckets[n-1]

W informatyce sortowanie przez scalanie (ang. merge sort), to rekurencyjny algorytm sortowania danych, mający zastosowanie przy danych dostępnych sekwencyjnie (po kolei, jeden element na raz), na przykład w postaci listy jednokierunkowej (tj. łączonej jednostronnie) albo pliku sekwencyjnego.

Algorytm ten jest dobrym przykładem algorytmów typu Dziel i zwyciężaj (ang. divide and conquer), których ideą działania jest podział problemu na mniejsze części, których rozwiązanie jest już łatwiejsze.

Wyróżnić można trzy podstawowe kroki:

1. Podziel zestaw danych na dwie, równe części (w przypadku nieparzystej liczby wyrazów jedna część będzie o 1 wyraz dłuższa);

2. Zastosuj sortowanie przez scalanie dla każdej z nich oddzielnie, chyba że pozostał już tylko jeden element;

3. Połącz posortowane podciągi w jeden.

Procedura scalania dwóch ciągów A[1..n] i B[1..m] do ciągu C[1..m+n]:

1. Utwórz wskaźniki na początki ciągów A i B → i=1, j=1

2. Jeżeli ciąg A wyczerpany (i>n), dołącz pozostałe elementy ciągu B do C i zakończ pracę.

3. Jeżeli ciąg B wyczerpany (j>m), dołącz pozostałe elementy ciągu A do C i zakończ pracę.

4. Jeżeli A[i] ≤ B[j] dołącz A[i] do C i zwiększ i o jeden, w przeciwnym przypadku dołącz B[j] do C i zwiększ j o jeden

55. Powtarzaj od kroku 2 aż wszystkie wyrazy A i B trafią do C

const int N = 20; // Liczebność zbioru.

int d[N],p[N];

// Procedura sortująca

void MergeSort(int i_p, int i_k)

{

int i_s,i1,i2,i;

i_s = (i_p + i_k + 1) / 2;

if(i_s - i_p > 1) MergeSort(i_p, i_s - 1);

if(i_k - i_s > 0) MergeSort(i_s, i_k);

i1 = i_p; i2 = i_s;

for(i = i_p; i <= i_k; i++)

p[i] = ((i1 == i_s) || ((i2 <= i_k) && (d[i1] > d[i2]))) ? d[i2++] : d[i1++];

for(i = i_p; i <= i_k; i++) d[i] = p[i];

}

// Program główny

int main()

{

int i;

// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi a następnie wyświetlamy jej zawartość

srand((unsigned)time(NULL));

for(i = 0; i < N; i++) d[i] = rand() % 100;

for(i = 0; i < N; i++) cout << setw(4) << d[i];

cout << endl;

// Sortujemy

MergeSort(0,N-1);

// Wyświetlamy wynik sortowania

cout << "Po sortowaniu:\n\n";

for(i = 0; i < N; i++) cout << setw(4) << d[i];

system("PAUSE"); return 0;}

Sortowanie szybkie

Algorytm działa rekursywnie - wybierany jest pewien element tablicy, tzw. element osiowy, po czym na początek tablicy przenoszone są wszystkie elementy mniejsze od niego, na koniec wszystkie większe, a w powstałe między tymi obszarami puste miejsce trafia wybrany element. Potem sortuje się osobno początkową i końcową część tablicy. Rekursja kończy się, gdy kolejny fragment uzyskany z podziału zawiera pojedynczy element, jako że jednoelementowa podtablica nie wymaga sortowania.

const int N = 20; // Liczebność zbioru.

int d[N];

// Procedura sortowania szybkiego

void Sortuj_szybko(int lewy, int prawy)

{

int i,j,piwot;

i = (lewy + prawy) / 2;

piwot = d[i]; d[i] = d[prawy];

for(j = i = lewy; i < prawy; i++)

if(d[i] < piwot)

{

swap(d[i], d[j]);

j++;

}

d[prawy] = d[j]; d[j] = piwot;

if(lewy < j - 1) Sortuj_szybko(lewy, j - 1);

if(j + 1 < prawy) Sortuj_szybko(j + 1, prawy);

}

// Program główny

int main(void)

{

int i;

srand((unsigned)time(NULL));

// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi a następnie wyświetlamy jej zawartość

srand((unsigned)time(NULL));

for(i = 0; i < N; i++) d[i] = rand() % 100;

for(i = 0; i < N; i++) cout << setw(4) << d[i];

cout << endl;

// Sortujemy

Sortuj_szybko(0,N - 1);

// Wyświetlamy wynik sortowania

cout << "Po sortowaniu:\n\n";

for(i = 0; i < N; i++) cout << setw(4) << d[i];

cout << endl;

system("PAUSE"); return 0;

}