Программа методом двоичного включения - Pascal ABC

Узнай цену своей работы

Формулировка задачи:

Подскажите, пожалуйста Использование идеи двоичного поиска позволяет значительно улучшить ал*горитм сортировки массива методом простого включения. Учитывая, что готовая последовательность, в которую надо вставить элемент, является упорядоченной, можно методом деления пополам определять позицию включения нового элемен*та в нее. Такой модифицированный алгоритм сортировки называется методом дво*ичного включения. Написать программу, реализующую этот метод.

Решение задачи: «Программа методом двоичного включения»

textual
Листинг программы
var a:array[1..100] of integer;
    n,i,j,m,l,r,x:integer;
begin
write('Введите размер массива от 2 до 100 n=');
readln(n);
randomize;
writeln('Исходный массив');
for i:=1 to n do
 begin
  a[i]:=random(100);
  write(a[i]:4);
 end;
writeln;
for i:=2 to n do
 begin
  x:=a[i];//запомним очередной элемент
  l:=1; //девый край
  r:=i; //правый край
  while l<r do  //пока левый меньше правого
   begin
    m:=(l+r) div 2; //середина
    if a[m]<x then l:=m+1 else r:=m; //если средний меньше текущего
                                    //левый ставим впереди среднего,
                                    //иначе правый в середину
   end;
  for j:=i downto r+1 do a[j]:=a[j-1]; //сдвигаем отсортированную часть на 1 вправо
  a[r]:=x;//текущий ставим в позицию правого
 end;
writeln('Отсортированный массив');
for i:=1 to n do
write(a[i]:4);
end.

Объяснение кода листинга программы

  1. Создается переменная a типа array[1..100] of integer. Это означает, что будет создан массив из 100 чисел типа integer.
  2. Задается переменная n, которая будет использоваться для хранения размера массива.
  3. Вызывается функция randomize, чтобы инициализировать генератор случайных чисел.
  4. Выводится сообщение Введите размер массива от 2 до 100 n=.
  5. Пользователю предлагается ввести размер массива от 2 до 100.
  6. Введенное значение сохраняется в переменной n.
  7. Генератор случайных чисел инициализируется.
  8. Выводится сообщение Исходный массив.
  9. Запускается цикл for, который выполняется n раз.
  10. Внутри цикла создаются переменные i, j, m, l, r, x.
  11. Переменная i инициализируется значением 1.
  12. Переменная j инициализируется значением n+1.
  13. Переменная m инициализируется как (i+j) деленное на 2.
  14. Переменная l инициализируется как min(i, m).
  15. Переменная r инициализируется как max(i, m).
  16. Запускается вложенный цикл while, который выполняется, пока l меньше r.
  17. Внутри вложенного цикла вычисляется средний элемент массива, сохраняя его в переменной m.
  18. Проверяется, меньше ли средний элемент текущего элемента. Если это так, то l устанавливается равным m+1. Если же средний элемент больше текущего, то r устанавливается равным m.
  19. l и r сдвигаются вправо на 1, используя сдвиг a[j]=a[j-1].
  20. В конце вложенного цикла while переменная a[r] устанавливается равной текущему элементу.
  21. Выводится сообщение Отсортированный массив.
  22. Запускается еще один цикл for, который выполняется от 1 до n.
  23. Внутри цикла выводится значение a[i] с помощью функции write.
  24. Цикл for завершается.
  25. Программа завершается.

Оцени полезность:

5   голосов , оценка 4.2 из 5
Похожие ответы