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

Массив разделяется на две части: отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только один первый элемент, а в качестве неотсортированной – все остальные элементы.

Алгоритм будет состоять из (n-1)-го прохода (n – размерность массива), каждый из которых будет включать четыре действия:

взятие очередного i-го неотсортированного элемента и сохранение его в дополнительной переменной;

поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;

сдвиг элементов массива от (i-1)-го до j-го вправо, чтобы освободить найденную позицию вставки;

вставка взятого элемента в найденную позицию.

Псевдокод для этого метода выглядит следующим образом: for i = 0 to n-1

temp = array [i]; for j = i -1 to 0

while (array[j]>temp) { array[j+1]=array[j] j--;

}

array[j+1]=temp;

Программа:

#include <iomanip>

#include <stdlib.h>

void vstavka(int x[], int n); int main()

{const int n =10; int x[n];

for (int i=0; i<n; i++) x[i] = rand() ;

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

cout << setw(6) << x[i];

cout<<endl<< endl; vstavka(x, n);

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

cout << setw(6) << x[i]; //вывод массива cout << endl;

_getch(); }return 0;

void vstavka(int x[], int n)

{

for (int i=1; i< n; i++) //считаем, что до i элементы отсортированы

{int temp = x[i]; //берем очередной элемент int j = i-1;

while ((temp < x[j]) && (j>=0)) // цикл поиска позиции вставки

{ x[j+1] = x[j]; // сдвиг элементов j--;

}

Программирование – лекция 12 (лекции Стрикелевой Л.В.)

25