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