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

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

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

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

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

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

Реалізація

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