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