Примеры. В приведенном ниже примере берется массив случайных чисел; массив сортируется, после чего с применением 2-х методов поиска ( метод половинного деления и метод

В приведенном ниже примере берется массив случайных чисел; массив сортируется, после чего с применением 2-х методов поиска (метод половинного деления и метод простого перебора) осуществляется поиск элемента x.

program pr1;{ программа поиска }

uses crt;

const max=100;

type feld=array[1..max] of integer;

var f:feld;

x:integer;

procedure binaersuchen(x:integer;f:feld);

(* Поиск методом половинного деления.

Массив должен быть отсортирован. *)

var i,rechts,links,mitte:integer;

found:boolean;

begin

links:=1; rechts:=max;

repeat mitte:=(links+rechts) div 2;

if x<f[mitte] then rechts:=mitte-1

else links:=mitte+1;

found:=x=f[mitte];

until found or (links>rechts);

if found

then

begin

write(x:3,'при i=',mitte:3);

writeln(' успешный поиск');

end

else writeln(x:3,' безрезультатный поиск');

end; (* по методу половинного деления *)

procedure feld_anlegen(var f:feld);

var i:integer;

begin

for i:=1 to max do f[i]:=random(99)+1;

end; { заполнение массива }

procedure druckfeld(f:feld);

var i:integer;

begin

for i:=1 to max do write(f[i]:4);

writeln;

end; { поле печати }

procedure ksuchen(x:integer; f:feld);

(* Простой перебор сверху вниз *)

var i:integer;

found:boolean;

begin

i:=1; found:=false;

while (i<=max) and not found do

begin

found:=x=f[i];

inc(i);

end;

if found

then writeln(x:3,'при i=',i-1:3,'элемент найден')

else writeln(x:3,'элемент не найден');

end; (* поиск *)

procedure sortiere(var f:feld);

var i,j,hilf:integer;

begin

(* Здесь просто сравниваются два соседних элемента

и соответствующим образом меняются местами (см.

следующий пример); это простейший, но к сожале-

нию, малоэффективный метод сортировки *)

for i:=1 to max-1 do

for j:=i+1 to max do

if f[j]<f[i] then {f[i] и f[j] меняются местами}

begin

hilf:=f[i];

f[i]:=f[j];

f[j]:=hilf;

end;

end; { сортировка }

begin (********** Исполняемая часть **********)

feld_anlegen(f);

druckfeld(f);

sortiere(f);

druckfeld(f);

writeln('Какое число искать? (Конец=0)');

readln(x);

while x<>0 do begin

ksuchen(x,f);

binaersuchen(x,f);

write('Какое число');

writeln(' искать?');

readln(x);

end;

end.

Центральной проблемой обработки данных является сортировка множества данных. Существует большое число методов сортировки. Следующий пример демонстрирует три элементарных способа поиска, добавления и замены элементов массива с некоторыми их модификациями (heapsort, shellsort, quicksort).

(* Здесь приведено три наиболее распространенных алгоритма,

применяемых при сортировке массива: перебор, добавление,

замена. Реализуется основной принцип сортировки. Каждый

способ допускает модификацию. Они известны

для: перебора как heapsort

добавления shellsort

замены quicksort

Частично отсортированный массив состоит из:

выходной последовательности =

уже отсортированный кусок в начале массива;

исходной последовательности =

не отсортированный кусок в конце массива. *)

program pr2;

{программа сортировки}

uses crt;

const n=1000;

type feld=array[-9..n] of integer;

(* -9 по методу shellsort *)

var a:feld;

anz,nr:integer;

procedure eingabe(var f:feld);

var i:integer;

begin

for i:=1 to anz do f[i]:=random(99)+1;

end; (* Ввод *)

procedure druckfeld(f:feld);

(* Выдаются первые 20 элементов *)

var i:integer;

begin

for i:=1 to 20 do write(f[i]:4); writeln;

end; (* Поле печати *)

procedure austausch(var a:feld);

(* Последовательно сравниваются между собой два соседних

элемента и соответствующим образом меняются местами.

Это самый примитивный способ сортировки (называемый

также пузырьковым методом или методом британского музея).*)

var i,j,x:integer;

begin (*Прямая замена*)

for i:=2 to anz do

for j:=anz downto i do

if a[j-1]>a[j] then (* поменять местами *)

begin

x:=a[j-1];

a[j-1]:=a[j];

a[j]:=x;

end;

end; (* Замена *)

procedure quicksort(var a:feld);

(* Число операций перемены местоположения элементов внутри

массива значительно сократится, если менять местами да-

леко отстоящие друг от друга элементы. Для этого выбира-

ется для сравнения один элемент x (наиболее целесообразно

выбрать элемент из середины массива), отыскивается слева

первый элемент, который не меньше x, а справа первый эле-

мент, который не больше x. Найденные элементы меняются

местами. После первого же прохода все элементы, которые

меньше x, будут стоять слева от x, а все элементы, кото-

рые больше x,- справа от x. С двумя половинами массива

поступают точно так же. Из-за такой рекурсии метод оформ-

ляется как процедура. *)

procedure quicks(links,rechts:integer);

var i,j,x,w:integer;

begin

i:=links; j:=rechts;

x:=a[(links+rechts) div 2];

repeat

while a[i]<x do i:=i+1;

while x<a[j] do j:=j-1;

if i<=j then

begin

w:=a[i]; a[i]:=a[j]; a[j]:=w;

i:=i+1; j:=j-1;

end;

until i>j;

if links<j then quicks(links,j);

if i<rechts then quicks(i,rechts);

end; (* quicks *)

(* Работа с алгоритмом заключается тогда в серии

отдельных обращений *)

begin

quicks(1,anz);

end; (* quicksort *)

procedure einfuegen(var a:feld);

(* Из исходной последовательности берется следующий элемент

и добавляется в выходной массив, причем для него с шагом

1 ищется соответствующее место, начиная с конца массива. *)

var i,j,x:integer;

begin (* Непосредственное добавление *)

for i:=2 to anz do

begin

x:=a[i]; a[0]:=x; j:=i-1;

while x<a[j] do

begin

a[j+1]:=a[j];

j:=j-1;

end;

a[j+1]:=x;

end;

end; (* Добавление *)

procedure shellsort(var a:feld);

(* Алгоритм добавления выполняется t раз с уменьшающимся

каждый раз шагом s[1], s[2],..., s[t] для "следующего

x". Пусть s[1]=anf, а s[t]=1. Для того, чтобы установить

конечную метку для добавления, нужно массив a сначала

продлить на начальную длину шага anf. Итак, нужно задать

type feld = array[-anf..n] of integer;

Для выбора шага рекомендуется, например, 40, 13, 4, 1

или 31, 15, 7, 3, 1 или 9, 5, 4, 1 *)

var s:array[1..4] of integer;

marke,m,t,i,j,k,x:integer;

begin (* shellsort *)

t:=4; s[4]:=1; s[3]:=3; s[2]:=5; s[1]:=9;

for m:=1 to t do

begin

k:=s[m]; marke:=-k;

for i:=k+1 to anz do

begin

x:=a[i];

j:=i-k;

if marke=0 then marke:=-k;

marke:=marke+1;

a[marke]:=x;

while x<a[j] do

begin

a[j+k]:=a[j]; j:=j-k;

end;

a[j+k]:=x;

end;

end;

end; (* shellsort *)

procedure auswahl(var a:feld);

(* Из исходной последовательности выбираются те элементы,

которые следует добавить в конец выходной последователь-

ности *)

var i,j,k,x:integer;

begin (* Прямой выбор *)

for i:=1 to anz-1 do

begin

k:=i; x:=a[i];

for j:=i+1 to anz do

{ В оставшейся части ищется наименьший элемент }

if a[j]<x then

begin

k:=j;

x:=a[j];

end;

a[k]:=a[i]; a[i]:=x;

end;

end; (* Перебор *)

procedure heapsort(var a:feld);

(* При выборе сохраняется появляющаяся по пути информация

о соотношениях между элементами (теряющаяся при прямом

переборе), так что следующий шаг выбора значительно сок-

ращается. Согласно предварительному условию о том, что

место в памяти должно использоваться лишь для хранения

a, весь массив a предварительно упорядочивается таким

образом, чтобы всеми элементами выполнялись следующие

соотношения:

a[i]>=a[2i] для всех i=1,..., n/2

a[i]>=a[2i+1]

Упорядоченный таким образом массив называется "кучей"

(heap - динамическая область). Вначале в состояние "ку-

чи" приводится левая половина массива a. Затем берется

первый элемент справа (поскольку он имеет наибольшее

значение), правая граница сдвигается влево на единицу

и остальной массив вновь отфильтровывается, чтобы опять

получить "кучу". Затем повторяется тот же процесс. Итак,

в отличие простого перебора выходная последовательность

формируется справа. *)

var rechts,links,x:integer;

procedure sieb;

(* Массив a, как и переменные links,rechts

является глобальным *)

var i,j:integer;

begin

i:=links; j:=2*i; x:=a[i];

while j<=rechts do

begin

if j<rechts then

if a[j]<a[j+1] then j:=j+1;

if x<a[j] then

begin

a[i]:=a[j]; i:=j;

j:=2*i;

end

else j:=rechts+1;

end;

a[i]:=x;

end; (* Фильтрация *)

begin (* heapsort *)

rechts:=anz;

for links:=(anz div 2) downto 1 do sieb;

(* В результате получим массив в форме "кучи" *)

(* Теперь начнем сортировать *)

while rechts>1 do

begin

links:=1;

x:=a[links];

a[links]:=a[rechts];

a[rechts]:=x;

rechts:=rechts-1;

sieb;

end;

end; (* heapsort *)

begin (********** Исполняемая часть **********)

write('Сколько элементов (<=1000):');

readln(anz);

eingabe(a);

clrscr;

druckfeld(a);

writeln(anz:50);

writeln ('Какой метод?');

writeln ('1=einfuegen');

writeln ('2=shellsort');

writeln ('3=auswaehlen');

writeln ('4=heapsort');

writeln ('5=austauschen');

writeln ('6=quicksort');

readln(nr);

writeln('Внимание:'); delay(500); write(^g);

case nr of

1: einfuegen(a);

2: shellsort(a);

3: auswahl(a);

4: heapsort(a);

5: austausch(a);

6: quicksort(a);

else writeln('Ничего не нужно'); end;

write(^g);

writeln('Выполнить с сортировкой:');

druckfeld(a);

end.

Здесь будут считаны n чисел и отсортированы в соответствии с таблицей ASCII (таблица кодов).

program pr3;

{ Программа сортировки строк }

uses crt;

const n=10;

type feld=array[1..n] of string[10];

var z:feld;

procedure lies(var a:feld);

var i:integer;

begin

clrscr;

for i:=1 to n do

begin

write('слово: ',i:2,' '); readln(a[i]);

end;

end; (* Считывание *)

procedure drucklinks(f:feld);

(* Выдается массив слов, выравненных по левому краю *)

var i:integer;

begin

for i:=1 to n do writeln(f[i]);

end; (* Печать *)

procedure druckrechts(f:feld);

(* Выдается массив слов, выравненных по правому краю *)

var i:integer;

begin

for i:=1 to n do writeln(f[i]:10);

end; (* Печать *)

procedure sortieren(var a:feld);

var i,j:integer;

x:string[10];

begin (* Прямой перебор *)

for i:=2 to n do

for j:=n downto i do

if a[j-1]>a[j] then (* Перемена местами *)

begin

x:=a[j-1];

a[j-1]:=a[j];

a[j]:=x;

end;

end; (* Сортировка *)

begin (********** Исполняемая часть **********)

lies(z);

writeln('до сортировки:');

drucklinks(z);

sortieren(z);

writeln(^j'после сортировки:');

druckrechts(z);

end.

В завершении нашего обзора сравним эффективность описанных методов сортировки.

В качестве показателей для оценки того или иного метода в них используются количество сравнений и количество перемещений элементов в ходе сортировки. Однако эти характеристики не учитывают затрат времени на другие операции, такие, как управление циклами и др. Очевидно, что критерием для сравнения различных методов является время, затрачиваемое на сортировку. Данные о времени выполнения процедур сортировки получены Н.Виртом. Конечно, современные компьютеры работают значительно быстрее чем тогда, когда были проведены расчеты. В тоже время относительные показатели различных методов в целом не изменились. В табл.1 представлены относительные характеристики 9 вариантов методов сортировки, полученные на основе результатов, приведенных Н.Виртом.

Метод сортировки	Упорядоченный массив	Случайный массив	Упорядоченный в обратном порядке массив
Сортировка простыми вставками	2.4 4.6	6.1 24.1	19.0 76.6
Сортировка выбором	97.8 338.4	8.5 32.6	18.8 72.3
“Пузырьковая” сортировка	108.0 433.0	17.1 67.6	40.3 160.3
Усовершенствованная “пузырьковая” сортировка	1.0 1.6	18.4 71.1	44.5 176.8
“Шейкер” – сортировка	1.0 1.8	16.0 60.7	43.8 176.2
Сортировка методом Шелла	11.6 23.2	2.1 5.8	4.2 13.3
Пирамидальная сортировка	23.2 50.1	1.8 4.0	2.8 6.1
Сортировка слиянием	19.8 46.8	1.7 4.0	2.7 6.3
Быстрая сортировка	6.2 18.6	1.0 2.4	1.0 2.1

Табл.1 Сравнительные характеристики методов сортировки

Значение, равное 1, в каждой колонке соответствует наименьшему времени, затрачиваемому на сортировку массива указанным методом. Все остальные значения в столбце рассчитаны относительно минимальному времени.

Верхнее число в каждой колонке дано для массива из 256, а нижнее - для 512 элементов. Еще раз заметим, что современные компьютеры такие массивы отсортируют очень быстро, но в данном случае нас интересуют относительные показатели различных методов.

Приведенные данные демонстрируют явное различие методов n² и log₂n.

Из табл.1 видно, что наилучшим среди простых методов является сортировка вставками, среди усовершенствованных - быстрая сортировка. Н.Вирт отмечает также следующее:

n “пузырьковая” сортировка является наихудшим среди всех сравниваемых методов. Ее Улучшенный вариант – “шейкер” - сортировка - все-таки хуже, чем сортировка простыми вставками и сортировка выбором.

n особенностью быстрой сортировки является то, что она сортирует массив с элементами, расположенными в обратном порядке практически так же, как и отсортированный в прямом порядке. Следует добавить, что приведенные результаты были получены при сортировке числовых массивов. Если же значением элементов массива являются данные типа “запись”, в которых сопутствующие поля (компоненты) занимают в семь раз больше памяти, чем числовое поле, по которому проводится сортировка, то картина изменится на следующую.

Метод сортировки	Упорядоченный массив	Случайный массив	Упорядоченный в обратном порядке массив
Сортировка простыми вставками	2.4 9.2	6.1 18.8	19.0 58.1
Сортировка выбором	97.8 109.4	8.5 10.1	18.8 38.6
“Пузырьковая” сортировка	108.0 122.0	17.1 53.5	40.3 151.3
Усовершенствованная “пузырьковая” сортировка	1.0 1.0	18.4 54.0	44.5 155.7
“Шейкер” – сортировка	1.0 1.0	16.0 51.2	43.8 155.6
Сортировка методом Шелла	11.6 37.2	2.1 6.2	4.2 11.8
Пирамидальная сортировка	23.2 52.8	1.8 4.1	2.8 6.1
Сортировка слиянием	19.8 39.2	1.7 3.2	2.7 5.0
Быстрая сортировка	6.2 11.0	1.0 2.3	1.0 2.0

Табл.2 Сравнительные характеристики методов сортировки массивов данных типа “запись”

Верхнее число в каждой колонке относится к сортировке числового массива, а нижнее - массива данных типа “запись” (число элементов в обоих случаях 256).

Видно, что

1.Сортировка выбором дает существенный выигрыш и оказывается лучшим из простых методов.

2. “Пузырьковая” сортировка по-прежнему является наихудшим методом.

Быстрая сортировка даже укрепила свою позицию в качестве самого быстрого метода и оказалась действительно лучшим алгоритмом сортировки

Дата добавления: 2014-11-09