Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Алгоритмы сортировки массива целых чисел - файл 1.doc


Алгоритмы сортировки массива целых чисел
скачать (75 kb.)

Доступные файлы (1):

1.doc75kb.09.12.2011 05:57скачать

содержание
Загрузка...

1.doc

Реклама MarketGid:
Загрузка...
Сортировка «Пузырьком»


P:=0




i:=2..k






_


a:=y[i-1]
+




y[i-1]:=y[i]



y[i]:=a





p:=1




_

+

Описание алгоритма:

За каждый проход последовательно сравниваются два соседних элемента и, если порядок в паре неверный, выполняется перестановка элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что перестановки больше не нужны, что означает — массив отсортирован.

^ Program Massiv;

Type mass=array [1..100] of integer;

Var i,b,n: integer; x: mass;

Procedure Puzyrek (k:integer; var y:mass);

Var i,j,m,a,p: integer;

begin

Repeat

p:=0;

For i:=2 to k do

If y[i-1]>y[i] then begin a:=y[i-1];

y[i-1]:=y[i];

y[i]:=a;

p:=1;

end;

Until (p=0);

end;

Begin

Write('n='); readln(n);

b:=2*n;

For i:=1 to n do begin

x[i]:=random(b);

writeln('x[',i,']=',x[i]);

end;

writeln;

Puzyrek (n,x);

For i:=1 to n do writeln('x[',i,']=',x[i]);

end.

Сортировка методом «Последовательных перестановок»




i:=1..(n-1)





m:=z[i]



k:=1

j:=i+1..n

m:=z[j]

k:=j

a:=z[i]

z[i]:=m

z[k]:=a



Описание алгоритма:

На первом проходе находим элемент с минимальным значением среди всех элементов массива и меняем его местами с первым неотсортированным элементом. На последующих проходах сортируем «хвост» массива: находим минимальное значение среди неотсортированных элементов, то есть исключив из рассмотрения уже отсортированные, и также меняем его местами с первым неотсортированным элементом.

^ Program Massiv;

Type mass=array [1..100] of integer;

Var i,b,n: integer; x,a,c: mass;

Procedure Perestanovka (n:integer; var z:mass);

Var i,j,m,a,k: integer;

begin

For i:=1 to (n-1) do begin

m:=z[i];

k:=i;

For j:=i+1 to n do begin

If z[j]<m then begin

m:=z[j];

k:=j;

end;

end;

a:=z[i];

z[i]:=m;

z[k]:=a;

end;

end;

Begin

Write('n='); readln(n);

b:=2*n;

For i:=1 to n do begin

x[i]:=random(b);

writeln('x[',i,']=',x[i]);

end;

writeln;

Perestanovka (n,x);

For i:=1 to n do writeln('x[',i,']=',x[i]);

end.

«Гномья» сортировка




i:=1





+


a:=x[i+1]

i:=i+1



x[i+1]:=x[i]

x[i]:=a

i:=i-1





i:=2




+

Описание алгоритма:

Гном смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Если нет предыдущего горшка (назад идти некуда), то он шагает вперёд; если нет следующего горшка (вперёд идти некуда), то сортировка закончена.

^ Program Gnom;

uses dos;

Type mass=array [1..100] of integer;

Var i,b,n,a: integer; x: mass;

start:longint;

Function GetTim:longint;

var h,m,s,ss :word;

begin

GetTime(h,m,s,ss);

GetTim:=ss+100*s {+100*60*m}

end;

Begin

Write('n='); readln(n);

b:=2*n;

For i:=1 to n do begin

x[i]:=random(b);

writeln('x[',i,']=',x[i]);

end;

writeln;

start:=Gettim;

i:=1;

Repeat

If x[i]>x[i+1] then begin a:=x[i+1];

x[i+1]:=x[i];

x[i]:=a;

i:=i-1;

If i=0 then i:=2 end

else i:=i+1

Until i=n;

writeln('time=',gettim-start)

For i:=1 to n do writeln('x[',i,']=',x[i]);

end.

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


i:=2..n

j:=1..i-1

a:=x[i]

x[i]:=x[j]

x[j]:=a




Описание алгоритма:

На каждом шаге алгоритма мы по порядку выбираем один из элементов массива и, если нужно, вставляем его на нужную позицию в уже отсортированном массиве, до тех пор, пока набор входных данных не будет исчерпан.

^ Program Vstavka;

uses dos;

Type mass=array [1..100] of integer;

Var i,b,n,j,a: integer; x: mass;

start:longint;

Function GetTim:longint;

var h,m,s,ss :word;

begin

GetTime(h,m,s,ss);

GetTim:=ss+100*s {+100*60*m}

end;

Begin

Write('n='); readln(n);

b:=2*n;

For i:=1 to n do begin

x[i]:=random(b);

writeln('x[',i,']=',x[i]);

end;

writeln;

start:=Gettim;

For i:=2 to n do

For j:=1 to i-1 do

If x[i]<x[j] then begin

a:=x[i];

x[i]:=x[j];

x[j]:=a; end;

writeln('time=',gettim-start);

For i:=1 to n do writeln('x[',i,']=',x[i]);

end.

Быстродействие (время в мс)

(даны средние значения времени за три запуска программы для определенного количества элементов)

^ Кол-во элементов

Пузырёк

Перестановки

Гном

Вставки

100

0

0

0

0

300

5

0

5

4

500

11

0

6

6

1000

47

8

29

28

2000

181

31

115

108

3000

415

73

262

245

4000

730

130

467

434

5000

1137

199

729

679



Вывод: Существуют несколько факторов, влияющих на выбор алгоритма в каждой конкретной ситуации:

1. Время сортировки

2. Память - дополнительные затраты памяти, зависящие от размера

массива.

3. Устойчивость - устойчивая сортировка не меняет взаимного

расположения равных элементов.

4. Естественность поведения - эффективность метода при обработке уже

отсортированных, или частично отсортированных данных.

Естественный - значит учитывает этот факт и работает быстрее.

Hеестественный метод этот факт не учитывает.

5. Простота - количество операторов, выполняемых алгоритмом. Более простые алгоритмы вызывают меньше ошибок при программировании.

Учитывая эти факторы и таблицу быстродействия для конкретных случаев, можно сделать вывод, что наиболее быстрым является алгоритм сортировки последовательными перестановками. Он показал наилучшее время как при небольших массивах так и при большом количестве элементов среди рассматриваемых алгоритмов. При любом количестве элементов массива наихудшее время показал алгоритм сортировки пузырьком. Метод сортировки вставками, несмотря на такие приемущества как устойчивость и естественность , показал почти одинаковое время работы с методом гнома, меньшее чем у сортировки пузырьком, но намного уступающим по времени сортировке последовательными перестановками.


Скачать файл (75 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации