Визуализации алгоритмов сортировки

Пример

Для графа G=({2,3,5,7,8,9,10,11},{(3,8),(3,10),(5,11),(7,11),(7,8),(8,9),(11,2),(11,9),(11,10)}){\displaystyle G={\Bigl (}{\bigl \{}2,3,5,7,8,9,10,11{\bigr \}},{\bigl \{}(3,8),(3,10),(5,11),(7,11),(7,8),(8,9),(11,2),(11,9),(11,10){\bigr \}}{\Bigr )}}


Бесконтурный ориентированный граф

существует несколько согласованных последовательностей его вершин, которые могут быть получены при помощи топологической сортировки, например:

  • 7,5,11,3,8,2,9,10{\displaystyle 7,5,11,3,8,2,9,10}
  • 3,7,5,8,11,10,9,2{\displaystyle 3,7,5,8,11,10,9,2}

Видно, что в последовательности могут быть переставлены любые две стоящие рядом вершины, которые не входят в отношение частичного порядка E{\displaystyle E}.

Сравнение алгоритмов по скорости

Сделав столько визуализаций, было бы странно не заставить их соревноваться между собой.

На случайном наборе данных, как и ожидалось, коктейльная сортировка (слева) заметно проигрывает. Вторая слева — сортировка вставками, далее Шелла, и самая правая — сортировка расчёской:

Error handling this external URL

Те же алгоритмы, но на отсортированном в обратном порядке массиве. Заметно, что метод вставок сработал ещё медленнее:

Error handling this external URL

Теперь сравним алгоритмы, работающие за O(n log n). Быстрая сортировка слева, затем пирамидальная, слиянием, и самая правая — поразрядная.


Error handling this external URL

Те же алгоритмы ещё раз, но на этот раз в массиве только 8 уникальных значений. В этот раз быстрая сортировка справилась хуже.

Error handling this external URL

Подробнее про алгоритмы сортировки для начинающих вы можете прочитать в нашей статье из цикла «Алгоритмы и структуры данных».

Также посмотрите другие визуализации алгоритмов сортировки, больше ориентированные на учебные цели.

Середнячки

Середнячки: Рандом

type=random, unique=True
size(от min до max) × count
100(от 100 до 999) × 100 1000(от 1000 до 9999) × 10
Python PHP Python PHP
0.14101 0.18901 1.59109 1.7251
0.20601 0.22301 2.33013 2.09712
0.15301 0.22901 1.6711 2.23613
0.21601 0.26402 2.55515 2.73116
0.16701 0.33402 1.7251 3.13218

Середнячки: Почти отсортировано

type=almost, unique=True
size(от min до max) × count
100(от 100 до 999) × 100 1000(от 1000 до 9999) × 10
Python PHP Python PHP
0.009 0.005 0.009 0.005
0.009 0.014 0.01 0.014
0.01 0.01 0.011 0.008
0.011 0.008 0.013 0.008
0.011 0.017 0.013 0.017

Середнячки: Реверс

type=reverse, unique=True
size(от min до max) × count
100(от 100 до 999) × 100 1000(от 1000 до 9999) × 10
Python PHP Python PHP
0.26801 0.35902 3.10018 3.4292
0.39602 0.45303 4.49726 4.19524
0.22701 0.38402 2.48114 3.64421
0.30202 0.42603 3.34419 4.17524
0.30402 0.64404 3.36519 6.22036

Середнячки: Бинарник

type=random, unique=False, min=0, max=1
size × count
100 × 100 1000 × 10
Python PHP Python PHP
0.073 0.094 0.81105 0.86905
0.10401 0.11301 1.16307 1.06606
0.08801 0.12901 0.86405 1.18207
0.11501 0.15001 1.30107 1.41608
0.11401 0.25801 1.31908 2.46314

Быстрая сортировка

Этот алгоритм также относится к алгоритмам «разделяй и властвуй». Его используют чаще других алгоритмов, описанных в этой статье. При правильной конфигурации он чрезвычайно эффективен и не требует дополнительной памяти, в отличие от сортировки слиянием. Массив разделяется на две части по разные стороны от опорного элемента. В процессе сортировки элементы меньше опорного помещаются перед ним, а равные или большие —позади.

