Обменные сортировки
Суть обменных сортировок заключается в следующем. Сначала последовательно просматриваются элементы a1, …, an и находится наименьшее i, такое, что ai>ai+1. Затем элементы ai и ai+1 меняются местами, и просмотр возобновляется с ai+1 элемента, и т.д. Тем самым, наибольшее число передвигается на последнее место. Следующие просмотры начинаются опять сначала, уменьшая на единицу количество просматриваемых элементов. Массив будет упорядочен после просмотра, в котором участвовали только первый и второй элементы. Процесс сортировки по убыванию будет аналогичен.
В пределах этого вида можно выделить такие методы сортировок, как метод «пузырька»; метод улучшенной «пузырьковой» сортировки; метод быстрой сортировки.
Для сортировки методом «пузырька»массив последовательно просматривается несколько раз. Каждый просмотр состоит из сравнения каждого элемента массива ai с элементом ai+1 и обмена этих двух элементов, если они расположены не в нужном порядке.
Пример 1 . Пусть задан массив А, состоящий из элементов: А={25; 57; 48; 37; 12; 92; 86; 33}. Упорядочить его по возрастанию значений элементов.
Решение
На первом просмотре делаем следующие сравнения:
а1 с а2 (25 и 57) – нет обмена;
а2 с а3 (57 и 48) – обмен;
а3 с а4 (57 с 37) – обмен;
а4 с а5 (57 с 12) – обмен;
а5 с а6 (57 с 92) – нет обмена;
а6 с а7 (92 с 86) – обмен;
а7 с а8 (92 с 33) – обмен.
Таким образом, после первого просмотра элементы массива будут располагаться в таком порядке:
25 48 37 12 57 86 33 92.
После первого просмотра наибольший элемент 92 находится в нужной позиции. В общем случае элемент а(n-i+1) будет находиться в нужной позиции после i-той итерации. Этот метод называется «методом пузырька» потому, что каждое число, словно пузырек, медленно всплывает вверх в нужную позицию.
После второго просмотра получим последовательность:
25 37 12 48 57 33 86 92.Элемент 86 на нужном месте.
Поскольку каждая итерация помещает новый элемент в нужную позицию, то для сортировки некоторого массива, состоящего их n элементов, требуется не более n-1 итерации. Полный набор итераций для массива А выглядит следующим образом:
| 1-ая итерация | 92; | |||||||
| 2-ая итерация | 92; | |||||||
| 3-ая итерация | 92; | |||||||
| 4-ая итерация | 92; | |||||||
| 5-ая итерация | 92; | |||||||
| 6-ая итерация | 92; | |||||||
| 7-ая итерация | 92. |
Метод улучшенной «пузырьковой» сортировки основан на методе «пузырька» с той лишь разницей, что количество итераций меньше. Рассмотрим его на примере.
Пример 2. Упорядочим по возрастанию методом «пузырька» массив А, представленный в примере 13.1, а также проиллюстрируем метод улучшенной «пузырьковой» сортировки на примере упорядочивания данного массива по убыванию.
Решение
Создаем вспомогательные массивы В и С. В массиве В будут сохраняться результаты сортировки по убыванию, в массиве С – по возрастанию. Исходный массив А и отсортированные массивы В и С выведем на экран, используя подпрограмму-процедуру.
Program Sort1;
Uses CRT;
Type Mas=Array[1..50] Of Integer;
Var A,B,C:Mas;
i,j,p,N:integer;
{Процедура вывода элементов массива}
Procedure Vyvod(M:Integer; Var V:Mas);
Begin
For i:=1 to M do
Write(V[i]:2,' ':2);
Writeln
End;
Begin
Writeln('Введите количество элементов массива А');
Readln(N);
Writeln('Введите массив А');
For i:=1 to N do
Readln(A[i])
Writeln('Исходный массив');
Vyvod(N,A);
{Сортировка массива по возрастанию методом «пузырька»}
C:=A;
For i:=1 to N do
For j:=1 to N-1 do
If C[j]>C[j+1] Then
Begin
P:=C[j];
C[j]:=C[j+1];
C[j+1]:=P
End;
Writeln('Отсортированный по возрастанию массив А');
Vyvod(N,C);
{Сортировка массива по убыванию методом улучшенной «пузырьковой» сортировки. При использовании метода улучшенной «пузырьковой» сортировки i изменяется от 1 до n-1, j от 1 до n-i}
B:=A;
For i:=1 to N-1 do
For j:=1 to N-i do
If B[j]<B[j+1] Then
Begin
P:=B[j];
B[j]:=B[j+1];
B[j+1]:=P
End;
Writeln('Отсортированный по убыванию массив А');
Vyvod(N,B);
Readln
End.
Сеанс работы с программой:
Введите количество элементов массива А
Введите массив А
25 57 48 37 12 92 86 33
Результаты:
Исходный массив А
25.0 57.0 48.0 37.0 12.0 92.0 86.0 33.0
Отсортированный по возрастанию массив А
12.0 25.0 33.0 37.0 48.0 57.0 86.0 92.0
Отсортированный по убыванию массив А
92.0 86.0 57.0 48.0 37.0 33.0 25.0 12.0
Метод быстрой сортировки является еще одной реализацией обменных сортировок. Пусть имеется массив А, состоящий из N элементов. Для обозначения индексов элементов воспользуемся двумя переменными – i и j. Полагаем i=1, j=n. Если ai меньше aj, то j уменьшаем на единицу и снова сравниваем ai и aj. После первой перестановки i увеличивается на единицу, и выполняется еще одна перестановка. Затем j уменьшаем на единицу. Процесс сравнения продолжается до тех пор, пока исходный набор не будет упорядочен по возрастанию.
Рассмотрим этот метод на примере сортировки строк.
Пример 3. Имеется список бригады рабочих из 10 человек. Упорядочить его по возрастанию методом быстрой сортировки и вывести на экран.
Решение
Обозначим через переменную w строку длиной не более 20 символов (фамилия рабочего), v – массив из 10 элементов (количество рабочих), p – вспомогательная переменная строкового типа для перестановки элементов, i и j – индексы строк в массиве. Программа на языке Паскаль представлена ниже.
Program Sort_String;
Uses Crt;
Type W=String[20];
V=Array[1..10] Of W;
Var Fio:V;
I,J:Integer;
P:W;
Begin
Clrscr;
Writeln('Ввод списка бригады');
For I:=1 To 10 Do
Begin
Write(i,' рабочий - ');
Readln(FIO[I])
End;
For I:=1 To 10 Do {Метод быстрой сортировки}
For J:=10 Downto 1 Do
If (FIO[I]>FIO[J]) And (I<=J) Then
Begin
P:=FIO[I];
FIO[I]:=FIO[J];
FIO[J]:=P;
End;
Writeln(‘Отсортированный список бригады’);
For I:=1 To 10 Do
Writeln(Fio[I]);
Readln
End.
Сортировки выбором
Наиболее распространены следующие методы этого вида сортировки: с поиском минимального значения; с использованием бинарных деревьев; с использованием метода «турнира с выбыванием»; «пирамидальная» сортировка.
Рассмотрим подробнее первый метод этого вида сортировки – с поиском минимального значения. Суть его заключается в следующем. Сначала в массиве необходимо найти минимальный элемент, затем поменять его местом с первым, затем в усеченном (исключая первый элемент) массиве опять найти минимальный элемент и поставить его на второе место и так далее.
Пример 4.Отсортировать по возрастанию массив элементов 1 3 0 9 2.
Решение
Процесс сортировки выбором по методу поиска минимального значения пройдет через следующие шаги:
| 0: | min=a[3]=0 | переставляем a[1] < -- > a[3] | |||||
| 1: | 0│ | min=a[3]=1 | переставляем a[2] < -- > a[3] | ||||
| 2: | 1│ | min=a[5]=2 | переставляем a[3] < -- > a[5] | ||||
| 3: | 2│ | min=a[5]=3 | переставляем a[4] < -- > a[4] | ||||
| 4: | Готово |
Здесь знак │ отделяет отсортированную часть массива от несортированной. Ниже приводится программа, реализующая данный метод.
Program Sort2;
Uses Crt;
Var A: Array[1..50] Of Real;
I,J,N,K: Integer;
Min,W: 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('Исходный массив А');
Vyvod(N, A);
{Сортировка массива выбором}
For i:=1 to n do
Begin
min:=a[i]; k:=i;
For j:=i+1 to n do
If a[j]<=min then
Begin min:=a[j]; k:=j end;
{Перестановка i-го и min элементов}
w:=a[i];
a[i]:=a[k];
a[k]:=w;
End;
Writeln('Отсортированный массив А');
Vyvod(N, A);
readkey
End.
Сеанс работы с программой:
Введите количество элементов массива А
Введите массив А
1 3 0 9 2
Исходный массив А
1.0 3.0 0.0 9.0 2.0
Отсортированный массив А
0.0 1.0 2.0 3.0 9.0
Аналогичным данному методу и одним из самых простых методов сортировки является метод прямого выбора. Для его реализации выбирается максимальный элемент. Выбранный элемент меняется местами с последним элементом; процесс повторяется с оставшимися n-1, n-2 элементами и т.д., пока не останется один, самый малый по значению элемент.
Сортировка «вставками»
Наиболее распространены такие методы этого вида сортировки, как сортировка «простыми» вставками; сортировка «бинарными» вставками; сортировка Шелла; сортировка с вычислением адреса.
Суть сортировки «простыми» вставками заключается в последовательном переборе массива 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 с.
Дата добавления: 2019-02-07; просмотров: 586;