3. СОРТИРОВКА И ПОРЯДКОВЫЕ СТАТИСТИКИ

В этой главе изучаются две взаимосвязанные задачи — сортировка последовательности элементов и выбор 6-го наименьшего элемента последовательности. Под сортировкой последовательности мы подразумеваем переупорядочение ее элементов в такую последовательность, где все элементы расположены в порядке невозрастания или неубывания. Можно найти наименьший элемент последовательности, расположив ее элементы в порядке неубывания и выбрав из полученной последовательности элемент. Однако мы увидим, что выбрать наименьший элемент можно быстрее.

Сортировка — практически важная и теоретически интересная задача. Поскольку сортировка больших объемов данных составляет значительную часть коммерческой обработки данных, эффективные алгоритмы для сортировки важны и с экономической точки зрения. Что же касается разработки алгоритмов, то даже здесь процесс сортировки последовательности элементов очень важен — он является существенной частью многих алгоритмов.

В данной главе рассматриваются два класса сортирующих алгоритмов. Первый основан на использовании структуры сортируемых элементов. Например, если сортируемые элементы представлены числами от до то можно упорядочить последовательность из элементов за время а если словами в некотором алфавите, то за время, пропорциональное сумме длин этих слов.

Второй класс алгоритмов не предполагает у сортируемых элементов никакой структуры. Основная операция — сравнение двух элементов. В алгоритмах этого типа, как мы увидим, для сортировки последовательности, состоящей из элементов, требуется по крайней мере сравнений. Мы дадим два сортирующих алгоритма сложности а именно Сортдеревом со сложностью в худшем случае и Быстрсорт со средней сложностью