Сортировка массивов
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
3 3 17 9 12 12 11 9 2 5 Число итераций =8
После того как левая часть массива отсортирована, опять рекурсивно вызывается процедура, в которой определяется середина данной части массива, и выполняется обмен элементов. Массив становится таким:
20 19 19 19 18 5 17 10 1 3 3 17 9 12 12 11 9 2 5 Число итераций =9
20 19 19 19 18 5 17 10 1 3 3 17 9 12 12 11 9 2 5 Число итераций =10
Далее опять рекурсивно вызывается процедура для сортировки, пока в каждой из частей останется по одному элементу.
Затем рекурсивно вызывается процедура для аналогичной сортировки правой части (с 7-го по 13-й элемент). Результат последовательных этапов сортировки массива отображается так:
20 19 19 19 18 5 17 10 1 3 3 17 9 12 12 11 9 2 5 Число итераций=11
20 19 19 19 18 17 17 10 1 3 3 5 9 12 12 11 9 2 5 Число итераций =12
20 19 19 19 18 17 17 10 1 3 3 5 9 12 12 11 9 2 5 Число итераций =13
20 19 19 19 18 17 17 109 3 3 5 9 12 12 11 1 2 5 Число итераций=14
20 19 19 19 18 17 17 10 9 11 3 5 9 12 12 3 1 2 5 Число итераций =15
20 19 19 19 18 17 17 10 9 11 12 5 9 12 3 3 1 2 5 Число итераций =16
20 19 19 19 18 17 17 109 11 12 12 9 5 3 3 1 2 5 Число итераций=17
20 19 19 19 18 17 17 10 9 11 12 12 9 5 3 3 1 2 5 Число итераций=18
20 1919 19 18 17 17 12 9 11 12 10 9 5 3 3 1 2 5 Число итераций =19
20 19 19 19 18 17 17 12 12 11 9 10 9 5 3 3 1 2 5 Число итераций=20
20 19 19 19 18 17 17 12 12 11 9 109 5 3 3 1 2 5 Число итераций=21
20 19 19 19 18 17 17 12 12 11 9 10 9 5 3 3 1 2 5 Число итераций =22
20 19 19 19 18 17 17 12 12 11 10 9 9 5 3 3 1 2 5 Число итераций=23
20 19 19 19 18 17 17 12 12 11 10 9 9 5 5 3 1 2 3 Число итераций=24
20 19 19 19 18 17 17 12 12 11 10 9 9 5 5 3 1 2 3 Число итераций =25
19 19 19 18 17 17 12 12 11 109 9 5 5 3 1 2 3 Число итераций =26
20 19 19 19 18 17 17 12 12 11 10 9 9 5 5 3 3 2 1 Число итераций =27
По последнему значению A определяем, что для данного массива сортировка по невозрастанию выполняется за 27 итераций.
Как видно из приведенных примеров, алгоритм "быстрой" сортировки дает лучшие результаты, чем пузырьковый метод, однако следует учесть, что в некоторых случаях это преимущество снижается. Например, если применить эту программу для сортировки массива М, элементы которого имеют значения 29,27,24,3,23,19,19,18,1,17,15,13,1,0,9,9,8,6,6,5, то сортировка будет выполнена за 28 итераций, т. е. время процесса и число итераций даже увеличатся, несмотря на то, что исходный массив в большей степени упорядочен, в то время как сортировка линейным методом - 190 итераций для обоих массивов, пузырьковым - 166 (для первого массива- 170).
.5 БИНАРНЫЙ ПОИСК В УПОРЯДОЧЕННЫХ МАССИВАХ
Едва ли не самой внушительной демонстрацией эффективности применения компьютеров являются задачи, в которых осуществляется поиск информации в некотором списке. Ранее в упражнениях 2 - 4 мы использовали метод линейного (последовательного) поиска, суть которого заключается в последовательном просмотре всего списка элементов массива и сравнении значения очередного элемента с заданным для поиска. Этот метод поиска вполне эффективен на неупорядоченных массивах данных, а на предварительно отсортированных массивах значительно эффективнее выполнять поиск другими методами. Например, метод линейного поиска практически бесполезен при поиске информации в массивах большого размера, так как занимает много времени.
Одним из эффективных методов поиска в больших отсортированных массивах является бинарный поиск, или поиск методом деления пополам. В основе этого метода лежит идея целенаправленных последовательных догадок о предполагаемом местоположении искомого элемента. Такой метод можно проиллюстрировать на примере шуточного совета, как поймать в Африке льва: "Для начала разделим Африку пополам. Ясно, что лев находится только в одной половине. Та половина, в которой находится лев, снова делится пополам и т. д. Площадь Африки приблизительно 30 млн. км2. Следовательно, после примерно 45 делений мы получим площадку, не превышающую 1 м2. Теперь на такой площадке льва поймать нетрудно".
Аналогично выполняется бинарный поиск элемента в упорядоченном массиве. Вместо просмотра подряд всех элементов массива делим его пополам. Так как массив отсортирован, то, сравнивая искомый элемент со значением среднего элемента массива, мы в состоянии сделать вывод, может ли быть элемент с таким значением в массиве и в какой половине он находится, т. е. определить область дальнейшего поиска. Затем делится пополам та часть массива, в которой находится элемент, и так до тех пор, пока рассматриваемая часть массива получится состоящей из одного элемента.
Глава 2. ПРАКТИЧЕСКАЯ ЧАСТЬ
Задача 1. Составить программу, которая выводит несортированный массив целых чисел на экран, затем выполняет его сортировку методом линейной сортировки по невозрастанию и выводит отсортированный массив на экран.
program Sort_Lin;
crt;
Count=20;
M:array [1..Count] of byte=(9,11,12,3,19,1,5,17,10,18,3,19,17,9, 12,20,20,19,2,5);
I, J, N, L: Byte;
A: integer;;(Исходный массив:);I:=1 to Count do Write( , M[I]); Writeln;:=0;I:=1 to Count-1 do
for J:=I+1 to Count do
begin
A:=A+1;
if M[I] < M[J] then
begin
N:=M[I];
M[I]:=M[J];
M[J]:=N;
end;
for L:=1 to Count do Write( , M[L]); Writeln(Число итераций=, A);
end;;.
Задача 2. Составить программу, которая выводит несортированный массив целых чисел на экран, затем выполняет его сортировку методом пузырька по невозрастанию и выводит отсортированный массив на экран.
program Sort_Puz;
uses;
const
Count=10;
M:array [1..Count] of byte=(9, 11, 12, 3, 19, 1, 5, 17, 10, 18);
var
I, J, K, L: Byte;
A: integer;
ClrScr;
Writeln(Исходный массив);
for I:=1 to Count do Write(M[I], ); Writeln;
A:=0;
for I:=2 to Count do
begin
for J:=Count downto I do
begin
A:=A+1;
if M[J-1]<M[J] then
begin
K:=M[J-1];
M[J-1]:=M[J];
M[J]:=K;
for L:=1 to Count do Write( , M[L]);(Число итераций =, A);
end;
end;
end;;.
Задача 3. Составить программу, которая выводит не