Ниткоподібне сортування (Strand sort) – це алгоритм сортування. Він працює за допомогою повторного витягування сортованих підсписків зі списку, що потрібно посортувати, та їх злиттям в кінцевий (посортований) список. Кожна ітерація витягує з непосортованого списку нитку вже посортованих елементів і зливає ці нитки (списки) в одну.
Назва алгоритму походить від “ниток” (“частин”) посортованих даних в межах непосортованого списку, що вилучаються один за одним. Даний алгоритм є сортуванням з порівнянням, тому що він використовує порівняння, коли вилучає нитки-списки і коли з'єднує їх в посортований список.
Алгоритм ниткоподібного сортування у середньому виконує операцій. Проте у найкращому випадку (коли список уже посортований) алгоритм — лінійний, тобто здійснює всього порівнянь. У найгіршому випадку (коли список посортований у зворотньому напрямку) алгоритм виконує операцій.
Ниткоподібне сортування доцільно застосовувати для даних, що зберігаються у зв'язному списку, через часте додавання та вилучення елементів. Якщо використовувати іншу структуру даних — наприклад, масив, тоді час виконання та складність алгоритму значно зростають. Також це сортування варто використовувати, коли велика частина даних уже посортована, тому що такі дані вилучаються одною “ниткою”.
Приклад Список Підсписок Посортований список 3 1 5 4 2 1 4 2 3 5 1 4 2 3 5 2 1 4 3 5 2 1 3 4 5 2 1 3 4 5 1 2 3 4 5
Кроки: Пройти по списку і витягнути посортований підсписок, починаючи з першого елемента. Посортований підсписок з першої ітерації помістити в порожній посортований список. Повторити крок 1. Оскільки посортований список уже не порожній - злити підсписок та посортований список. Повторити кроки 3-4 поки зі списку не будуть вилучені всі елементи.
Псевдокод Простий спосіб зображення ниткоподібного сортування на псевдокоді: procedure strandSort( A : list of sortable items ) defined as: while length( A ) > 0 clear sublist sublist[ 0 ] := A[ 0 ] remove A[ 0 ] for each i in 0 to length( A ) - 1 do: if A[ i ] > sublist[ last ] then append A[ i ] to sublist remove A[ i ] end if end for merge sublist into results end while return results end procedure
Реалізація C++ #include <list> using namespace std;
template <typename T> list<T> strandSort(list<T> unsorted) { if (unsorted.size() <= 1)
return unsorted;
list<T> result; list<T> sublist; while (!unsorted.empty())
sublist.push_back(unsorted.front()); unsorted.pop_front(); for (typename list<T>::iterator it = unsorted.begin(); it != unsorted.end();)
if (sublist.back() <= *it)
sublist.push_back(*it); it = unsorted.erase(it);
else
it++;
result.merge(sublist);
return result; }
Haskell merge :: (Ord a) => [a] -> [a] -> [a] merge [] ys = ys merge xs [] = xs merge (x : xs) (y : ys) | x <= y = x : merge xs (y : ys) | otherwise = y : merge (x : xs) ys
strandSort :: (Ord a) => [a] -> [a] strandSort [] = [] strandSort (x : xs) = merge strand (strandSort rest) where (strand, rest) = extractStrand x xs extractStrand x [] = ([x], []) extractStrand x (x1 : xs) | x <= x1 = let (strand, rest) = extractStrand x1 xs in (x : strand, rest) | otherwise = let (strand, rest) = extractStrand x xs in (strand, x1 : rest)
Pascal program StrandSortDemo;
type TIntArray = array of integer;
function merge(left: TIntArray; right: TIntArray): TIntArray; var i, j, k: integer; begin setlength(merge, length(left) + length(right)); i := low(merge); j := low(left); k := low(right); repeat if ((left[j] <= right[k]) and (j <= high(left))) or (k > high(right)) then begin merge[i] := left[j]; inc(j); end else begin merge[i] := right[k]; inc(k); end; inc(i); until i > high(merge); end;
function StrandSort(s: TIntArray): TIntArray; var strand: TIntArray; i, j: integer; begin setlength(StrandSort, length(s)); setlength(strand, length(s)); i := low(s); repeat StrandSort[i] := s[i]; inc(i); until (s[i] < s[i-1]); setlength(StrandSort, i); repeat setlength(strand, 1); j := low(strand); strand[j] := s[i]; while (s[i+1] > s[i]) and (i < high(s)) do begin inc(i); inc(j); setlength(strand, length(strand) + 1); Strand[j] := s[i]; end; StrandSort := merge(StrandSort, strand); inc(i); until (i > high(s)); end;
var data: TIntArray; i: integer;
begin setlength(data, 8); Randomize; writeln('The data before sorting:'); for i := low(data) to high(data) do begin data[i] := Random(high(data)); write(data[i]:4); end; writeln; data := StrandSort(data); writeln('The data after sorting:'); for i := low(data) to high(data) do begin write(data[i]:4); end; writeln; end.
Посилання Paul E. Black "Strand Sort" зі при NIST. Реалізація алгоритму ниткоподібного сортування різними мовами програмування