Сортировка с бинарными вставками

Сортировка Пузырьком

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

Например, у нас есть массив целых чисел:

При первом проходе по массиву мы сравниваем значения 3 и 7. Поскольку 7 больше 3, мы оставляем их как есть. После чего сравниваем 7 и 4. 4 меньше 7, поэтому мы меняем их местами, перемещая семерку на одну позицию ближе к концу массива. Теперь он выглядит так:

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

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

И снова был произведен как минимум один обмен, а значит, проходим по массиву еще раз.

При следующем проходе обмена не производится, что означает, что наш массив отсортирован, и алгоритм закончил свою работу. Пример

Сортировка Шелла

Этот метод сортировки Д. Шелл предложил в 1959 г. Он использует минимум памяти и показывает высокие скорости при сортировке.

 По сути в методе Шелла применяются сравнения и перестановки элементов аналогичные методу вставок, но при этом порядок сравниваемых элементов совершенно другой. Идея сортировки методом Шелла состоит в том, чтобы сортировать элементы отстоящие друг от друга на некотором расстоянии step. Затем сортировка повторяется при меньших значениях step, и в конце процесс сортировки Шелла завершается при step = 1 (а именно обычной сортировкой вставками). До сих пор продолжает обсуждаться вопрос выбора шага сортировки step. Шелл предложил такую последовательность: N/2, N/4, N/8 …, где N – количество элементов в сортируемом массиве. Сортировка Шелла требует около log2N проходов для упорядочивания последовательности длиной N.

Пример

Шейкер-сортировка

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

Эти две идеи приводят к модификациям в методе пузырьковой сортировки.

От последней перестановки до конца (начала) массива находятся отсортированные элементы. Учитывая данный факт, просмотр осуществляется не до конца (начала) массива, а до конкретной позиции. Границы сортируемой части массива сдвигаются на 1 позицию на каждой итерации.

Массив просматривается поочередно справа налево и слева направо.

Просмотр массива осуществляется до тех пор, пока все элементы не встанут в порядке возрастания (убывания).

Количество просмотров элементов массива определяется моментом упорядочивания его элементов.

Рассмотрим алгоритм Шейкер-сортировки на примере. Дана последовательность

 

Пример и объяснение алгоритма

void shekerSort(double *mass, int count)
{
int left = 0, right = count - 1; // левая и правая границы сортируемой области массива
int flag = 1; // флаг наличия перемещений
// Выполнение цикла пока левая граница не сомкнётся с правой
// или пока в массиве имеются перемещения
while ((left < right) && flag > 0)
{
flag = 0;
for (int i = left; i<right; i++) //двигаемся слева направо
{
if (mass[i]>mass[i + 1]) // если следующий элемент меньше текущего,
{ // меняем их местами
double t = mass[i];
mass[i] = mass[i + 1];
mass[i + 1] = t;
flag = 1; // перемещения в этом цикле были
}
}
right--; // сдвигаем правую границу на предыдущий элемент
for (int i = right; i>left; i--) //двигаемся справа налево
{
if (mass[i - 1]>mass[i]) // если предыдущий элемент больше текущего,
{ // меняем их местами
double t = mass[i];
mass[i] = mass[i - 1];
mass[i - 1] = t;
flag = 1; // перемещения в этом цикле были
}
}
left++; // сдвигаем левую границу на следующий элемент
}
}
int main() {
double m[10];
// Вводим элементы массива
for (int i = 0; i<10; i++)

{
printf("m[%d]=", i);
scanf("%lf", &m[i]);
}
shekerSort(m, 10); // вызываем функцию сортировки
// Выводим отсортированные элементы массива
for (int i = 0; i<10; i++)
printf("%.2lf ", m[i]);
getchar(); getchar();
return 0;
}

Сортировка вставками

Сортировка вставками работает, проходя по массиву и перемещая нужное значение в начало массива. После того, как обработана очередная позиция, мы знаем, что все позиции до нее отсортированы, а после нее — нет.

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

Постепенно отсортированная часть массива растет, и, в конце концов, массив окажется упорядоченным.

Давайте взглянем на конкретный пример. Вот наш неотсортированный массив, который мы будем использовать:

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

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

На этом этапе элементы с индексами 0..1 отсортированы, а про элементы с индексами 2..n ничего не известно.

