2015-09-06
183
На каждом шаге алгоритма сортировки вставкой выбирается один из элементов входных данных и вставляется в нужную позицию в уже отсортированном списке до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен. Можно использовать практически любой алгоритм выбора. Обычно с целью получения устойчивого алгоритма сортировки элементы вставляются по порядку их появления во входном массиве.
Листинг 5.1. Программа демонстрирует метод сортировки вставкой массива из 10 целых элементов.
//L5_1.cpp
#include <iostream>
using namespace std;
int main()
{
setlocale(LC_CTYPE,"russian");
int A[10], n=10, i, j, key;
for(i=0; i<n; i++)
{
cout<<"Введите А("<<i+1<<")=";
cin>>A[i];
}
cout<<"Исходный массив\n";
for(i=0; i<n; i++)
cout<<A[i]<<" ";
cout<<endl;
for(i = 1; i<n; i++)
{
key = A[i];
j = i - 1;
while (j >= 0 && A[j] > key)
{
A[j + 1] = A[j];
j = j - 1;
A[j + 1] = key;
}
}
cout<<"Полученный массив\n";
for(i=0; i<n; i++)
cout<<A[i]<<" ";
cout<<endl;
return 0;
}
Результат работы программы листинга 5.1 приведен на рис. 5.1:
Рис. 5.1. Результат работы программы листинга 5.1