Алгоритм

Быстрая сортировка начинается с разбиения списка и выбора одного из элементов в качестве опорного. А всё остальное передвигаем так, чтобы этот элемент встал на своё место. Все элементы меньше него перемещаются влево, а равные и большие элементы перемещаются вправо.

Реализация


Существует много вариаций данного метода. Способ разбиения массива, рассмотренный здесь, соответствует схеме Хоара (создателя данного алгоритма).

Время выполнения

В среднем время выполнения быстрой сортировки составляет O(n log n).

Обратите внимание, что алгоритм быстрой сортировки будет работать медленно, если опорный элемент равен наименьшему или наибольшему элементам списка. При таких условиях, в отличие от сортировок кучей и слиянием, обе из которых имеют в худшем случае время сортировки O(n log n), быстрая сортировка в худшем случае будет выполняться O(n²)

Алгоритм

В «пузырьке», «шейкере» и «чёт-нечете» при переборе массива сравниваются соседние элементы. Основная идея «расчёски» в том, чтобы первоначально брать достаточно большое расстояние между сравниваемыми элементами и по мере упорядочивания массива сужать это расстояние вплоть до минимального. Таким образом, мы как бы причёсываем массив, постепенно разглаживая на всё более аккуратные пряди. Первоначальный разрыв между сравниваемыми элементами лучше брать с учётом специальной величины, называемой фактором уменьшения, оптимальное значение которой равно примерно 1,247[источник не указан 423 дня]. Сначала расстояние между элементами равно размеру массива, разделённого на фактор уменьшения (результат округляется до ближайшего целого). Затем, пройдя массив с этим шагом, необходимо поделить шаг на фактор уменьшения и пройти по списку вновь. Так продолжается до тех пор, пока разность индексов не достигнет единицы. В этом случае массив досортировывается обычным пузырьком.

Оптимальное значение фактора уменьшения 1,247…=11−e−ϕ{\displaystyle 1{,}247…={\tfrac {1}{1-e^{-\phi }}}}, где e{\displaystyle e} — основание натурального логарифма, а ϕ{\displaystyle \phi } — золотое сечение.

Оптимизация [ править | править код ]

В результате оптимизации гномья сортировка естественно трансформируется в сортировку вставками. Каждый раз «гном» наталкивается на новый номер, все значения слева от «гнома» уже отсортированы.

Гномья сортировка впервые была предложена 2 октября 2000 года Хамидом Сарбази-Азадом (Hamid Sarbazi-Azad). Он назвал ее «Глупая сортировка, простейший алгоритм сортировки всего с одним циклом…». И действительно, глупый этот метод или нет, но в нем задействован, никак в большинстве сортировок – два или более циклов, а только один. Позже, голландский ученый Дик Грун, на страницах одной из своих книг, привел для гномьей сортировки следующую аналогию.

Перевод:

Так описал основную идею алгоритма гномьей сортировки Дик Грун. Заменим гнома и горшки на более формальные объекты, например на указатель (номер текущего элемента) и элементы массива, и рассмотрим принцип работы алгоритма еще раз. Вначале указатель ставиться на 2-ый элемент массива (в C++ он имеет номер 1, а в Паскале номер 2).

Затем происходит сравнение двух соседних элементов A и A, т. е. сравниваются первый элемент (i-1) и второй (i). Если те стоят на своих позициях, то сдвигаем указатель на позицию i+1 и продолжаем сравнение с нового положения; иначе меняем элементы местами, и, поскольку в какой-то момент может оказаться, что элементы в левом подмассиве стоят не на своих местах, сдвигаем указатель на одну позицию влево, осуществляя следующее сравнение с новой позиции. Так алгоритм продолжает выполняться до тех пор, пока весь массив не будет упорядочен.


Здесь следует выделить два важных момента.