Следующим проверяется значение 4. Так как оно меньше семи, мы должны перенести его на правильную позицию в отсортированную часть массива. Остается вопрос: как ее определить? Это осуществляется методом FindInsertionIndex. Он сравнивает переданное ему значение (4) с каждым значением в отсортированной части, пока не найдет место для вставки.

Итак, мы нашли индекс 1 (между значениями 3 и 7). Метод Insert осуществляет вставку, удаляя вставляемое значение из массива и сдвигая все значения, начиная с индекса для вставки, вправо. Теперь массив выглядит так:

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

Когда больше нет возможностей для вставок, массив считается полностью отсортированным, и работа алгоритма закончена.

Пример

public void Sort(T[] items)

{

int sortedRangeEndIndex = 1;

 

while (sortedRangeEndIndex < items.Length)

{

   if (items[sortedRangeEndIndex].CompareTo(items[sortedRangeEndIndex - 1]) < 0)

   {

       int insertIndex = FindInsertionIndex(items, items[sortedRangeEndIndex]);

       Insert(items, insertIndex, sortedRangeEndIndex);

   }

 

   sortedRangeEndIndex++;

}

}

 

private int FindInsertionIndex(T[] items, T valueToInsert)

{

for (int index = 0; index < items.Length; index++) {

   if (items[index].CompareTo(valueToInsert) > 0)

   {

       return index;

   }

}

 

throw new InvalidOperationException("The insertion index was not found");

}

 

private void Insert(T[] itemArray, int indexInsertingAt, int indexInsertingFrom)

{

// itemArray =  0 1 2 4 5 6 3 7

// insertingAt = 3

// insertingFrom = 6

//

// Действия:

// 1: Сохранить текущий индекс в temp

// 2: Заменить indexInsertingAt на indexInsertingFrom

// 3: Заменить indexInsertingAt на indexInsertingFrom в позиции +1

// Сдвинуть элементы влево на один.

// 4: Записать temp на позицию в массиве + 1.

   

 

// Шаг 1.

T temp = itemArray[indexInsertingAt];

 

// Шаг 2.

 

itemArray[indexInsertingAt] = itemArray[indexInsertingFrom];

 

// Шаг 3.

for (int current = indexInsertingFrom; current > indexInsertingAt; current--)

{

   itemArray[current] = itemArray[current - 1];

}

 

// Шаг 4.

itemArray[indexInsertingAt + 1] = temp;

}

 

 

Сортировка выбором

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

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

При первом проходе алгоритм с помощью метода 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;}

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

Быстрая сортировка — это еще один алгоритм типа «разделяй и властвуй». Он работает, рекурсивно повторяя следующие шаги:

1. Выбрать ключевой индекс и разделить по нему массив на две части. Это можно делать разными способами, но в данной статье мы используем случайное число.

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

3. Повторяем первые два шага, пока массив не будет полностью отсортирован.

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

Сначала мы случайным образом выбираем ключевой элемент:

int pivotIndex = _pivotRng.Next(left, right);

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

Перемещение значений осуществляется методом partition.

На этом этапе мы знаем, что значение 6 находится на правильной позиции. Теперь мы повторяем этот процесс для правой и левой частей массива.

Мы рекурсивно вызываем метод quicksort на каждой из частей. Ключевым элементом в левой части становится пятерка. При перемещении значений она изменит свой индекс. Главное — помнить, что нам важно именно ключевое значение, а не его индекс.

Снова применяем быструю сортировку:

И еще раз:

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

Random _pivotRng = new Random();

 

public void Sort(T[] items)

{

quicksort(items, 0, items.Length - 1);

}

 

private void quicksort(T[] items, int left, int right)

{

if (left < right)

{

   int pivotIndex = _pivotRng.Next(left, right);

   int newPivot = partition(items, left, right, pivotIndex);

 

   quicksort(items, left, newPivot - 1);

   quicksort(items, newPivot + 1, right);

}

}

 

private int partition(T[] items, int left, int right, int pivotIndex)

{

T pivotValue = items[pivotIndex];

 

Swap(items, pivotIndex, right);

 

int storeIndex = left;

 

for (int i = left; i < right; i++)

{

   if (items[i].CompareTo(pivotValue) < 0)

   {

       Swap(items, i, storeIndex);

       storeIndex += 1;

   }

}

 

Swap(items, storeIndex, right);

return storeIndex;

}

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

Разделяй и властвуй

