Это упражнение дает нам несколько ценных уроков о сортировке в частности и программировании вообще.
Библиотечная функция qsort
Библиотечная функция qsort проста в использовании и работает достаточно быстро. Она работает медленнее, чем самодельные версии быстрой сортировки, только потому, что предназначена для применения к различным типам данных, поэтому сравнение элементов осуществляется через вызов внешней функции. Интерфейс функции sort языка C++ существенно проще: массив х сортируется вызовом sort(x, х+n). Кроме того, она достаточно эффективно реализована. Если системная сортировка отвечает вашим требованиям, не задумывайтесь и отметайте идею написания своей собственной.
Сортировка вставкой
Сортировку вставкой легко написать, и она достаточно эффективна для небольших задач. Сортировка 10 ООО целых чисел с помощью этого алгоритма требует на моем компьютере всего лишь треть секунды.
Случай больших п
Для больших п жизненно важным оказывается время выполнения алгоритма быстрой сортировки 0(п log /?). Методы разработки алгоритмов из главы 8 дали нам идею (принцип «разделяй и властвуй»), а верификация, обсуждавшаяся в главе 4, позволила нам реализовать эту идею в ясном и эффективном коде.
Хотя значительное увеличение производительности обычно достигается сменой алгоритма, методы оптимизации из главы 9 ускорили работу сортировки вставкой в 4 раза, а быстрой сортировки — в 2 раза.
Опубликовал vovan666
April 17 2013 00:02:46 ·
0 Комментариев ·
3212 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.