Вики-страница ученика
Содержание |
Название проекта
Упорядочивание информации в одномерных массивах
Авторы и участники проекта
Артур Акопджанян
Тема исследования группы
Скорость сортировки данных
Проблемный вопрос (вопрос для исследования)
Для чего существуют различные алгоритмы сортировки информации?
Раскрытие вопроса
Cортировка массивов — одно из наиболее важных действий над массивами в системах сбора и поиска информации, т. к. в отсортированных массивах найти нужную информацию можно гораздо быстрее по сравнению с несортированными. Cуществует множество различных алгоритмов сортировки, которые значительно отличаются друг от друга по скорости работы.
"Быстрые" способы сортировки массивов могут дать колоссальный выигрыш на больших массивах, содержащих тысячи элементов, однако для небольших массивов можно использовать самые простые способы сортировки.
Сравним алгоритмы сортировок, испытав их на массивах, содержащих 4000, 8000, 10000, 15000 и 20000 целых чисел, соответственно. Время выполнения измерено в тиках (1/60 доля секунды). Среди всех алгоритмов порядка O(n2) время сортировки вставками отражает тот факт, что на i-ом проходе требуется лишь i/2 сравнений. Этот алгоритм явно превосходит все прочие сортировки порядка O(n2). Заметьте, что самую худшую общую производительность демонстрирует сортировка методом пузырька. Результаты испытаний показаны в таблице 1.
Для иллюстрации эффективности алгоритмов сортировки в экстремальных случаях используются массивы из 20000 элементов, отсортированных по возрастанию и по убыванию. При сортировке методом пузырька и сортировке вставками выполняется только один проход массива, упорядоченного по возрастанию, в то время как сортировка посредством выбора зависит только от размера списка и производит 19999 проходов. Упорядоченность данных по убыванию является наихудшим случаем для пузырьковой, обменной и сортировки вставками, зато сортировка выбором выполняется, как обычно.
Таблица 1
| N | Обменная сортировка | Сортировка выбором | Пузырьковая сортировка | Сортировка вставками |
| 4 000 | 12.23 | 17.30 | 15.78 | 5.67 |
| 8 000 | 49.95 | 29.43 | 64.03 | 23.15 |
| 10 000 | 77.47 | 46.02 | 99.10 | 35.43 |
| 15 000 | 173.97 | 103.00 | 223.28 | 80.23 |
| 20 000 | 313.33 | 185.05 | 399.47 | 143.67 |
| 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 |
Из всего выше сказанного, можно сделать вывод, что для каждой ситуации, должна применяться наиболее эффективная сортировка, так как это дает выигрыш в скорости, особенно при использовании в больших массивах информации.
