Работа 3.6 Упр.27 ГДЗ Семакин 10 класс (Информатика)

Задача

Сортировка вставками. Дана последовательность чисел $$a_1, a_2, \ldots, a_n$$. Требуется переставить числа в порядке возрастания. Делается это следующим образом. Пусть $$a_1, a_2, \ldots, a_i$$ — упорядоченная по неубыванию последовательность, т. е. $$a_1 \leq a_2 \leq \ldots \leq a_i$$. Берётся следующее число $$a_{i+1}$$ и вставляется в последовательность так, чтобы новая последовательность была также возрастающей. Процесс производится до тех пор, пока все элементы от $$i+1$$ до $$n$$ не будут перебраны. Примечание. Место помещения очередного элемента в отсортированную часть найти с помощью двоичного поиска. Двоичный поиск оформить в виде отдельной функции.

Подробный ответ

Нужно отсортировать массив по неубыванию методом вставок. Для каждого очередного элемента ищем место вставки в уже отсортированной части массива с помощью двоичного поиска, а затем сдвигаем элементы вправо и вставляем число на найденное место.

Ниже приведён вариант программы на Pascal.

var
a: array[1..100] of integer;
n, i, j, l, r, m, x: integer;
function BinSearch(l, r, x: integer): integer;
begin
while l <= r do
begin
m := (l + r) div 2;
if a[m] < x then
l := m + 1
else
r := m — 1;
end;
BinSearch := l;
end;
begin
read(n);
for i := 1 to n do
read(a[i]);
for i := 2 to n do
begin
x := a[i];
j := BinSearch(1, i — 1, x);
for m := i downto j + 1 do
a[m] := a[m — 1];
a[j] := x;
end;
for i := 1 to n do
write(a[i], ‘ ‘);
end.

Функция BinSearch возвращает позицию, на которую нужно вставить элемент x в отсортированную часть массива a[1..i-1]. После этого элементы сдвигаются вправо, и элемент вставляется на своё место.