|
==============================================================
> 12. Требования и свойства сортировок. Что когда лучше?
==============================================================
A: Kantor Ilia
Охарактеризуем сортировки по четырем параметрам:
1. Время сортировки
2. Память - дополнительные затраты памяти, зависящие от размера
массива.
3. Устойчивость - устойчивая сортировка не меняет взаимного
расположения равных элементов.
Многие методы (например, HeapSort) по ходу работы так
перетряхивают массив, что равные элементы после сортировки
могут идти в совсем другой последовательности, нежели до этого.
4. Естественность поведения - эффективность метода при обработке уже
отсортированных, или частично отсортированных данных.
Естественный - значит учитывает этот факт и работает быстрее.
Hеестественный метод этот факт не учитывает, либо бывает, что
работает даже хуже(!).
Кроме того, есть два типа основных сортировок:
Распределяющая и ее вариации | Сортировка сравнениями
|
Основана на том, что число возможных | Пользуется лишь возможностью
значений ключа конечно. | прямого сравнения ключей и
| их упорядоченностью.
| Quicksort, Heapsort, Insertsort...
Сортировки сравнениями:
> SelectSort, BubbleSort, ShellSort - на практике не применяются.
> TreeSort - сортировка двоичным деревом
1. Общее быстродействие всегда O(nlogn).
2. Обычное дерево: n элементов (ключ + 2 указателя),
выбор с замещением: 2n-1 элементов
3. Устойчивости нет.
4. Поведение неестественно.
Примечание.
Поэтому TreeSort обычно применяют там, где
- построенное дерево можно с успехом применить для других задач.
- данные уже построены в 'дерево'. } не тратится
- данные можно считывать непосредственно в дерево. } лишняя
Hапример, при потоковом вводе с консоли или из файла. } память
Более подробно о выборе разновидности TreeSort смотри в соответствующем
вопросе.
> Insertsort - простые вставки.
1. Общее быстродействие - O( n^2 ), но ввиду простоты реализации
метода является наибыстрейшим для малых ( 12-20 элементов ) массивов и списков.
2. Сортировка происходит 'на месте', т.е дополнительных затрат памяти нет.
3. Устойчивая.
4. Естественное поведение.
Примечание. Ввиду своих особенностей, метод хорош для частично
отсортированных данных.
> Quicksort - быстрая сортировка
1. Общее быстродействие Quicksort O( nlogn ) времени.
Случай n^2 возможен лишь в теории, но вероятность такого
чрезвычайно мала. В общем и целом - наиболее быстрая сортировка
сравнениями для разупорядоченных массивов с 50 и более элементами.
2. Итерационный вариант требует logn памяти, рекурсивный - O(n).
3. Устойчивости нет.
4. Поведение неестественно. Уже практически отсортированный
массив будет сортироваться столько же, сколько и полностью
разупорядоченный.
> Heapsort - пирамидальная сортировка.
1. В 1.5 раза медленнее быстрой. Общее быстродействие всегда O(nlogn).
2. Сортировка 'на месте'
3. Устойчивости нет.
4. Поведение неестественно.
Примечание. Основное достоинство - сортировка не требует дополнительной
памяти, хороший средний случай. Ее элементы часто применяются в смежных
задачах.
> Mergesort - сортировка слиянием
1. Общее быстродействие - Theta(nlogn)
2. Theta(n)
3. Устойчивая.
4. Зависит от конкретной сортировки, основанной на принципе слияния.
Hа практике используются реализации с естественным поведением.
Примечание. Mergesort - общее название для обширного класса сортировок,
основанных на принципе слияния. Такие сортировки уступают QuickSort при
работе с массивами, но выигрывают на файлах и списках.
Распределяющая сортировка:
Для массивов:
Пусть всего n элементов, сортировка производится по k разрядам,
каждый может принимать до s различных значений. Числа k и s - константы,
известные до начала сортировки.
1. Общее быстродействие O(k(n+s)) [s иногда не учитывают вовсе]
2. Реализация со временным массивом O(n), [Radix Sort]
Реализация без временного массива O(logn) [Radix Exchange Sort]
3. Реализация со временным массивом устойчивая,
Реализация без временного массива неустойчивая.
4. Hеестественное поведение
Для списков:
1. Общее быстродействие O(k(n+s)) [s иногда не учитывают]
2. Дополнительной памяти не требуется, так как реорганизовывать
список можно просто через указатели
3. Устойчивая сортировка.
4. Hеестественное поведение.
> 12.1 Какая самая быстрая сортировка ?
===========================================================================
В общем случае:
Малые массивы/списки - менее 20 элементов => InsertSort
Большие массивы => QuickSort
Длинные списки/файлы => MergeSort
Для сортировок сравнениями давно доказана теорема о максимальном быстродействии: Omega(nlogn) операций.
Если количество возможных различных ключей ненамного больше их общего
числа - то наибыстрейшей будет распределяющая сортировка и ее вариации:
Radix sort - 'радиксная', или 'распределяющая' сортировка.
Hапример, для больших массивов строк, целых чисел из небольшого промежутка.
Hа ее принципах основана Multiway Quicksort /MQS/ - быстрая с составными
ключами, на мой взгляд, неплохо удавшаяся попытка Jon Bentley и Robert
Sedgewick соединить преимущества Radix sort и QuickSort. Есть и другие шаги
в этом направлении..
Существует еще очень много различных сортировок, которые выходят за рамки
FAQ'а.
В конкретном случае надо смотреть по данным и имеющимся в наличии
ресурсам. В типичных случаях самыми простыми и довольно быстрыми
решениями будут стандартные методы.
> 12.2 Что лучше: распределяющая сортировка или сортировка сравнениями ?
===========================================================================
Когда количество возможных различных ключей ненамного больше их общего
числа - распределяющая.
Различных ключей очень много, размер массива сравнительно небольшой
- сравнениями.
Время сортировки случайных целых чисел из промежутка [0..999]
Цифры могут меняться в зависимости от реализации, но соотношения
останутся приблизительно такими же.
n 10 20 30 40 50 100 200
Quick Sort 0.22 0.55 0.88 1.65 2.14 4.50 13.13
Merge Sort 0.33 0.88 1.37 1.97 2.74 6.37 14.78
Radix Sort 0.38 0.71 0.99 1.38 1.70 3.29 6.64
Иллюстрация замедления распределяющей сортировки при расширении
промежутка в два раза. Как следует из асимптотики, она работает в 2 раза
медленнее.
промежуток 0-999 промежуток 0-999999
n = 100 Сравнений Перемещений Время Сравнений Перемещений Время
Quick Sort 600 478 4.51 846 562 5.93
Merge Sort 543 672 6.43 538 672 6.38
Radix Sort 0 1000 3.29 0 2000 6.92
|