До сих пор мы рассматривали линейные алгоритмы. Они используют мало дополнительной памяти, но имеют квадратичную сложность. На примере сортировки слиянием мы посмотрим на алгоритм типа «разделяй и властвуй»

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

Если вы хотите найти человека по фамилии Петров, вы не станете искать, начиная с буквы А и переворачивая по одной странице. Вы, скорее всего, откроете книгу где-то посередине. Если попадете на букву Т, перелистнете несколько страниц назад, возможно, слишком много — до буквы О. Тогда вы пойдете вперед. Таким образом, перелистывая туда и обратно все меньшее количество страниц, вы, в конце концов, найдете нужную.

Насколько эффективны эти алгоритмы?

Предположим, что в телефонной книге 1000 страниц. Если вы открываете ее на середине, вы отбрасываете 500 страниц, в которых нет искомого человека. Если вы не попали на нужную страницу, вы выбираете правую или левую сторону и снова оставляете половину доступных вариантов. Теперь вам надо просмотреть 250 страниц. Таким образом мы делим нашу задачу пополам снова и снова и можем найти человека в телефонной книге всего за 10 просмотров. Это составляет 1% от всего количества страниц, которые нам пришлось бы просмотреть при линейном поиске.

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

При сортировке слиянием мы разделяем массив пополам до тех пор, пока каждый участок не станет длиной в один элемент. Затем эти участки возвращаются на место (сливаются) в правильном порядке.

Давайте посмотрим на такой массив:

Разделим его пополам:

И будем делить каждую часть пополам, пока не останутся части с одним элементом:

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

Сначала мы получаем группы по два отсортированных элемента, потом «собираем» их в группы по четыре элемента и в конце собираем все вместе в отсортированный массив.

Для работы алгоритма мы должны реализовать следующие операции:

1. Операцию для рекурсивного разделения массива на группы (метод Sort).

2. Слияние в правильном порядке (метод Merge).

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

public void Sort(T[] items)

{

if (items.Length <= 1)

{

    return;

}      

 

int leftSize = items.Length / 2;

int rightSize = items.Length - leftSize;

T[] left = new T[leftSize];

T[] right = new T[rightSize];

Array.Copy(items, 0, left, 0, leftSize);

Array.Copy(items, leftSize, right, 0, rightSize);

Sort(left);

Sort(right);

Merge(items, left, right);

}  

 

private void Merge(T[] items, T[] left, T[] right)

{

int leftIndex = 0;

int rightIndex = 0;

int targetIndex = 0;

int remaining = left.Length + right.Length;

while(remaining > 0)

{

   if (leftIndex >= left.Length)

   {

       items[targetIndex] = right[rightIndex++];

   }

   else if (rightIndex >= right.Length)

   {

       items[targetIndex] = left[leftIndex++];

   }

   else if (left[leftIndex].CompareTo(right[rightIndex]) < 0)

   {

       items[targetIndex] = left[leftIndex++];

   }

   else

   {

       items[targetIndex] = right[rightIndex++];

   }

 

   targetIndex++;

   remaining--;

}

}

 

Пример

static void InsertBin()

{

int[] A = { 3, 8, 4, 3, 2, 7, 10, 5 };

int i, j;

int n = 8;

int m, l, r, k;

Console.WriteLine("Исходный массив:");

for (i = 0; i < n; i++)

Console.Write("{0} ", A[i]);

for (i = 2; i < n; i++)

{

k=A[i];

l =1;

r = i;

while(l<r)

{

m = (l + r) / 2;

if (k<A[m])

{

r = m - 1;

}

// else r = m;

else if (k>A[m])

{

 

l = m + 1;

}

else k =A[m];

 

}

for (j = i; j > r + 1; j--)

{

A[j] = A[j - 1];

A[r] = k;

}

 

}

Console.WriteLine(" ");

Console.WriteLine(" ");

Console.WriteLine("Отсортированый массив:");

for (i = 0; i < n; i++)

Console.Write("{0} ", A[i]);

Console.Read();

 

}

Сортировка подсчётом

Алгоритм сортировки подсчетом прост. Подсчитывается количество вхождений всех элементов из диапазона в сортируемый массив, и потом выводятся элементы нужное количество раз. В данной реализации не используется массив сортируемых элементов. После считывания очередного элемента, увеличение счетчика происходит сразу же. Реализация данного алгоритма на C#: using System; using System.Collections.Generic; using System.Linq; using System.Text;

