Geum.ru

Варианты заданий 37 Контрольные вопросы к защите ргр: 39

Вид материалаКонтрольные вопросы

Содержание


Анализ эффективности сортировки
Некоторые методы сортировок
Подобный материал:
1   2   3   4   5   6   7   8

Анализ эффективности сортировки


В качестве оценки эффективности алгоритма сортировки обычно используют функциональную зависимость времени работы алгоритма от размерности исходного массива T(n), где n – количество элементов массива. Временем работы алгоритма называют число элементарных шагов, которые он выполняет. При анализе алгоритмов в первую очередь интерес представляет характер зависимости при достаточно больших размерностях массивов (n→∞).

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

Количество сравнений и перестановок будет зависеть не только от длины массива N, но и от того, насколько исходный массив упорядочен. Наиболее благоприятный случай, когда массив уже отсортирован. В худшем случае, количество перестановок и сравнений будет максимальным. Большей частью нас будет интересовать время работы в худшем случае, т.к. это определяет наибольшее время работы сортировки. На практике «плохие» случаи встречаются чаще, и время работы в среднем бывает довольно близко к времени работы в худшем случае.


В математике характер зависимости часто определяют порядком функции, при этом берется старший порядок. Такая характеристика функции называется порядком роста или сложностью. Обозначается: T(n)=Θ(g(n)). Алгоритм с меньшим порядком роста времени работы предпочтительнее.


НЕКОТОРЫЕ МЕТОДЫ СОРТИРОВОК

Сортировка подсчетом


Если элемент в отсортированном по возрастанию массиве стоит на i-ом месте, значит он не меньше (i-1) элементов.

Идея сортировки подсчетом состоит в том, чтобы выяснить, сколько, элементов превышает i-ый элемент массива, что указывает на его место в отсортированном массиве. Если значение элемента превышает k элементов, следовательно, слева от него будут стоять эти k элементов (при упорядочивании по неубыванию), а данный элемент будет стоять на (k+1)-ом месте.

Пример 1

Упорядочить по возрастанию массив целых чисел, отличных друг от друга: М={3, 6, 1, 12, 4, 25, 9}.


Для этого посчитаем, сколько элементов меньше первого элемента массива M[1]= 3, затем – сколько элементов меньше второго числа M[2]=6, и т.д. Число 3 по значению превышает только одно число, значит, оно должно стоять на 2-ом месте. В итоге получаем значения, приведенные ниже (см. ):

Таблица 1

Индекс элемента в исходном массиве P
i-ый элемент
Кол-во элементов< i-го элемента
Индекс элемента в отсортированном массиве new_P

1
3
1
1+1=2

2
6
3
3+1=4

3
1
0
0+1=1

4
12
5
5+1=6

5
4
2
2+1=3

6
25
6
6+1=7

7
9
4
4+1=5

Блок-схема сортировки подсчетом:




Процедура сортировки подсчетом по возрастанию:


procedure sort_creat (var p:array of integer; n:byte);

var i,j,kol:integer;

new_p: array[1..n]of integer;

begin

for i:=1 to n do

begin

kol:=0;

for j:=1 to n do

if p[i]>p[j] then inc(kol);

new_p[kol+1]:=p[i];

end;

end;


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


Процедура сортировки подсчетом по неубыванию:


procedure sort_creat(p:array of integer; n:integer);

var i,j,kol:integer;

new_p:array[1..n]of integer;

begin

for i:=1 to n do

begin

kol:=0;

for j:=1 to n do

if p[i]>p[j] then inc(kol);

while new_p[kol+1]=p[i] do inc(kol);

new_p[kol+1]:=p[i];

end;

end;


Оценим эффективность сортировки подсчетом по количеству сравнений. Так как мы сравниваем каждый элемент с каждым элементом массива, то имеем N*N сравнений. Эффективность алгоритма C=N*N=Θ(N2), т.е. сортировка подсчетом имеет квадратичную сложность. Множитель N2 свидетельствует о том, что алгоритм неэффективен при большом N , т.к. при удвоении числа элементов массива количество сравнений увеличится в 4 раза. Но он очень прост в реализации.

Независимо от отсортированности массива, количество перестановок равно длине массива N. То есть эффективность алгоритма по перестановкам имеет линейную сложность.