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

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

Обычно упорядочивающая функция не вычисляется по какому-либо правилу, а хранится как явная компонента поля  каждого элемента. Ее значение называется ключом кеу элемента. Поэтому для представления элементов хорошо подходят такие образования, как запись, а графически это представляется так (рис. 1):
Говоря об алгоритмах сортировки, мы будем обращать внимание лишь на компоненту — ключ, другие же компоненты можно даже и не определять (рис.2). Поэтому из наших дальнейших рассмотрений вся сопутствующая информация. Чтобы уменьшить эти затраты, сортировку производят в таблице адресов ключей. После сортировки перестанавливают указатели. Это метод сортировки таблицы адресов (рис.3) . Метод сортировки называется устойчивым, если в процессе сортировки относительное расположение элементов с равными ключами не изменяется. Устойчивость сортировки часто бывает желательной, если речь идет об элементах, уже упорядоченных (отсортированных) по некоторым вторичным ключам  (т.е. свойствам) , не влияющим на основной ключ.

Отсортированный массив (рис. 2):

Массив отсортированный другим методом (рис. 3):

Основное условие: выбранный метод сортировки массивов должен экономно использовать доступную память. Это предполагает, что перестановки, приводящие элементы в порядок, должны выполняться на том же месте, т.е. методы, в которых элементы из массива А передаются в результирующий массив H, представляют существенно меньший интерес. Ограничив критерием экономии памяти наш выбор нужного метода среди многих возможных, мы будем сначала классифицировать методы по их экономичности, т.е. по времени их работы. Хорошей мерой эффективности может быть С — число необходимых сравнений ключей и М — число пересылок (перестановок) элементов.
Эти числа — функции от n- числа сортируемых элементов. Хотя улучшенные алгоритмы сортировки требуют порядка n*log n сравнений, мы разберем простой метод, который причисляется к так называемым прямым, где требуется порядка n^2 сравнений ключей. К достоинствам прямых методов относятся :
1.Прямые методы особенно удобны для объяснения характерных черт основных  принципов большинства сортировок.
2.Программы этих методов легко понимать, и они коротки. Напомним, что сами программы также занимают память.
3.Улучшенные методы требуют небольшого числа операций, но эти операции обычно сами более сложны, и поэтому для достаточно малых n прямые методы оказываются быстрее, хотя при больших n их использовать, конечно, не следует.
Методы сортировки «на том же месте» можно разбить в соответствии с определяющими их принципами на три основные категории:
1.Сортировки прямым включением Bу insertion .
2.Сортировки прямым выделением Bу selection .
3.Сортировки прямым обменом Bу exchange .

Алгоритм

К прямым методам относится метод прямого выбора.
Рассматриваем весь ряд массива и выбираем элемент меньший или больший элемента а(i), определяем его место в массиве — k, и затем меняем местами элемент а(i) и элемент а(k).
for i = 1 to n — 1

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

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