Лекция. Алгоритмы сортировки Под сортировкой
жүктеу/скачать 0,94 Mb.
|
|
Лекция. Алгоритмы сортировки Под сортировкой обычно понимают процесс перестановки объектов некоторого множества в определенном порядке. Цель сортировки – облегчить в дальнейшем поиск элементов отсортированного множества. Это очень часто выполняемая, фундаментальная операция. Объекты сортируются в телефонных справочниках, в списках налогоплательщиков, в оглавлениях книг, в библиотеках, в словарях, на складах, то есть почти всюду, где нужно искать хранимые объекты. Даже детей учат приводить вещи «в порядок», и они сталкиваются с некоторыми видами сортировки задолго до того, как начнут изучать арифметику. Поэтому сортировка – весьма важная операция, особенно в обработке данных. Кажется, ничто не поддается сортировке лучше, чем данные! И все же при изучении сортировки наибольший интерес для нас будут представлять еще более фундаментальные приемы, используемые при построении алгоритмов. Нелегко найти приемы, которые не использовались бы так или иначе в связи с алгоритмами сортировки. При этом сортировка – идеальная тема для демонстрации широкого разнообразия алгоритмов, решающих одну и ту же задачу, причем многие из них в каком-нибудь смысле оптимальны, и почти каждый из них имеет какие-нибудь преимущества перед остальными. Поэтому здесь хорошо видно, зачем нужен анализ эффективности алгоритмов. Более того, на примере сортировок становится понятно, что можно получить весьма существенный выигрыш в эффективности, разрабатывая хитроумные алгоритмы, даже если уже имеются очевидные методы. Если даны n элементов a0, a1, ... , an–1 то сортировка состоит в их перестановке к виду ak0, ak1, ... , ak[n–1] таким образом, чтобы для некоторой упорядочивающей функции f f(ak0) ≤ f(ak1) ≤ ... ≤ f(ak[n–1]). Главное требование при разработке алгоритмов сортировки массивов – экономное использование доступной оперативной памяти. Это означает, что перестановки, с помощью которых упорядочиваются элементы, должны выполняться in situ (лат.: на месте – прим. перев.), то есть, не требуя дополнительной временной памяти, так что методы, которые требуют копирования элементов из массива a в массив-результат b, не представляют интереса. Ограничив таким образом выбор методов, попробуем классифицировать их в соответствии с эффективностью, то есть временем работы. Хорошая мера эффективности – число необходимых сравнений ключей C, а также число перестановок элементов M. Эти величины являются функциями числа сортируемых элементов n. Хотя хорошие алгоритмы сортировки требуют порядка n*log(n) сравнений, мы сначала рассмотрим несколько простых и очевидных методов, которые называются простыми и требуют порядка n2 сравнений ключей. Есть три важные причины, почему нужно рассмотреть простые методы, прежде чем переходить к быстрым алгоритмам: 1. Простые методы особенно хороши для обсуждения основных принципов сортировки. 2. Соответствующие программы легко понять. К тому же они короткие: ведь нужно помнить, что программы тоже занимают место в памяти! 3. Хотя более изощренные методы требуют меньшего числа операций, но эти операции обычно сложнее устроены; поэтому простые методы оказываются быстрее для малых n, хотя их нельзя использовать для больших n. Алгоритмы сортировки, упорядочивающие элементы in situ, могут быть разделены на три основные категории в соответствии с используемым приемом: • сортировка вставками; • сортировка выбором; • сортировка обменом. жүктеу/скачать 0,94 Mb. Достарыңызбен бөлісу:
|