(495) 240-82-80ПН-СБ с 10:00 до 18:00
We speak English

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

Принцип метода:

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

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

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

Программа, реализующая рассмотренный алгоритм, будет иметь следующий вид:

ClrList↵
"Введите длину массива " : ? →N ↵
For 1→I To N ↵
"Введите" : I
"-й элемент массива" ↵
?→List 1 [ I ] ↵
Next ↵
List 1
For 2→I To N ↵
List 1 [ I ] →В↵
1→J ↵
While B> List 1 [ J ] ↵
J+1→J ↵
WhileEnd↵
For I-1→K To J Step -1 ↵
List 1 [ K ] → List 1 [ K+1 ] ↵
Next ↵
B →List 1 [ J ] ↵
Next ↵
List 1