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

Сортировка вставками - простой и достаточно эффективный метод сортировки, при котором элементы данных используются в качестве ключей для сравнения. Алгоритм сначала упорядочивает элементы X[0] и X[1], вставляя X[1] перед X[0], если X[0] > X[1]. Затем оставшиеся элементы данных по очереди вставляются в этот упорядоченный набор. После i-й итерации элемент X[i] оказывается в своей правильной позиции и элементы от X[0] до X[i] уже отсортированы.

После каждой итерации только один элемент помещается в свою правильную позицию.

При сортировке вставками выполняется меньше перестановок, чем в "пузырьковой" сортировке.

Алгоритм:

Пусть в массиве X находится N элементов, тогда для i от 1 до N необходимо выполнить следующие шаги:

1. Запоминаем значение i-ого элемента в переменную temp.
2. Присваиваем j значение элемента слева от текущего (i-ого).
3. До тех пор пока X[j] > temp, сдвигаем X[j] вправо.
4. Вставляем элемент temp в освободившуюся позицию.

После окончания цикла массив отсортирован.

Пример:

Возьмем массив из чисел:

Первый проход:

temp = 2

Вставка:

Второй проход:

temp = 4

Вставка:

Третий проход:

temp = -4

Вставка:

Четвертый проход:

temp = 3

Вставка:

Массив отсортирован

Реализация алгоритма:

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

#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#include <time.h>

template <typename T>
void ISort(T array[] /* Сортируемый массив */, int size /* Размер массива */)
{
 // Переменные циклов
 int i, j; 
 // Временная переменная для хранения текущего элемента
 T temp; 
 
 // Находим позицию очередного элемента и вставляем его туда
 for(i = 1; i < size; i++)
 {
 // Запоминаем текущий элемент
 temp = array[i];
 j = i - 1;
 // Просматриваем элементы слева от текущего
 while(j >= 0 && array[j] > temp)
 {
 // Если находим элемент меньше текущего, то сдвигаем его вправо
 array[j + 1] = array[j];
 j--;
 }
 // Помещаем текущий элемент в освободившуюся позицию
 array[j + 1] = temp;
 }
}

// Функция для вывода массива
template <typename T>
void PrintArray(T array[], int size)
{
 // функция setw(n) создает поле для вывода с шириной n символов
 for(int i = 0; i < size; i++)
 {
 if(i % 5 == 0)
 cout << endl;
 cout << setw(15) << array[i];
 }
 cout << endl;
}

// Тестирование
void main()
{
 // Инициализация генератора случайных чисел
 srand(time(0));
 // Размер массивов
 const N = 10;
 
 int i;
 int a[N];
 float b[N];

 // Инициализация массивов случайными числами в диапазоне от -10 до 10
 for(i = 0; i < N; i++)
 {
 a[i] = rand() % 21 - 10;
 b[i] = rand() / (float)32767 * 20 - 10;
 }

 // Вывод массивов
 cout << "Array A:\n";
 PrintArray(a, N); 

 cout << "Array B:\n";
 PrintArray(b, N); 

 // Сортировка массивов
 ISort(a, N);
 ISort(b, N);

 // Вывод отсортированных массивов
 cout << endl;
 cout << "Array A:\n";
 PrintArray(a, N); 

 cout << "Array B:\n";
 PrintArray(b, N); 
}