double arrow

Сортировка «вставками»

Наиболее распространены такие методы этого вида сортировки, как сортировка «простыми» вставками; сортировка «бинарными» вставками; сортировка Шелла; сортировка с вычислением адреса.

Суть сортировки «простыми» вставками заключается в последовательном переборе массива 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 с.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: