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

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

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

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

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

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

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

Кроки:

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; } 

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) 

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.]

п о р Алгоритми сортування Теорія Обчислювальна складність | Нотація великого О | Відношення порядку | Список | Стабільність | Сортування порівняннями Сортування обміном Сортування бульбашкою | Сортування змішуванням | Odd-even sort | Сортування гребінцем | Сортування гнома | Швидке сортування Сортування вибором Сортування вибором | Пірамідальне сортування Сортування включенням Сортування включенням | Сортування Шелла | Сортування бінарним деревом | Сортування вставкою з проміжками | Patience sorting[en] Сортування злиттям Сортування злиттям | Ниткоподібне сортування Алгоритми без порівнянь Сортування за розрядами | Сортування комірками | Сортування підрахунком | Цифрове сортування | Burstsort[en] | Bead sort[en] Інші Топологічне сортування | Sorting network[en] | Bitonic sorter[en] Непрактичні алгоритми Випадкове сортування | Stooge sort