Void main()

{ int A[] = {4, 7, 3, 4, 8, 2, 3, 6, 6, 4, 9, 2, 3};

int n = sizeof(A) / sizeof(int);

InsertSort(a, n);

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

cout<<A[i]<<' ';

}

Алгоритм эффективен на небольших наборах данных (на наборах данных до десятков элементов может оказаться лучшим) и на наборах данных, которые уже частично отсортированы.

Это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы).

Ввиду своих особенностей хорош для списков. 

Не требует дополнительной памяти.

Общее быстродействие - O(n²), но ввиду простоты метода является наиболее быстрым для малых (12-20 элементов) массивов.  

Если использовать двоичный поиск для определения места элемента, то трудоемкость алгоритма составляет n * log(n). Однако эта трудоемкость не учитывает затрат на перемещение элементов при сдвиге.

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

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

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

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

Здесь группа  это последовательность элементов, номера которых образуют арифметическую прогрессию с разностью h (шаг группы).

В начале процесса упорядочения выбирается первый шаг группы h₁, который зависит от размера таблицы.

Шелл предложил брать  h₁ = n / 2, h_i = h_{i -1} / 2.

В более поздних работах Хиббард показал, что для ускорения процесса целесообразно определить шаг h₁ по формуле: h₁ = 2^k + 1, где 2^k < n <= 2^{k + 1}.

После выбора h₁ методом вставки упорядочиваются группы, содержащие элементы с номерами позиций:    

i, i + h₁, i + 2 * h₁, . . . , i + m_i * h₁

где i = 1, 2, . . . , h₁;

m_i - наибольшее целое, удовлетворяющее неравенству i + m_i * h_i <= n

Затем выбирается шаг h₂ < h₁ и упорядочиваются группы, содержащие элементы с номерами позиций

i, i + h₂, . . . , i + m_i * h₂

Эта процедура со все уменьшающимися шагами продолжается до тех пор, пока очередной шаг h_i не станет равным единице (h₁ > h₂ > ... > h_i).

Этот последний этап представляет собой упорядочение массива методом вставки.

Так как исходная таблица упорядочивалась отдельными группами с последовательным объединением этих групп, то общее количество сравнений меньше, чем n /4, требуемое при методе вставки.

Число операций сравнения пропорционально n*(log₂(n))²

Пример. Элементы одной группы выделены одинаковым цветом. Первое значение h равно 10/2=5.

На каждом шаге оно уменьшается вдвое. Элементы, входящие в одну группу, сравниваются и если значение элемента, стоящего левее того, с которым он сравнивается, оказывается больше (сорт. по возрас.), тогда они меняются местами. Так, элементы путем внутригрупповых перестановок постепенно становятся на свои позиции, и на посл. шаге (d = 1) сортировка сводится к проходу по одной группе, включающей в себя N элементов.

#include <iostream>

using namespace std;

int i, j, n, d, c;

void Shell(int A[], int n) //сортировка Шелла

{ d = n; d = d / 2;

while (d > 0)

{ for (i = 0; i < n - d; i++)

{ j = i;

while (j >= 0 && A[j] > A[j + d])

{ c = A[j];

A[j] = A[j + d];

A[j + d] = c;

j--;

}

}

d = d / 2;

}

}