Глава 2
2.1 Теоретический обзор про сортировки
Это расположение данных в памяти ЭВМ в регулируемом виде по их ключам. При обработке данных важно знать информационное поле данных и размещение их в машине. Различают внутреннюю и внешнюю сортировку. Внутренняя – это сортировка в оперативной памяти. Внешняя - сортировка во внешней памяти. Если сортируемые записи занимают большой объем памяти, то их перемещение требует больше времени. Для уменьшения затрат используют метод сортировки таблицы адресов. Производится перестановка указателей , сам массив не перемещается. При сортировке могут встречаться одинаковые ключи данных , в этом случае одинаковые ключи желательно расположить в том же порядке , что и в исходном файле. Эфективность сотировки определяется: 1 временем затраченным на сортировку 2 объемом оперативной памяти 3 временем затраченным на написание программы. Порядок числа сравнений при сортировки определяется в пределах от O(nlogn) до O(n2). Сортировки классифицируются:
2.2 Математическая формулировка сортировки Шелла
Получить на входе файл с текстом, из этого текста взять слова, отсортировать их с помощью сортировки Шелла. При выполнении задания руководствоваться следующим:
Взять за основу файл с произвольным текстом (слова с разделителем , . : ; ?... ).
Расположить все слова в отдельном файле в алфавитном порядке (без повторений).
Протестировать работу программы на следующих примерах: отсортированный файл,
почти сортированный,
несортированный (произвольный),
отсортированный в обратном порядке.
Проанализировать к-во проходов, к-во перестановок и время сортировки.
Оценить устойчивость (длина ключа - 3 символа, последний тест)
и естественность алгоритма (два первых теста).
Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, идея которого состоит в сравнении элементов, стоящих не только рядом, но и на расстоянии друг от друга. Иными словами — сортировка вставками с предварительными «грубыми» проходами.
Рассмотрим следующий алгоритм сортировки массива a[0].. a[15].
Рис
1
1. Вначале сортируем простыми вставками каждые 8 групп из 2-х элементов (a[0], a[8[), (a[1], a[9]), ... , (a[7], a[15]). См рис.2
Рис
2
2. Потом сортируем каждую из четырех групп по 4 элемента (a[0], a[4], a[8], a[12]), ..., (a[3], a[7], a[11], a[15]). (см.Рис 3)
Рис
3
В нулевой группе будут элементы 4, 12, 13, 18, в первой - 3, 5, 8, 9 и т.п.
3. Далее сортируем 2 группы по 8 элементов, начиная с (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14]). (см.рис 4)
Рис
4
4. В конце сортируем вставками все 16 элементов.
Рис
5
Очевидно, лишь последняя сортировка необходима, чтобы расположить все элементы по своим местам. Остальные элементы максимально близко к соответствующим позициям, так что в последней стадии число перемещений будет весьма невелико. Последовательность и так почти отсортирована. Ускорение подтверждено многочисленными исследованиями и на практике оказывается довольно существенным.
Единственной характеристикой сортировки Шелла является приращение - расстояние между сортируемыми элементами, в зависимости от прохода. В конце приращение всегда равно единице - метод завершается обычной сортировкой вставками, но именно последовательность приращений определяет рост эффективности.