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

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

При обработке данных в ЭВМ важно знать и информационное поле элемента, и его размещение в памяти машины. Для этих целей используется сортировка. Итак, сортировка- -это расположение данных в памяти в регулярном виде по их ключам. Регулярность рассматривают как возрастание значения ключа от начала к концу в массиве.
Различают следующие типы сортировок:
внутренняя сортировка — это сортировка, происходящая в оперативной памяти машины
внешняя сортировка — сортировка во внешней памяти.
Если сортируемые записи занимают большой объем памяти, то их перемещение требует больших затрат. Для того, чтобы их уменьшить, сортировку производят в таблице адресов ключей, делают перестановку указателей, т.е. сам массив не перемещается. Это метод сортировки таблицы адресов.
При сортировке могут встретиться одинаковые ключи. В этом случае при сортировке желательно расположить после сортировки одинаковые ключи в том же расположении, что и в исходном файле. Это устойчивая сортировка.
Эффективность сортировки можно рассмотреть с нескольких критериев:
время, затрачиваемое на сортировку
объем оперативной памяти, требуемой для сортировки
время, затраченное программистом на написание программы

Рассмотрим второй критерий подробнее: мы можем подсчитать количество сравнений при выполнении сортировки или количество перемещений.
Предположим, что число сравнений определяется формулой:
C = 0,01n2 + 10n
Если n<1000, то второе слагаемое больше.
Если n>1000, то первое слагаемое больше.
То есть, при малых n порядок сравнения равен , а при больших n он равен n.
Различают следующие методы сортировки:
строгие (прямые) методы
улучшенные методы

Рассмотрим преимущества прямых методов:
1. Программы этих методов легко понимать, и они коротки. Напомним, что сами программы также занимают память.
2. Прямые методы особенно удобны для объяснения характерных черт основных принципов большинства сортировок.
3. Усложненные методы требуют небольшого числа операций, но эти операции обычно сами более сложны, и поэтому для достаточно малых n прямые методы оказываются быстрее, хотя при больших n их использовать, конечно,  не следует.

Методы сортировки «на том же месте» можно разбить в соответствии с определяющими их принципами на 3 категории:
1. Сортировки с помощью включения (by insertion)
2. Сортировки с помощью выделения (by selection)
3. Сортировки с помощью обменов (by exchange)

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

Такой метод широко используется при игре в карты. Элементы (карты)  мысленно делятся на уже «готовую» последовательность a(1),…,a(i-1)  и исходную последовательность. При каждом шаге, начиная с i=2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при  этом он вставляется на нужное место.

Алгоритм

Алгоритм  сортировки прямым включением таков:
for x:=2 to n do
x:=a[i]
включение х на соответствующее место среди a[1]…a[i]
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

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