Во-первых, процесс упорядочивания заканчивается, тогда когда не выполняется условие i #include «stdafx.h» #include using namespace std ; int n ; void Gnome_sort ( int i, int j, int * mas ) < while ( i n ) < if ( mas mas ) < i = j ; j ++ ; > else < int t = mas ; mas = mas ; mas = t ; i — ; if ( i == 0 ) < i = j ; j ++ ; > > > cout «Отсортированный массив: « ; for ( i = 0 ; i n ; i ++ ) //вывод массива cout mas » « ; > void main ( ) < setlocale ( LC_ALL, «Rus» ) ; int m, k ; cout «Размер массива > « ; cin >> n ; int * a = new int ; for ( k = 0 ; k n ; k ++ ) //ввод массива < cout k + 1 » элемент >« ; cin >> a ; > k = 1 ; m = 2 ; Gnome_sort ( k, m, a ) ; //вызов функции сортировки delete a ; system ( «pause>>void» ) ; >

Код программы на Pascal:

Кажется немного необычным, тот факт, что алгоритм сортировки использует всего один цикл. Плюс к этому, на практике гномья сортировка не уступает в скорости сортировки вставками, что видно из таблицы трех случаев этих сортировок.

Гномья сортировка (Gnome sort) – простой в реализации алгоритм сортировки массива, назван в честь садового гнома, который предположительно таким методом сортирует садовые горшки.

Описание [ править | править код ]

Ниже написан псевдокод сортировки. Это оптимизированная версия с использованием переменной j, чтобы разрешить прыжок вперёд туда, где он остановился до движения влево, избегая лишних итераций и сравнений:

Если мы хотим отсортировать массив с элементами от большего к меньшему, то на итерациях цикла while будет происходить следующее:

  • (начальное состояние: i == 1, j == 2);
  • (ничего не произошло, но сейчас i == 2, j == 3);
  • (обмен a и a, сейчас i == 1, а j == 3 по-прежнему);
  • (обмен a и a, сейчас i == 3, j == 4);
  • (обмен a и a, сейчас i == 2, j == 4);
  • (ничего не произошло, но сейчас i == 4, j == 5);
  • цикл закончился, т. к. i не Реализация на С++

Примеры реализации

В простой форме функционального программирования на Haskell данный алгоритм будет выглядеть так:

data Tree a = Leaf | Node (Tree a) a (Tree a)

insert :: Ord a => a -> Tree a -> Tree a
insert x Leaf = Node Leaf x Leaf
insert x (Node t y t') | x <= y = Node (insert x t) y t'
insert x (Node t y t') | x > y = Node t y (insert x t')

flatten :: Tree a -> a
flatten Leaf = []
flatten (Node t x t') = flatten t ++ x ++ flatten t'

treesort :: Ord a => a -> a
treesort = flatten . foldr insert Leaf

Реализация на C++14:

#include <memory>
#include <cassert>
#include <algorithm>

#include <vector>
#include <iostream>

using namespace std;

// класс, представляющий бинарное дерево
class BinaryTree
{
protected
  // узел бинарного дерева
  struct BinaryTreeNode
  {
    shared_ptr<BinaryTreeNode> left, right; // левое и правое поддерево
    int key; // ключ
  };

  shared_ptr<BinaryTreeNode> m_root; // корень дерева
  
protected
  // рекурсивная процедура вставки ключа
  // cur_node - текущий узел дерева, с которым сравнивается вставляемый узел
  // node_to_insert - вставляемый узел
  void insert_recursive(const shared_ptr<BinaryTreeNode>& cur_node, const shared_ptr<BinaryTreeNode>& node_to_insert)
  {
      assert(cur_node != nullptr);
      // сравнение
      bool insertIsLess = node_to_insert->key < cur_node->key;
      if(insertIsLess)
      {
        // вставка в левое поддерево
        if(cur_node->left == nullptr)
          cur_node->left = node_to_insert;
        else
          insert_recursive(cur_node->left, node_to_insert);
      }
      else
      {
        // вставка в правое поддерево
        if(cur_node->right == nullptr)
          cur_node->right = node_to_insert;
        else
          insert_recursive(cur_node->right, node_to_insert);
      }
  }

public
  void insert(int key)
  {
    shared_ptr<BinaryTreeNode> node_to_insert(new BinaryTreeNode);
    node_to_insert->key = key;

    if(m_root == nullptr)
    {
        m_root = node_to_insert;
        return;
    }

    insert_recursive(m_root, node_to_insert);
  }

public
  typedef function<void(int key)> Visitor;

protected
  // рекурсивная процедура обхода дерева
  // cur_node - посещаемый в данный момент узел
  void visit_recursive(const shared_ptr<BinaryTreeNode>& cur_node, const Visitor& visitor)
  {
    assert(cur_node != nullptr);

    // сначала посещаем левое поддерево
    if(cur_node->left != nullptr)
      visit_recursive(cur_node->left, visitor);

    // посещаем текущий элемент
    visitor(cur_node->key);

    // посещаем правое поддерево
    if(cur_node->right != nullptr)
      visit_recursive(cur_node->right, visitor);
  }

public
  void visit(const Visitor& visitor)
  {
    if(m_root == nullptr)
      return;
    visit_recursive(m_root, visitor);
  }
};

int main()
{
  BinaryTree tree;
  // добавление элементов в дерево
  vector<int> data_to_sort = {10, 2, 7, 3, 14, 7, 32};
  for(int value  data_to_sort)
  {
    tree.insert(value);
  }
  // обход дерева
  tree.visit([](int visited_key)
  {
    cout<<visited_key<<" ";
  });
  cout<<endl;

  // результат выполнения: 2 3 7 7 10 14 32
  return ;
}

Пример создания бинарного дерева и сортировки на языке Java:

// Скомпилируйте и введите java TreeSort
class Tree {
   public Tree left;            // левое и правое поддеревья и ключ
   public Tree right;
   public int key;

   public Tree(int k) {        // конструктор с инициализацией ключа
      key = k;
   }

/*  insert (добавление нового поддерева (ключа))
    сравнить ключ добавляемого поддерева (К) с ключом корневого узла (X).
    Если K>=X, рекурсивно добавить новое дерево в правое поддерево.
    Если K<X, рекурсивно добавить новое дерево в левое поддерево.
    Если поддерева нет, то вставить на это место новое дерево
*/
   public void insert( Tree aTree) {
     if ( aTree.key < key )
        if ( left != null ) left.insert( aTree );
        else left = aTree;
     else
        if ( right != null ) right.insert( aTree );
        else right = aTree;
   }

/*  traverse (обход)
    Рекурсивно обойти левое поддерево.
    Применить функцию f (печать) к корневому узлу.
    Рекурсивно обойти правое поддерево.
*/
   public void traverse(TreeVisitor visitor) {
      if ( left != null) 
            left.traverse( visitor );

      visitor.visit(this);

      if ( right != null ) 
            right.traverse( visitor );
   }
}

interface TreeVisitor {
  public void visit(Tree node);
};

class KeyPrinter  implements TreeVisitor {
  public void visit(Tree node) {
      System.out.println( " " + node.key );
  }
};

class TreeSort {
  public static void main(String args[]) {
     Tree myTree;
     myTree = new Tree( 7 );       // создать дерево (с ключом)
     myTree.insert( new Tree( 5 ) );  // присоединять поддеревья
     myTree.insert( new Tree( 9 ) );
     myTree.traverse(new KeyPrinter());
  }
}

Алгоритм Тарьяна (1976)

На компьютере топологическую сортировку можно выполнить за O(n) времени и памяти, если обойти все вершины, используя поиск в глубину, и выводить вершины в момент выхода из неё.

Другими словами алгоритм состоит в следующем:

  • Изначально все вершины белые.
  • Для каждой вершины делаем шаг алгоритма.

Шаг алгоритма:

  • Если вершина чёрная, ничего делать не надо.
  • Если вершина серая — найден цикл, топологическая сортировка невозможна.
  • Если вершина белая
    • Красим её в серый
    • Применяем шаг алгоритма для всех вершин, в которые можно попасть из текущей
    • Красим вершину в чёрный и помещаем её в начало окончательного списка.

Пример

Пример будет на том же графе, однако порядок, в котором выбираем вершины для обхода — c, d, e, a, b.

Шаг Текущая Белые Стек (серые) Выход (чёрные)
a, b, c, d, e
1 c a, b, d, e c
2 d a, b, e c, d
3 e a, b c, d, e
4 d a, b c, d e
5 c a, b c d, e
6 a, b c, d, e
7 d a, b c, d, e
8 e a, b c, d, e
9 a b a c, d, e
10 b a, b c, d, e
11 a a b, c, d, e
12 a, b, c, d, e
13 b a, b, c, d, e

Описание

При сортировке Шелла сначала сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии d{\displaystyle d} (о выборе значения d{\displaystyle d} ). После этого процедура повторяется для некоторых меньших значений d{\displaystyle d}, а завершается сортировка Шелла упорядочиванием элементов при d=1{\displaystyle d=1} (то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

  • отсутствие потребности в памяти под стек;
  • отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.

Модификации[править]

Сортировка чет-нечетправить

Сортировка чет-нечет (англ. odd-even sort) — модификация пузырьковой сортировки, основанная на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. Сложность — . Псевдокод указан ниже:

function oddEvenSort(a):
  for i = 0 to n - 1 
    if i mod 2 == 0
      for j = 2 to n - 1 step 2
        if a < a
          swap(a, a)  
    else      
      for j = 1 to n - 1 step 2
        if a < a
          swap(a, a)

Преимущество этой сортировки — на нескольких процессорах она выполняется быстрее, так как четные и нечетные индексы сортируются параллельно.

Сортировка расческойправить

Сортировка расческой (англ. comb sort) — модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. Сложность — , но стремится к . Является самой быстрой квадратичной сортировкой. Недостаток — она неустойчива. Псевдокод указан ниже:

function combSort(a):
  k = 1.3
  jump = n
  bool swapped = true
  while jump > 1 and swapped
    if jump > 1
      jump /= k
    swapped = false
    for i = 0 to size - jump - 1
      if a < a
        swap(a, a)
        swapped = true

Пояснения: Изначально расстояние между сравниваемыми элементами равно , где — оптимальное число для этого алгоритма. Сортируем массив по этому расстоянию, потом уменьшаем его по этому же правилу. Когда расстояние между сравниваемыми элементами достигает единицы, массив досортировывается обычным пузырьком.

Сортировка перемешиваниемправить

Сортировка перемешиванием (англ. cocktail sort), также известная как Шейкерная сортировка — разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность — , но стремится она к , где — максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Псевдокод указан ниже:

function shakerSort(a):
  begin = -1
  end = n - 2
  while swapped
    swapped = false   
    begin++
    for i = begin to end 
      if a > a 
        swap(a, a)
        swapped = true    
    if !swapped
      break    
    swapped = false 
    end--
    for i = end downto begin
      if a > a 
        swap(a, a)
        swapped = true

Выбор длины промежутков

Среднее время работы алгоритма зависит от длин промежутков — d{\displaystyle d}, на которых будут находиться сортируемые элементы исходного массива ёмкостью N{\displaystyle N} на каждом шаге алгоритма. Существует несколько подходов к выбору этих значений:

  • первоначально используемая Шеллом последовательность длин промежутков: d1=N2,di=di−12,dk=1{\displaystyle d_{1}=N/2,d_{i}=d_{i-1}/2,d_{k}=1} в худшем случае, сложность алгоритма составит O(N2){\displaystyle O(N^{2})};
  • предложенная Хиббардом последовательность: все значения 2i−1≤N,i∈N{\displaystyle 2^{i}-1\leq N,i\in \mathbb {N} }; такая последовательность шагов приводит к алгоритму сложностью O(N32){\displaystyle O(N^{3/2})};
  • предложенная Седжвиком последовательность: di=9⋅2i−9⋅2i2+1{\displaystyle d_{i}=9\cdot 2^{i}-9\cdot 2^{i/2}+1}, если i четное и di=8⋅2i−6⋅2(i+1)2+1{\displaystyle d_{i}=8\cdot 2^{i}-6\cdot 2^{(i+1)/2}+1}, если i нечетное. При использовании таких приращений средняя сложность алгоритма составляет: O(n76){\displaystyle O(n^{7/6})}, а в худшем случае порядка O(n43){\displaystyle O(n^{4/3})}. При использовании формулы Седжвика следует остановиться на значении inc, если 3*inc > size.;
  • предложенная Праттом последовательность: все значения 2i⋅3j≤N2,i,j∈N{\displaystyle 2^{i}\cdot 3^{j}\leq N/2,i,j\in \mathbb {N} }; в таком случае сложность алгоритма составляет O(N(logN)2){\displaystyle O(N(logN)^{2})};
  • эмпирическая последовательность Марцина Циура (последовательность A102549 в OEIS): d∈{1,4,10,23,57,132,301,701,1750}{\displaystyle d\in \left\{1,4,10,23,57,132,301,701,1750\right\}}; является одной из лучших для сортировки массива ёмкостью приблизительно до 4000 элементов.;
  • эмпирическая последовательность, основанная на числах Фибоначчи: d∈{Fn}{\displaystyle d\in \left\{F_{n}\right\}};
  • все значения (3j−1)≤N{\displaystyle (3^{j}-1)\leq N} [источник не указан 3916 дней], j∈N{\displaystyle j\in \mathbb {N} }; такая последовательность шагов приводит к алгоритму сложностью O(N32){\displaystyle O(N^{3/2})}.

Реализация на Паскаль

  1. Заполняю массив случайными числами.
  2. Завожу цикл с условием «i < i + j», которое буквально означает «i отличается от i + j».
    1. Обнуляю i для того, чтобы при новом пробеге по массиву индекс не вышел за его границы.
    2. Завожу внутренний цикл с условием «i + j <= n», которое буквально значит «сумма индекса i и расстояния j между a и другим сравниваемым элементом не больше, чем самый большой индекс массива».
      1. Если a > a, то меняю их местами.
      2. Увеличиваю i.
    3. Уменьшаю j.
const
  n = 5;
 
var
  a array ..n of integer;
  i, jr integer;
  j real;
 
begin
  for i :=  to n do ai := Random(12);
  j := n;
  jr := Round(j);
  while i < i + jr do
  begin
    i := ;
    jr := Round(j);
    while i + j <= n do
    begin
      if ai > ai + Round(j)] then
      begin
        ai := ai + ai + jr;
        ai + jr := ai - ai + jr;
        ai := ai - ai + jr;
      end;
      Inc(i);
    end;
    j := j  1.247;
  end;
  
  for i :=  to n do
  begin
    for jr :=  to i - 1 do
    begin
      if ajr > ajr + 1 then
      begin
        ajr := ajr + ajr + 1;
        ajr + 1 := ajr - ajr + 1;
        ajr := ajr - ajr + 1;
      end;
    end;
  end;
  Writeln(a);
end.

Цикл прекратится лишь тогда, когда j станет равной 0, иначе говоря, когда i станет равным i + j.

Эффективность

Процедура добавления объекта в бинарное дерево имеет среднюю алгоритмическую сложность порядка O(log(n)){\displaystyle O(log(n))}. Соответственно, для n объектов сложность будет составлять O(nlog(n)){\displaystyle O(n\,log(n))}, что относит сортировку с помощью двоичного дерева к группе «быстрых сортировок». Однако, сложность добавления объекта в разбалансированное дерево может достигать O(n){\displaystyle O(n)}, что может привести к общей сложности порядка O(n2){\displaystyle O(n^{2})}.

При физическом развёртывании древовидной структуры в памяти требуется не менее чем 4n{\displaystyle 4n} ячеек дополнительной памяти (каждый узел должен содержать ссылки на элемент исходного массива, на родительский элемент, на левый и правый лист), однако, существуют способы уменьшить требуемую дополнительную память.

Алгоритм Кана (1962)

Один из первых алгоритмов, и наиболее приспособленный к исполнению вручную.

Пусть дан бесконтурный ориентированный простой граф G=(V,E){\displaystyle G=(V,E)}. Через A(v),v∈V{\displaystyle A(v),v\in V} обозначим множество вершин таких, что u∈A(v)⇔(u,v)∈E{\displaystyle u\in A(v)\Leftrightarrow (u,v)\in E}. То есть, A(v){\displaystyle A(v)} — множество всех вершин, из которых есть дуга в вершину v{\displaystyle v}. Пусть P{\displaystyle P} — искомая последовательность вершин.

пока |P|<|V|{\displaystyle |P|<|V|}
  выбрать любую вершину v{\displaystyle v} такую, что A(v)=∅{\displaystyle A(v)=\varnothing } и v∉P{\displaystyle v\notin P}
  P←P,v{\displaystyle P\gets P,v}
  удалить v{\displaystyle v} из всех A(u),u≠v{\displaystyle A(u),u\neq v}

Наличие хотя бы одного контура в графе приведёт к тому, что на определённой итерации цикла не удастся выбрать новую вершину v{\displaystyle v}.

Пример работы алгоритма

Пусть задан граф G=({a,b,c,d,e},{(a,b),(a,c),(a,d),(a,e),(b,d),(c,d),(c,e),(d,e)}){\displaystyle G={\Bigl (}{\bigl \{}a,b,c,d,e{\bigr \}},{\bigl \{}(a,b),(a,c),(a,d),(a,e),(b,d),(c,d),(c,e),(d,e){\bigr \}}{\Bigr )}}. В таком случае алгоритм выполнится следующим образом:

шаг v{\displaystyle v} A(a){\displaystyle A(a)} A(b){\displaystyle A(b)} A(c){\displaystyle A(c)} A(d){\displaystyle A(d)} A(e){\displaystyle A(e)} P{\displaystyle P}
−{\displaystyle -} ∅{\displaystyle \varnothing } a{\displaystyle a} a{\displaystyle a} a,b,c{\displaystyle a,b,c} a,c,d{\displaystyle a,c,d} ∅{\displaystyle \varnothing }
1 a{\displaystyle a} ∅{\displaystyle \varnothing } ∅{\displaystyle \varnothing } ∅{\displaystyle \varnothing } b,c{\displaystyle b,c} c,d{\displaystyle c,d} a{\displaystyle a}
2 c{\displaystyle c} ∅{\displaystyle \varnothing } ∅{\displaystyle \varnothing } ∅{\displaystyle \varnothing } b{\displaystyle b} d{\displaystyle d} a,c{\displaystyle a,c}
3 b{\displaystyle b} ∅{\displaystyle \varnothing } ∅{\displaystyle \varnothing } ∅{\displaystyle \varnothing } ∅{\displaystyle \varnothing } d{\displaystyle d} a,c,b{\displaystyle a,c,b}
4 d{\displaystyle d} ∅{\displaystyle \varnothing } ∅{\displaystyle \varnothing } ∅{\displaystyle \varnothing } ∅{\displaystyle \varnothing } ∅{\displaystyle \varnothing } a,c,b,d{\displaystyle a,c,b,d}
5 e{\displaystyle e} ∅{\displaystyle \varnothing } ∅{\displaystyle \varnothing } ∅{\displaystyle \varnothing } ∅{\displaystyle \varnothing } ∅{\displaystyle \varnothing } a,c,b,d,e{\displaystyle a,c,b,d,e}

На втором шаге вместо c{\displaystyle c} может быть выбрана вершина b{\displaystyle b}, поскольку порядок между b{\displaystyle b} и c{\displaystyle c} не задан.

Сложность[править]

В данной сортировке выполняются всего два различных вида операции: сравнение элементов и их обмен. Поэтому время всего алгоритма , где — время, затрачиваемое на сравнение элементов, а — время, за которое мы производим все необходимые обмены элементов.

Так как в алгоритме меняться местами могут только соседние элементы, то каждый обмен уменьшает количество инверсий на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по убыванию. Несложно посчитать, что количество инверсий в таком массиве . Получаем, что .

В неоптимизированной реализации на каждой итерации внутреннего цикла производятся сравнений, а так как внутренний цикл запускается также раз, то за весь алгоритм сортировки производятся сравнений.

В оптимизированной версии точное количество сравнений зависит от исходного массива. Известно, что худший случай равен , а лучший — . Следовательно, .

В итоге получаем .


С этим читают