Сортировка методом простого включения (сдвиг-вставка, вставками, вставка и сдвиг)

Хотя этот метод сортировки намного менее эффективен, чем сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

· прост в реализации;

· эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;

· эффективен на наборах данных, которые уже частично отсортированы;

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

· может сортировать массив по мере его получения;

· не требует временной памяти, даже под стек.

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

Рис. 12.3. Демонстрация сортировки по неубыванию методом простого включения

//Описание функции сортировки методом простого включения

void InsertSort (int k,int x[max]) {

int i,j, temp;

for (i=0;i<k;i++) {

//цикл проходов, i - номер прохода

temp=x[i];

//поиск места элемента

for (j=i-1; j>=0 && x[j]>temp; j--)

x[j+1]=x[j];//сдвигаем элемент вправо, пока не дошли

//место найдено, вставить элемент

x[j+1]=temp;

}

}

В отличие от пузырьковой сортировки и сортировки простого выбора, количество сравнений в сортировке вставками зависит от изначальной упорядоченности списка. Если список уже отсортирован, количество сравнений равно n-1 ; в противном случае его производительность является величиной порядка n2.