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

Элементы массива делятся на уже готовую отсортированную последовательность (слева) и еще необработанные (справа). Сначала левая последовательность содержит один элемент a[0]. Начиная с i=1 (это второй элемент массива), из исходной последовательности извлекается i -ый элемент и вставляется на нужное место готовой последовательности, затем i увеличивается на 1 и т. д.

Пример работы сортировки приведен в таблице 8.1.

Таблица 8.1 – Сортировка методом вставки

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

- выбранный элемент сравнивают с очередным элементом отсортированной части, начиная с j=i-1;

- если выбранный элемент больше или равен a[j], то его включают в отсортированную часть;

- в противном случае a[j] сдвигают на одну позицию.

Процесс поиска подходящего места заканчивается при двух различных условиях:

- если найден элемент a[j]>=a[i];

- достигнут левый конец готовой последовательности.

Ниже приведен соответствующий код:

for(i=1; i<n; i++){

int tmp=a[i]; // запомнили элемент, который будем вставлять

int j=i-1;

while(j>=0 && x<a[j]){ // поиск подходящего места

a[j+1]=a[j]; // сдвиг вправо

j--;

}

a[j+1]=tmp; // вставка элемента

}

Метод сортировки вставками относится к устойчивым.

Обменная сортировка

Элементы, начиная с нулевого и до предпоследнего, сравниваются со всеми, расположенными правее. Если пара сравниваемых элементов «неправильная», они обмениваются местами. Альтернативно можно сравнивать элементы с последнего до второго (с индексом 1) со всеми левыми.

Код обменной сортировки:

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

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

if(a[i]>a[j]) {

int tmp=a[i];

a[i]=a[j];

a[j]=tmp;

}

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