Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

время, затрачиваемое на сортировку;
объем оперативной памяти, требуемой для сортировки;
время, затраченное программистом на написание программы.
Выделяем первый критерий, поскольку будем рассматривать только методы сортировки «на том же месте», то есть не резервируя для процесса сортировки дополнительную память. Эквивалентом затраченного на сортировку времени можно считать количество сравнений при выполнении сортировки и количество перемещений.
Порядок числа сравнения при сортировке лежит в пределах от  О (n log n)   до О (n2);    О (n) — идеальный  и недостижимый случай.
Различают следующие методы сортировки:
строгие (прямые) методы;
улучшенные методы.
Строгие методы:
1)метод прямого включения;
2)метод прямого выбора;
3)метод прямого обмена.
Эффективность этих трех методов примерно одинакова.

6.1. Сортировка методом прямого включения

Такой метод  широко используется при игре в карты. Элементы мысленно делятся на уже готовую последовательность  a1,…,ai-1 и исходную последовательность. При каждом шаге, начиная с i = 2  и увеличивая i  каждый раз на единицу, из исхожной последовательности извлекается i-й элемент и перекладывается  в готовую последовательность, при этом он вставляется на нужное место.На рис. 6.2 показан в качестве примера процесс сортировки  с помощью включения шести случайно выбранных чисел. Алгоритм этой сортировки таков:

for i = 2 to n
x = a(i)
находим место среди а(1)…а(i) для включения х
next i

Для сортировки методом прямого включения пользуются следующими приемами:

Псевдокод:
Без барьера:
for i = 2 to n
x = a(i)
for j = i — 1 downto 1
if x < a(j )
then  a( j + 1) = a(j )
else  go to  L
endif
next j
L:  a( j + 1) = x
next i
return

С барьером:
for i = 2 to n
x = a(i)
a(0) = x {a(0) — барьер}
j = i — 1
while  x < a(j )  do
a( j +1) = a(j )
j = j — 1
endwhile
a( j +1) = x
next i
return

Паскаль:
Без  барьера:
for i:= 2 to n do
begin
x:= a(i);
for j:= i — 1downto 1 do
if x < a(j ) then
a(j +1):= a(j )
else  goto  1;
end;
end;
1:   a(j + 1):= x;
end;
end;

С барьером:
for i := 2 to n do
begin
x:= a(i);
a(0):= x; {a(0) — барьер}
j:= i — 1;
while  x < a(j ) do
begin
a(j +1):= a(j );
j:=j — 1;
end;
a(j +1):= x;
end;

Эффективность алгоритма

Число сравнений ключей Ci при i- м просеивании самое большее равно i-1, самое меньшее — 1; если предположить, что все перестановки из N ключей равновероятны, то среднее число сравнений = i/2. Число же пересылок Mi=Ci+3 (включая барьер). Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие же оценки — когда они первоначально расположены в обратном порядке. В некотором смысле сортировка с помощью включения демонстрирует истинно естественное поведение. Ясно, что приведенный алгоритм описывает процесс устойчивой сортировки: порядок элементов с равными ключами при нем остается неизменным.

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники