Ниткоподібне сортування

Ниткоподібне сортування (Strand sort) – це алгоритм сортування. Він працює за допомогою повторного витягування сортованих підсписків зі списку, що потрібно посортувати, та їх злиттям в кінцевий (посортований) список. Кожна ітерація витягує з непосортованого списку нитку вже посортованих елементів і зливає ці нитки (списки) в одну.

Ниткоподібне сортування

алгоритм у дії під час сортування списку чисел
Клас	Алгоритм сортування
Структура даних	Список
Найгірша швидкодія	${\displaystyle O(n^{2})}$
Найкраща швидкодія	${\displaystyle O(n)}$
Середня швидкодія	${\displaystyle O(n^{2})}$
Просторова складність у найгіршому випадку	${\displaystyle O(1)}$  допоміжний

Назва алгоритму походить від “ниток” (“частин”) посортованих даних в межах непосортованого списку, що вилучаються один за одним. Даний алгоритм є сортуванням з порівнянням, тому що він використовує порівняння, коли вилучає нитки-списки і коли з'єднує їх в посортований список.

Алгоритм ниткоподібного сортування у середньому виконує ${\displaystyle O(n^{2})}$ операцій. Проте у найкращому випадку (коли список уже посортований) алгоритм — лінійний, тобто здійснює всього ${\displaystyle O(n)}$ порівнянь. У найгіршому випадку (коли список посортований у зворотньому напрямку) алгоритм виконує ${\displaystyle O(n^{2})}$ операцій.

Ниткоподібне сортування доцільно застосовувати для даних, що зберігаються у зв'язному списку, через часте додавання та вилучення елементів. Якщо використовувати іншу структуру даних — наприклад, масив, тоді час виконання та складність алгоритму значно зростають. Також це сортування варто використовувати, коли велика частина даних уже посортована, тому що такі дані вилучаються одною “ниткою”.

Приклад

Список	Підсписок	Посортований список
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. Пройти по списку і витягнути посортований підсписок, починаючи з першого елемента.
2. Посортований підсписок з першої ітерації помістити в порожній посортований список.
3. Повторити крок 1.
4. Оскільки посортований список уже не порожній - злити підсписок та посортований список.
5. Повторити кроки 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 

Реалізація

#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" [ 31 січня 2009 у Wayback Machine.] зі ^[en] при NIST.
• Реалізація алгоритму ниткоподібного сортування різними мовами програмування [ 18 квітня 2015 у Wayback Machine.]