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

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

Ниткоподібне сортування
алгоритм у дії під час сортування списку чисел
Клас Алгоритм сортування
Структура даних Список
Найгірша швидкодія
Найкраща швидкодія
Середня швидкодія
Просторова складність у найгіршому випадку   допоміжний

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

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

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

Приклад
CписокПідсписокПосортований список
3 1 5 4 2
1 4 23 5
1 4 23 5
21 43 5
21 3 4 5
21 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.

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.