Для чего существуют различные алгоритмы сортировки информации?
(→Раскрытие вопроса) |
(→Раскрытие вопроса) |
||
| Строка 23: | Строка 23: | ||
<p>Для иллюстрации эффективности алгоритмов сортировки в экстремальных случаях используются массивы из 20000 элементов, отсортированных по возрастанию и по убыванию. При сортировке методом пузырька и сортировке вставками выполняется только один проход массива, упорядоченного по возрастанию, в то время как сортировка посредством выбора зависит только от размера списка и производит 19999 проходов. Упорядоченность данных по убыванию является наихудшим случаем для пузырьковой, обменной и сортировки вставками, зато сортировка выбором выполняется, как обычно.</p> | <p>Для иллюстрации эффективности алгоритмов сортировки в экстремальных случаях используются массивы из 20000 элементов, отсортированных по возрастанию и по убыванию. При сортировке методом пузырька и сортировке вставками выполняется только один проход массива, упорядоченного по возрастанию, в то время как сортировка посредством выбора зависит только от размера списка и производит 19999 проходов. Упорядоченность данных по убыванию является наихудшим случаем для пузырьковой, обменной и сортировки вставками, зато сортировка выбором выполняется, как обычно.</p> | ||
| − | + | <table> | |
| − | + | <tr> | |
| − | + | <td>N</td> | |
| + | <td>Обменная сортировка</td> | ||
| + | <td>Сортировка выбором</td> | ||
| + | <td>Пузырьковая сортировка</td> | ||
| + | <td>Сортировка вставками</td> | ||
| + | </tr> | ||
| + | |||
| + | |||
4 000 12.23 17.30 15.78 5.67 | 4 000 12.23 17.30 15.78 5.67 | ||
| Строка 34: | Строка 41: | ||
20 000 313.33 185.05 399.47 143.67 | 20 000 313.33 185.05 399.47 143.67 | ||
| − | + | </table> | |
N Обменная Сортировка Пузырьковая Сортировка | N Обменная Сортировка Пузырьковая Сортировка | ||
Версия 15:25, 27 ноября 2011
Содержание |
Название проекта
Упорядочивание информации в одномерных массивах
Авторы и участники проекта
Семенов Алексей
Тема исследования группы
Проблемный вопрос (вопрос для исследования)
Для чего существуют различные алгоритмы сортировки информации?
Раскрытие вопроса
Cортировка массивов — одно из наиболее важных действий над массивами в системах сбора и поиска информации, т. к. в отсортированных массивах найти нужную информацию можно гораздо быстрее по сравнению с несортированными. Cуществует множество различных алгоритмов сортировки, которые значительно отличаются друг от друга по скорости работы.
"Быстрые" способы сортировки массивов могут дать колоссальный выигрыш на больших массивах, содержащих тысячи элементов, однако для небольших массивов можно использовать самые простые способы сортировки.
Сравним алгоритмы сортировок, испытав их на массивах, содержащих 4000, 8000, 10000, 15000 и 20000 целых чисел, соответственно. Время выполнения измерено в тиках (1/60 доля секунды). Среди всех алгоритмов порядка O(n2) время сортировки вставками отражает тот факт, что на i-ом проходе требуется лишь i/2 сравнений. Этот алгоритм явно превосходит все прочие сортировки порядка O(n2). Заметьте, что самую худшую общую производительность демонстрирует сортировка методом пузырька. Результаты испытаний показаны в таблице 1.
Для иллюстрации эффективности алгоритмов сортировки в экстремальных случаях используются массивы из 20000 элементов, отсортированных по возрастанию и по убыванию. При сортировке методом пузырька и сортировке вставками выполняется только один проход массива, упорядоченного по возрастанию, в то время как сортировка посредством выбора зависит только от размера списка и производит 19999 проходов. Упорядоченность данных по убыванию является наихудшим случаем для пузырьковой, обменной и сортировки вставками, зато сортировка выбором выполняется, как обычно.
| N | Обменная сортировка | Сортировка выбором | Пузырьковая сортировка | Сортировка вставками |
N Обменная Сортировка Пузырьковая Сортировка
сортировка выбором сортировка вставками
8 000 (упорядочен по возраст.) 185.27 185.78 0.03 0.05 8 000 (упорядочен по убыв.) 526.17 199.00 584.67 286.92
В общем случае “Быстрая сортировка” является самым быстрым алгоритмом. Благодаря своей эффективности, равной O(n log2n), он явно превосходит любой алгоритм порядка O(n2). Судя по результатам испытаний, приведенных в следующей таблице, он также быстрее любой из сортировок порядка O(n log2n), рассмотренных нами в прошлом номере. Обратите внимание, что эффективность «быстрой» сортировки составляет O(n log2n) даже в экстремальных случаях. Зато сортировка посредством поискового дерева становится в этих случаях O(n2) сложной, так как формируемое дерево является вырожденным.
n Турнирная Сортировка посред- Пирамидальная "Быстрая"
сортировка ством дерева сортировка сортировка
4 000 0.28 0.32 0.13 0.07 8 000 0.63 0.68 0.28 0.17 10 000 0.90 0.92 0.35 0.22 15 000 1.30 1.40 0.58 0.33 20 000 1.95 1.88 0.77 0.47
(упорядочен по возрастанию) 8 000 1.77 262.27 0.75 0.23 (упорядочен по убыванию) 8 000 1.65 275.70 0.80 0.28
Из всего выше сказанного, можно сделать вывод, что для каждой ситуации, должна применяться наиболее эффективная сортировка, так как это дает выигрыш в скорости, особенно при использовании в больших массивах информации.