namespace Sort { class Program { static void Main() { int k = 100; // Считываем размер массива, // который необходимо отсортировать int size; size = Convert.ToInt32(Console.ReadLine()); // Динамически выделяем память под // хранение массива размера size int[] c = new int[k]; //считываем строку string str = Console.ReadLine(); //разбиваем по пробелам string[] mas = str.Split(' ');

//строим массив с for (int i = 0; i < size; i++) { c[int.Parse(mas[i])]++; } //бежимся по всему отрезку //с 0 до k-1 for (int i = 0; i < k; i++) { //выводим i c[i] раз for (int j = 0; j < c[i]; j++) { Console.Write(i); Console.Write(' '); } } } } }

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

Идея алгоритма очень проста. Пусть имеется массив A размером N, тогда сортировка выбором сводится к следующему:

 

1. берем первый элемент последовательности A[i], здесь i – номер элемента, для первого i равен 1;

2. находим минимальный (максимальный) элемент последовательности и запоминаем его номер в переменную key;

3. если номер первого элемента и номер найденного элемента не совпадают, т. е. если key?1, тогда два этих элемента обмениваются значениями, иначе никаких манипуляций не происходит;

4. увеличиваем i на 1 и продолжаем сортировку оставшейся части массива, а именно с элемента с номером 2 по N, так как элемент A[1] уже занимает свою позицию;

 

 

С каждым последующим шагом размер подмассива, с которым работает алгоритм, уменьшается на 1, но на способ сортировки это не влияет, он одинаков для каждого шага.

 

public void SelectionSort(int[] arr)

{

int min, temp;

int length = arr.Length;

 

for (int i = 0; i < length - 1; i++)

{

min = i;

 

for (int j = i + 1; j < length; j++)

{

if (arr[j] < arr[min])

{

min = j;

}

}

 

if (min!= i)

{

temp = arr[i];

arr[i] = arr[min];

arr[min] = temp;

}

}

}

 

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

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

}

 

 

Сортировка Пузырьком

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

Например, у нас есть массив целых чисел:

При первом проходе по массиву мы сравниваем значения 3 и 7. Поскольку 7 больше 3, мы оставляем их как есть. После чего сравниваем 7 и 4. 4 меньше 7, поэтому мы меняем их местами, перемещая семерку на одну позицию ближе к концу массива. Теперь он выглядит так:

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

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

И снова был произведен как минимум один обмен, а значит, проходим по массиву еще раз.

При следующем проходе обмена не производится, что означает, что наш массив отсортирован, и алгоритм закончил свою работу. Пример

Сортировка Шелла

Этот метод сортировки Д. Шелл предложил в 1959 г. Он использует минимум памяти и показывает высокие скорости при сортировке.

