Наиболее распространены такие методы этого вида сортировки, как сортировка «простыми» вставками; сортировка «бинарными» вставками; сортировка Шелла; сортировка с вычислением адреса.
Суть сортировки «простыми» вставками заключается в последовательном переборе массива a2, …, an с тем, чтобы каждый новый элемент ai вставлять на подходящее место в уже упорядоченной совокупности a1, …, ai-1. Это место определяется последовательным сравнением ai с упорядоченными элементами a1, …, ai-1.
При сортировке «бинарными» вставками место, на которое надо вставить элемент ai в уже упорядоченную совокупность a1, …, ai-1, определяется алгоритмом деления пополам. Таким образом, получается алгоритм сортировки «бинарными» вставками, который понимается как «вставка делением пополам».
Пример 5. Вставить в упорядоченный по возрастанию массив А = {3; 4; 7; 9} новый элемент, равный 5, таким образом, чтобы сохранилась упорядоченность.
Решение
Алгоритм решения задачи следующий:
1. Найти в массиве элемент, больший вставляемого. Для этого следует просмотреть все элементы, начиная с первого. Это элемент а[3] = 7.
|
|
2. Увеличить длину массива на 1. Результат – массив А = {3 4 7 9 X}.
3. Все элементы, стоящие справа от найденного, включая его самого, то есть от 3-го, сдвинуть вправо. Результат – массив А = {3 4 7 7 9}.
4. На освободившуюся позицию, то есть на место элемента а[3], вставить новый элемент, то есть 5. В итоге получаем массив А = {3 4 5 7 9}.
При решении задач такого рода следует учитывать, что, если все элементы массива меньше вставляемого, новый элемент надо вставить в конец массива, и если все элементы массива больше вставляемого, то новый элемент надо вставить в начало массива.
Ниже приведена программа Sort3, реализующая данный алгоритм:
Program Sort3;
Uses CRT;
Var a: array[1..50] of real;
i,j,n,k: integer;
g:real;
{Процедура вывода элементов массива}
Procedure Vyvod(M:Integer; Var V:Mas);
Begin
For i:=1 to M do
Write(V[i]:2,' ':2);
Writeln
End;
Begin
Clrscr;
Writeln('Введите количество элементов массива А');
Readln(n);
Writeln('Введите массив А');
For i:=1 to n do
Read(a[i]);
Writeln;
Writeln('Введите число, которое нужно вставить');
Readln(g);
Writeln('Исходный массив А');
Vyvod(N, A);
{1. Ищем элемент больше вставляемого}
k:=1; { k - индекс сравниваемого элемента}
While (k<=n) and (g>=a[k]) do {если k не превышает n и
вставляемый элемент меньше или равен a[k]}
k:=k+1; {то переходим к следующему элементу}
{2. Увеличиваем длину массива на 1}
n:=n+1;
{3.Сдвигаем элементы, начиная с k-го вправо}
For i:=n downto k+1 do
a[i]:=a[i-1];
{4.В a[k] заносим g}
a[k]:=g;
Writeln('Новый массив А');
Vyvod(N, A);
readkey
End.
Сеанс работы с программой:
Введите количество элементов массива А
Введите массив А
3 4 7 9
Введите число, которое нужно вставить
|
|
Исходный массив А
3.0 4.0 7.0 9.0
Новый массив А
3.0 4.0 5.0 7.0 9.0
Сортировка «слияниями» (Алгоритм фон Неймана)
Суть заключается в упорядочении массива a1, …, an по неубыванию. Метод основан на многократных слияниях уже упорядоченных групп элементов массива. Сначала весь массив рассматривается как совокупность упорядоченных групп по одному элементу в каждом. Слиянием соседних групп получаются упорядоченные группы, каждая из которых содержит два элемента (кроме последней группы, которой не нашлось парной). Далее полученные группы укрупняются тем же способом и т.д. Здесь приходится использовать вспомогательный массив b1, …, bn.
ЛИТЕРАТУРА
1. Абрамов, В. Введение в язык Паскаль / В. Г Абрамов, Н. П. Трифонов, Г. Н. Трифонова. – Москва: Наука, 1988. – 320 с.
2. Алексеев, А. П. Информатика 2007: учебное пособие для студентов вузов, обучающихся по направлению подготовки дипломированных специалистов 210400 (654400) –Телекоммуникации / А. П. Алексеев. –Москва: Солон-Пресс, 2007. – 608 с.
3. Бобровский, С. И. Delphi 7. Учебный курс / С. И. Бобровский. – Санкт- Петербург: Питер, 2008. – 736 с.
4. Бородич, Ю. С. Паскаль для персональных компьютеров / Ю. С. Бородич [и др.]. – Минск: Высшая школа, 1991. – 336 с.
5. Вальвачев, А. Н. Программирование на языке Паскаль для персональных ЭВМ ЕС /А. Н Вальвачев, В. С. Крисевич. – Минск: Вышейшая школа, 1991. – 224 с.
6. Вардомацкая, Е. Ю. Основы информатики и вычислительной техники: курс лекций / Е. Ю. Вардомацкая. – Витебск, 2005. – 130 с.
7. Вардомацкая, Е. Ю. Информатика в прикладных задачах легкой промышленности: пособие / Е. Ю. Вардомацкая, Т. Н. Окишева. – Витебск, 2007.–187 с.
8. Вардомацкая, Е. Ю. Информатика: учебное пособие. В двух частях. Часть I. / Е. Ю. Вардомацкая, Т. Н. Окишева. – Витебск, 2007. – 237 с.
9. Велихов, А. В. Основы информатики и компьютерной техники: учебное пособие для студентов ссузов и вузов по дисциплине "Основы информатики" / А. В. Велихов. – Москва: СОЛОН-ПРЕСС, 2007. – 544 с.
10. Епанешников, А. Программирование в среде Turbo Pascal 7.0 / А. Епанешников, В. Епанешников. – Москва: Диалог – МИФИ, 2000. – 256 с.
11. Морозевич, А. Н. Прикладная информатика: учебное пособие / под общ. ред. А. Н. Морозевича. – Мн.: Выш. школа, 2003. – 335 с.: ил
12. Офицеров, Д. В. Программирование на персональных ЭВМ: практикум: учебное пособие / Д. В. Офицеров, А. Б. Долгий, В. А. Старых; под общ. ред. Д. В. Офицерова. – Минск: Высшая школа, 1993. – 256 с.
13. Попов, В. Б. Паскаль и Дельфи: учебный курс / В. Б. Попов. – Санкт- Петербург: Питер, 2005. – 576 с.
14. Прищепов, М. А. Программирование на языках Basic, и Object Pascal в среде Delphi: учебное пособие / М. А. Прищепов, Е. В. Севернева, А. И. Шакирин; под общ. ред. М. А. Прищепова. – Минск: ТетраСистемс, 2006. – 320 с.
15. Фаронов, В. В. Delphi. Программирование на языке высокого уровня: учебник для вузов / В. В. Фаронов. – Санкт-Петербург: Питер, 2008. – 640 с.