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

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

Сортировка — это расположение данных в памяти в регулярном виде по их ключам. Регулярность рассматривают как возрастание (убывание) значения ключа от начала к концу в массиве.
Если сортируемые записи занимают большой объем памяти, то их перемещение требует больших затрат. Для того, чтобы их уменьшить, сортировку производят в таблице адресов ключей, делают перестановку указателей, т.е. сам массив не перемещается. Это метод сортировки таблицы адресов.
При сортировке могут встретиться одинаковые ключи. В этом случае при сортировке желательно расположить после сортировки одинаковые ключи в том же порядке, что и в исходном файле. Это устойчивая сортировка.
Эффективность сортировки можно рассматривать с нескольких критериев:
время, затрачиваемое на сортировку;
объем оперативной памяти, требуемой для сортировки;
время, затраченное программистом на написание программы.
Выделяем первый критерий. Можно подсчитать количество сравнений при выполнении сортировки или количество перемещений.
Пусть Н = 0,01n2 + 10n — число сравнений. Если n < 1000, то второе слагаемое больше, если n > 1000, то больше первое слагаемое.
Т. е. при малых n порядок сравнения будет равен n2, при больших n порядок сравнения — n.
Порядок сравнения при сортировке лежит в пределах
от 0 (n log n)  до 0 (n2); 0 (n) — идеальный случай.
Различают следующие методы сортировки:
строгие (прямые) методы;
улучшенные методы.
Строгие методы:
1) метод прямого включения;
2) метод прямого выбора;
3) метод прямого обмена.
Количество перемещений в этих трех методах примерно одинаково.

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

Неформальный алгоритм
for i = 2 to n
x = a(i)
находим место среди а(1)…а(i) для включения х
next i
Программа  на Паскале:
for i := 2 to n do
begin
x := a[i];
a[0] = x;
for j := i — 1 downto 1 do
if x < a[j]
then a[j + 1] := a[j]
else a[j + 1] := x;
end;

Эффективность алгоритма:
Количество сравнений в худшем случае будет равно
(n — 1)(n — 1).

3.2.2 Сортировка методом прямого выбора

Рассматриваем весь ряд массива и выбираем элемент, меньший или больший элемента а(i), определяем его место в массиве — k, и затем меняем местами элемент а(i) и элемент а(k).
Программа на Паскале:
for i := 1 to n — 1 do
begin
x := a[i];
k := i;
for j := i + 1 to n do
if x > a[j] then
begin
k := j;
x := a[k];
end;
a[k] := a[i];
a[i] := x;
end;
Эффективность алгоритма:
Число сравнений М = .
Число перемещений Cmin = 3(n — 1), Cmax = 3(n — 1)
(порядок n2).
В худшем случае сортировка прямым выбором дает порядок n2, как и для числа сравнений, так и для числа перемещений.

3.2.3 Сортировка с помощью прямого обмена (пузырьковая)
Идея: n — 1 раз проходят массив снизу вверх. При этом ключи попарно сравниваются. Если нижний ключ в паре меньше верхнего, то их меняют местами.
Программа на  Паскале:
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;

Страницы: 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

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