Алгоритм сортировки расчёской (Comb Sort).

Основная идея «расчёски» в том, чтобы первоначально брать достаточно большое расстояние между сравниваемыми элементами и по мере упорядочивания массива сужать это расстояние вплоть до минимального. Таким образом, мы как бы причёсываем массив, постепенно разглаживая на всё более аккуратные пряди.

Реализован на языке программирования C#. Консольное приложение.

Пример кода из программы приведен ниже.

Топологическая сортировка

(Topological sort) — один из основных алгоритмов на графах, который применяется для решения множества более сложных задач.
Задача топологической сортировки графа состоит в следующем: указать такой линейный порядок на его вершинах, чтобы любое ребро вело от вершины с меньшим номером к вершине с большим номером. Очевидно, что если в графе есть циклы, то такого порядка не существует.
Ориентированной сетью (или просто сетью) называют бесконтурный ориентированный граф. В задачах подобного плана рассматриваются только конечные сети.

Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

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

2. далее выполняется операция алгоритма, называемая слиянием. Два единичных массива сливаются в общий результирующий массив, при этом из каждого выбирается меньший элемент (сортировка по возрастанию) и записывается в свободную левую ячейку результирующего массива. После чего из двух результирующих массивов собирается третий общий отсортированный массив, и так далее. В случае если один из массивов закончиться, элементы другого дописываются в собираемый массив;

3. в конце операции слияния, элементы перезаписываются из результирующего массива в исходный.

1) static Int32[] Merge_Sort(Int32[] massive)

{

if (massive.Length == 1)

return massive;

Int32 mid_point = massive.Length / 2;

return Merge(Merge_Sort(massive.Take(mid_point).ToArray()), Merge_Sort(massive.Skip(mid_point).ToArray()));

}

 

static Int32[] Merge(Int32[] mass1, Int32[] mass2)

{

Int32 a = 0, b = 0;

Int32[] merged = new int[mass1.Length + mass2.Length];

for (Int32 i = 0; i < mass1.Length + mass2.Length; i++)

{

if (b < mass2.Length && a < mass1.Length)

if (mass1[a] > mass2[b])

merged[i] = mass2[b++];

else //if int go for

merged[i] = mass1[a++];

else

if (b < mass2.Length)

merged[i] = mass2[b++];

else

merged[i] = mass1[a++];

}

return merged;

}

 

static void Main(string[] args)

{

Int32[] arr = new Int32[100];

//заполняем массив случайными числами

Random rd = new Random();

for(Int32 i = 0; i < arr.Length; ++i) {

arr[i] = rd.Next(1, 101);

}

System.Console.WriteLine("The array before sorting:");

foreach (Int32 x in arr)

{

System.Console.Write(x + " ");

}

//сортировка

 

arr = Merge_Sort(arr);

 

System.Console.WriteLine("\n\nThe array after sorting:");

foreach (Int32 x in arr)

{

System.Console.Write(x + " ");

}

System.Console.WriteLine("\n\nPress the <Enter> key");

System.Console.ReadLine();

}

2) //предыдущий пример сортирует лишь целые числа. Следующий - работает со всеми типами данных.

static IComparable[] Merge_Sort(IComparable[] massive)

{

if (massive.Length == 1)

return massive;

int mid_point = massive.Length / 2;

return Merge(Merge_Sort(massive.Take(mid_point).ToArray()), Merge_Sort(massive.Skip(mid_point).ToArray()));

}

static IComparable[] Merge(IComparable[] mass1, IComparable[] mass2)

{

Алгоритм чётно-нечётной сортировки (Odd-Even Sort).

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

Сначала элементы с нечётными индексами сравниваются/обмениваются с элементами с чётными индексами (1-й со 2-м, 3-й с 4-м, 5-й с 6-м и т.д.). Затем элементы с чётными индексами сравниваются/обмениваются с соседними элементами с нечётными индексами (2-й с 3-м, 4-й с 5-м, 6-й с 7-м и т.д.). Затем снова нечётные сравниваются с чётными, потом снова чётные с нечётными и т.д. Процесс завершается если в результате двух прогонов не происходило обменов — значит массив упорядочен.

Реализован на языке программирования C#. Консольное приложение.

Пример кода из программы приведен ниже.

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

Давайте посмотрим на работу сортировки выбором на нашем неотсортированном массиве.

При первом проходе алгоритм с помощью метода FindIndexOfSmallestFromIndex пытается найти наименьшее значение в массиве и переместить его в начало.

Имея такой маленький массив, мы сразу можем сказать, что наименьшее значение — 3, и оно уже находится на правильной позиции. На этом этапе мы знаем, что на первой позиции в массиве (индекс 0) находится самое маленькое значение, следовательно, начало массива уже отсортировано. Поэтому мы начинаем второй проход — на этот раз по индексам от 1 до n — 1.

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

Теперь неотсортированная часть массива начинается с индекса 2. Она растет на один элемент при каждом проходе алгоритма. Если на каком-либо проходе мы не сделали ни одного обмена, это означает, что массив отсортирован.

После еще двух проходов алгоритм завершает свою работу:

public void Sort(T[] items)

{

int sortedRangeEnd = 0;

 

while (sortedRangeEnd < items.Length)

{

   int nextIndex = FindIndexOfSmallestFromIndex(items, sortedRangeEnd);

   Swap(items, sortedRangeEnd, nextIndex);

 

   sortedRangeEnd++;

}

}

 

private int FindIndexOfSmallestFromIndex(T[] items, int sortedRangeEnd)

{

T currentSmallest = items[sortedRangeEnd];

int currentSmallestIndex = sortedRangeEnd;

 

for (int i = sortedRangeEnd + 1; i < items.Length; i++)

{        

   if (currentSmallest.CompareTo(items[i]) > 0)

   {

       currentSmallest = items[i];

       currentSmallestIndex = i;

   }

}

 

return currentSmallestIndex;

}