 По сути в методе Шелла применяются сравнения и перестановки элементов аналогичные методу вставок, но при этом порядок сравниваемых элементов совершенно другой. Идея сортировки методом Шелла состоит в том, чтобы сортировать элементы отстоящие друг от друга на некотором расстоянии step. Затем сортировка повторяется при меньших значениях step, и в конце процесс сортировки Шелла завершается при step = 1 (а именно обычной сортировкой вставками). До сих пор продолжает обсуждаться вопрос выбора шага сортировки step. Шелл предложил такую последовательность: N/2, N/4, N/8 …, где N – количество элементов в сортируемом массиве. Сортировка Шелла требует около log2N проходов для упорядочивания последовательности длиной N.

Пример

Шейкер-сортировка

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

Эти две идеи приводят к модификациям в методе пузырьковой сортировки.

От последней перестановки до конца (начала) массива находятся отсортированные элементы. Учитывая данный факт, просмотр осуществляется не до конца (начала) массива, а до конкретной позиции. Границы сортируемой части массива сдвигаются на 1 позицию на каждой итерации.

Массив просматривается поочередно справа налево и слева направо.

Просмотр массива осуществляется до тех пор, пока все элементы не встанут в порядке возрастания (убывания).

Количество просмотров элементов массива определяется моментом упорядочивания его элементов.

Рассмотрим алгоритм Шейкер-сортировки на примере. Дана последовательность

 

Пример и объяснение алгоритма

void shekerSort(double *mass, int count)
{
int left = 0, right = count - 1; // левая и правая границы сортируемой области массива
int flag = 1; // флаг наличия перемещений
// Выполнение цикла пока левая граница не сомкнётся с правой
// или пока в массиве имеются перемещения
while ((left < right) && flag > 0)
{
flag = 0;
for (int i = left; i<right; i++) //двигаемся слева направо
{
if (mass[i]>mass[i + 1]) // если следующий элемент меньше текущего,
{ // меняем их местами
double t = mass[i];
mass[i] = mass[i + 1];
mass[i + 1] = t;
flag = 1; // перемещения в этом цикле были
}
}
right--; // сдвигаем правую границу на предыдущий элемент
for (int i = right; i>left; i--) //двигаемся справа налево
{
if (mass[i - 1]>mass[i]) // если предыдущий элемент больше текущего,
{ // меняем их местами
double t = mass[i];
mass[i] = mass[i - 1];
mass[i - 1] = t;
flag = 1; // перемещения в этом цикле были
}
}
left++; // сдвигаем левую границу на следующий элемент
}
}
int main() {
double m[10];
// Вводим элементы массива
for (int i = 0; i<10; i++)

{
printf("m[%d]=", i);
scanf("%lf", &m[i]);
}
shekerSort(m, 10); // вызываем функцию сортировки
// Выводим отсортированные элементы массива
for (int i = 0; i<10; i++)
printf("%.2lf ", m[i]);
getchar(); getchar();
return 0;
}

Сортировка вставками

Сортировка вставками работает, проходя по массиву и перемещая нужное значение в начало массива. После того, как обработана очередная позиция, мы знаем, что все позиции до нее отсортированы, а после нее — нет.

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

Постепенно отсортированная часть массива растет, и, в конце концов, массив окажется упорядоченным.

Давайте взглянем на конкретный пример. Вот наш неотсортированный массив, который мы будем использовать:

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

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

На этом этапе элементы с индексами 0..1 отсортированы, а про элементы с индексами 2..n ничего не известно.

Следующим проверяется значение 4. Так как оно меньше семи, мы должны перенести его на правильную позицию в отсортированную часть массива. Остается вопрос: как ее определить? Это осуществляется методом FindInsertionIndex. Он сравнивает переданное ему значение (4) с каждым значением в отсортированной части, пока не найдет место для вставки.

Итак, мы нашли индекс 1 (между значениями 3 и 7). Метод Insert осуществляет вставку, удаляя вставляемое значение из массива и сдвигая все значения, начиная с индекса для вставки, вправо. Теперь массив выглядит так:

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

Когда больше нет возможностей для вставок, массив считается полностью отсортированным, и работа алгоритма закончена.

Пример

public void Sort(T[] items)

{

int sortedRangeEndIndex = 1;

 

while (sortedRangeEndIndex < items.Length)

{

   if (items[sortedRangeEndIndex].CompareTo(items[sortedRangeEndIndex - 1]) < 0)

   {

       int insertIndex = FindInsertionIndex(items, items[sortedRangeEndIndex]);

       Insert(items, insertIndex, sortedRangeEndIndex);

   }

 

   sortedRangeEndIndex++;

}

}

 

private int FindInsertionIndex(T[] items, T valueToInsert)

{

for (int index = 0; index < items.Length; index++) {

   if (items[index].CompareTo(valueToInsert) > 0)

   {

       return index;

   }

}

 

throw new InvalidOperationException("The insertion index was not found");

}

 

private void Insert(T[] itemArray, int indexInsertingAt, int indexInsertingFrom)

{

// itemArray =  0 1 2 4 5 6 3 7

// insertingAt = 3

// insertingFrom = 6

//

// Действия:

// 1: Сохранить текущий индекс в temp

// 2: Заменить indexInsertingAt на indexInsertingFrom

// 3: Заменить indexInsertingAt на indexInsertingFrom в позиции +1

// Сдвинуть элементы влево на один.

// 4: Записать temp на позицию в массиве + 1.

   

 

// Шаг 1.

T temp = itemArray[indexInsertingAt];

 

// Шаг 2.

 

itemArray[indexInsertingAt] = itemArray[indexInsertingFrom];

 

// Шаг 3.

for (int current = indexInsertingFrom; current > indexInsertingAt; current--)

{

   itemArray[current] = itemArray[current - 1];

}

 

// Шаг 4.

itemArray[indexInsertingAt + 1] = temp;

}

 

 

Сортировка выбором

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

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

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

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

На втором проходе мы определяем, что наименьшее зна<