Podstawowe algorytmy
Na stronach tych omówione są najciekawsze algorytmy omawiane na wykładzie ze Wstępu do Informatyki na pierwszym roku studiów informatycznych na Wydziale PPT Pwr.
O sortowaniu przez scalanie nie ma mądrych cytatów w internecie
- nikt
Sortowanie przez scalanie
Rekurencyjny algorytm sortowania danych, stosujący metodę dziel i zwyciężaj. Odkrycie algorytmu przypisuje się Johnowi von Neumannowi.
Wyróżnić można trzy podstawowe kroki.
- Podziel zestaw danych na dwie równe części,
- Zastosuj sortowanie przez scalanie dla każdej z nich oddzielnie, chyba że pozostał już tylko jeden element,
- Połącz posortowane podciągi w jeden.
Szczególnie jest przydatny zwłaszcza przy danych dostępnych sekwencyjnie (po kolei, jeden element naraz), na przykład w postaci listy jednokierunkowej (tj. łączonej jednostronnie) albo pliku sekwencyjnego.
Złożoność obliczeniowa
- Pierwszy krok (podział) trwa zawsze stały czas, niezależnie od rozmiaru tablicy - $ \theta ( 1 ) $
- Drugi krok (scalanie podtablic) trwa logarytmicznie długo w stosunku do rozmiaru tablicy - $ \theta( \log( n ) ) $
- Ostatni krok trwa liniowo długo w stosunku do rozmiaru tablicy - $ \theta( n ) $
$$ T(n) = \theta( n\log(n) ) $$
Kod funkcji Merge-Sort
Pseudo-kod funkcji
SORT-SCAL(T, p, r): JEŚLI p < r: q → (p+r)/2 SORT-SCAL(T, p, q) SORT-SCAL(T, q+1, r) SCALANIE(T, p, q, r)
JavaScript
function mergeSort( arr )
{
if( arr.length < 2 )
{
return arr;
}
var mid = Math.floor( arr.length / 2 );
var subLeft = mergeSort( arr.slice( 0, mid ) );
var subRight = mergeSort( arr.slice( mid ) );
return merge( subLeft, subRight );
}
function merge( a, b )
{
var result = [];
while( a.length > 0 && b.length > 0 )
{
result.push( a[0] < b[0] ? a.shift() : b.shift() );
}
return result.concat( a.length ? a : b );
}Sortowanie przez scalanie
Wprowadź liczby całkowite oddzielone spacją i naciśnij przycisk "Posortuj".
Posortuj
Posortuj