Элементарные методы сортировки

Сортировка выбором

Один из самых простых алгоритмов сортировки работает следующим образом. Сначала находится наименьший элемент массива и меняется местами с элементом, стоящим первым в сортируемом массиве. Потом находится второй наименьший элемент и меняется местами с элементом, стоящим вторым в исходном массиве. Этот процесс продолжается до тех пор, пока весь массив не будет отсортирован. Данный метод называется сортировкой выбором (selection sort), поскольку он все время выбирает наименьший элемент из числа не отсортированных. На рис 6.2 представлен пример работы этого метода.

В этом примере первый проход ничего не меняет, поскольку в массиве нет элемента, меньшего самого левого элемента А. На втором проходе наименьшим среди оставшихся оказался другой элемент А, поэтому он меняется местами с элементом S, занимающим вторую позицию. На третьем проходе элемент Е из середины массива обменивается с О в третьей позиции, на четвертом проходе еще один элемент Е меняется местами с R в четвертой позиции и т.д.

Программа 6.2 — реализация сортировки выбором, в которой выдержаны все принятые нами соглашения. Внутренний цикл содержит только сравнение текущего элемента с наименьшим выявленным на данный момент элементом (плюс код, необходимый для сдвига индекса текущего элемента и проверки, что он не выходит за границы массива). Проще не придумаешь. Действия по перемещению элементов находятся вне внутреннего цикла: каждая операция обмена элементов устанавливает один из них в окончательную позицию, так что всего необходимо N— 1 таких операций (для последнего элемента обмен не нужен). Поэтому время выполнения определяется в основном количеством сравнений. В разделе 6.5 мы покажем, что это количество пропорционально N 2, научимся предсказывать общее время выполнения и узнаем, как сравнивать сортировку выбором с другими элементарными методами.

Программа 6.2. Сортировка выбором

Для каждого i от l до r-1 элемент a[i] меняется местами с минимальным элементом из a[i], ..., a[r]. По мере продвижения индекса i слева направо элементы слева от него занимают свои окончательные позиции в массиве (и больше не перемещаются), поэтому, когда i достигнет правого конца, массив будет полностью отсортирован.

template <class Item>
void selection(Item a[], int l, int r)
  { for (int i = l; i < r; i++)
      { int min = i;
        for (int j = i+1; j <= r; j++)
if (a[j] < a[min]) min = j;
  exch(a[i], a[min]);
      }
  }
      

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

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

Упражнения

6.11. Покажите в стиле рис 6.2 процесс упорядочения файла E A S Y Q U E S T I O N методом выбора.

6.12. Каково максимальное количество обменов любого конкретного элемента в процессе сортировки выбором? Чему равно среднее количество обменов, приходящееся на один элемент?

6.13. Приведите пример файла из N элементов, в котором во время выполнения сортировки выбором условие a[j] < a[min] неверно максимальное количество раз (когда min изменяет значение).

6.14. Является ли сортировка выбором устойчивой?

Сортировка вставками

Картежники часто упорядочивают карты в руках следующим образом: выбирают по очереди каждую карту и вставляют ее в нужное место среди уже отсортированных элементов. В компьютерной реализации потребуется освободить место для вставляемого элемента, сдвинув большие элементы на одну позицию вправо и переместив на освободившееся место вставляемый элемент. Функция sort из программы 6.1 является программной реализацией этого метода, получившего название сортировка вставками (insertion sort).

Как и в случае сортировки выбором, элементы слева от текущего индекса уже упорядочены, однако они еще не находятся в окончательных позициях, т.к. могут быть сдвинуты для освобождения места под меньшие элементы, которые будут обнаружены позже. Массив будет полностью отсортирован, когда индекс достигнет правого конца. Пример работы этого метода показан на рис 6.3.

Реализация сортировки вставками, представленная в программе 6.1, проста, но не эффективна. Сейчас мы рассмотрим три способа ее усовершенствования, иллюстрирующих один общий принцип: хотелось бы получить компактный, понятный и эффективный код, однако часто эти цели противоречат друг другу, поэтому приходится искать компромисс. Для этого мы сначала разработаем естественную реализацию, а потом усовершенствуем ее серией преобразований, проверяя эффективность (и правильность) каждого такого преобразования.

Прежде всего, можно отказаться от выполнения операций compexch, когда встречается ключ, не больший ключа вставляемого элемента, поскольку подмассив, находящийся слева, уже отсортирован. А именно, при выполнении условия a[j-1] < a[j] можно выполнить команду break, чтобы выйти из внутреннего цикла for в функции sort программы 6.1. Это изменение превращает реализацию в адаптивную сортировку и примерно вдвое ускоряет работу программы для случайно упорядоченных ключей (см. лемму 6.2).

После усовершенствования, описанного в предыдущем абзаце, получилось два условия прекращения выполнения внутреннего цикла — для наглядности можно заменить его на оператор while. Менее очевидное улучшение реализации следует из того факта, что условие j > l обычно оказывается излишним: ведь оно выполняется только когда вставляемый элемент является наименьшим из просмотренных к этому моменту и поэтому доходит до начала массива.

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

Часто применяется альтернативный способ: сортируемые ключи хранятся в элементах массива от a[1] до a[N], а в a[0] заносится сигнальный ключ (sentinel key), значение которого по крайней мере не больше наименьшего ключа в сортируемом массиве. Тогда проверка, найден ли меньший ключ, проверяет сразу оба условия, и в результате внутренний цикл становится меньше, а быстродействие программы повышается.

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

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

t = a[j]; a[j] = a[j-1]; a[j-1] = t;
      

затем

t = a[j-1]; a[j-1] = a[j-2]; a[j-2] = t
      

и т.д. Значение t между этими двумя последовательностями не изменяется, но происходит бесполезная трата времени на его запоминание и тут же на чтение для следующего обмена. Программа 6.3 сдвигает большие элементы вправо без выполнения обменов, тем самым избегая напрасной траты времени.

Программа 6.3. Сортировка вставками

Это усовершенствованный вариант функции sort из программы 6.1, поскольку он (1) помещает в первую позицию наименьший элемент массива, чтобы использовать его как сигнальный ключ; (2) во внутреннем цикле выполняет лишь одну операцию присваивания, а не обмена; и (3) прекращает выполнение внутреннего цикла, когда вставляемый элемент уже находится в требуемой позиции. Для каждого i упорядочиваются элементы a[l], ..., a[i] с помощью сдвига на одну позицию вправо элементов a[l], ..., a[i-1] из отсортированного списка, которые больше a[i], и занесения a[i] в освободившееся место.

template <class Item>
void insertion(Item a[], int l, int r)
  { int i;
    for (i = r; i > l; i--) compexch(a[i-1], a[i]);
    for (i = l+2; i <= r; i++)
      { int j = i; Item v = a[i];
        while (v < a[j-1])
{ a[j] = a[j-1]; j--; }
        a[j] = v;
      }
  }
      

Реализация сортировки вставками в программе 6.3 значительно эффективнее реализации в программе 6.1 (в разделе 6.5 мы увидим, что она работает почти вдвое быстрее). В данной книге нас интересуют как элегантные и эффективные алгоритмы, так и элегантные и эффективные реализации этих алгоритмов. В данном случае алгоритмы несколько отличаются друг от друга — правильнее назвать функцию sort из программы 6.1 неадаптивной (nonadaptive) сортировкой вставками. Глубокое понимание свойств алгоритма — лучшее руководство для разработки его реализации, которая может эффективно использоваться в различных приложениях.

В отличие от сортировки выбором, время выполнения сортировки вставками зависит главным образом от исходного порядка ключей во входных данных. Например, если файл большой, а ключи уже упорядочены (или почти упорядочены), то сортировка вставками выполняется быстро, а сортировка выбором — медленно. Более полное сравнение алгоритмов сортировки приведено в разделе 6.5.

Упражнения

6.15. Покажите в стиле рис 6.3 процесс упорядочения файла E A S Y Q U E S T I O N методом вставок.

6.16. Приведите реализацию сортировки вставками, в которой внутренний цикл оформлен с помощью оператора while с завершением по одному из двух условий, описанных в тексте.

6.17. Для каждого из условий цикла while в упражнении 6.16 приведите пример файла из N элементов, для которого в момент выхода из цикла это условие всегда ложно.

о 6.18. Является ли сортировка вставками устойчивой?

6.19. Приведите неадаптивную реализацию сортировки выбором, основанную на поиске минимального элемента с помощью кода наподобие первого цикла for из программы 6.3.

Пузырьковая сортировка

Многие начинают знакомство с сортировкой с исключительно простого метода пузырьковой сортировки (bubble sort). В процессе своей работы она выполняет проходы по файлу с обменом местами соседних элементов, нарушающих порядок, до тех пор, пока файл не станет отсортирован. Основным достоинством пузырьковой сортировки является легкость ее реализации, хотя в этом она сравнима с методом вставок и методом выбора. В общем случае пузырьковый метод работает медленнее, однако мы рассмотрим его для полноты картины.

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

Программа 6.4. Пузырьковая сортировка

Для каждого i от l до r-1 внутренний цикл (j) по элементам a[i], ..., a[r] помещает минимальный элемент в a[i], перебирая элементы справа налево и выполняя сравнение с обменом соседних элементов. Наименьший элемент перемещается при всех таких сравнениях и " всплывает " в начало файла. Как и в сортировке выбором, индекс i перемещается по файлу слева направо, а элементы слева от него находятся в окончательных позициях.

template <class Item>
void bubble(Item a[], int l, int r)
  { for (int i = l; i < r; i++)
    for (int j = r; j > i; j-- )
      compexch(a[j-1], a[j]);
  }
      

Быстродействие программы 6.4 можно повысить, тщательно оптимизировав внутренний цикл примерно так же, как это было сделано в разделе 6.3 для сортировки вставками (см. упражнение 6.25). В самом деле, сравните коды: программа 6.4 практически идентична неадаптивной сортировке вставками из программы 6.1. Они отличаются только тем, что в сортировке вставками внутренний цикл for перебирает левую (отсортированную) часть массива, а в пузырьковой сортировке — правую (не обязательно упорядоченную) часть массива.

Программа 6.4 использует только инструкции compexch и поэтому не является адаптивной, однако можно повысить ее эффективность для почти упорядоченных файлов, проверяя после каждого прохода, были ли выполнены перестановки (т.е. файл полностью отсортирован, и можно выйти из внешнего цикла). Это усовершенствование ускоряет пузырьковую сортировку на некоторых типах файлов, однако, как будет показано в разделе 6.5, в общем случае оно все равно не так эффективно, как выход из внутреннего цикла сортировки вставками.

В пузырьковой сортировке ключи с малыми значениями постепенно сдвигаются влево. Поскольку проходы выполняются справа налево, каждый ключ меняется местами с ключом слева до тех пор, пока не будет обнаружен ключ с меньшим значением. На первом проходе E меняется местами с L, P и M и останавливается справа от A; затем A продвигается к началу файла, пока не остановится перед другим A, который уже находится на свом месте. Как и в случае сортировки выбором, после i-го прохода i-й по величине ключ устанавливается в окончательное положение, но при этом другие ключи также приближаются к своим окончательным позициям.

Упражнения

6.20. Покажите в стиле рис 6.4 процесс упорядочения файла E A S Y Q U E S T I O N методом пузырьковой сортировки.

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

6.22. Является ли пузырьковая сортировка устойчивой?

6.23. Объясните, почему пузырьковая сортировка лучше неадаптивной версии сортировки выбором, описанной в упражнении 6.19.

6.24. Экспериментально определите количество сэкономленных проходов для случайных файлов из N элементов, если добавить в пузырьковую сортировку проверку упорядоченности файла.

6.25. Разработайте эффективную реализацию пузырьковой сортировки с минимально возможным числом операторов во внутреннем цикле. Проверьте, что ваши " усовершенствования " не снижают быстродействие программы!

Характеристики производительности элементарных методов СОРТИРОВКИ

Сортировка выбором, сортировка вставками и пузырьковая сортировка являются квадратичными по времени алгоритмами как в худшем, так и в среднем случае; все они не требуют дополнительной памяти. Поэтому время их выполнения отличается лишь на постоянный коэффициент, хотя принципы работы существенно различаются (см. рис 6.5, рис 6.6 и рис 6.7).

Эти снимки процесса сортировки вставками (слева) и выбором (справа) случайной последовательности иллюстрируют выполнение сортировки обоими методами. Упорядоченность массива показана в виде графика зависимости a[i] от индекса i. Перед началом сортировки график представляет равномерно распределенную случайную величину, а по окончании сортировки он выглядит диагональю из левого нижнего угла в правый верхний угол. Сортировка вставками никогда не забегает вперед за текущую позицию в массиве, а сортировка выбором никогда не возвращается назад.

На этой диаграмме показаны различия в способах упорядочения файла сортировкой вставками, сортировкой выбором и пузырьковой сортировкой. Сортируемый файл представлен отрезками, которые сортируются по углу наклона. Черные отрезки означают элементы, к которым выполнялся доступ на каждом проходе сортировки; серые отрезки означают не задействованные элементы. В процессе сортировки вставками (слева) вставляемый элемент перемещается на каждом проходе примерно на полпути назад по упорядоченной части. Сортировка выбором (в центре) и пузырьковая сортировка (справа) перебирают на каждом проходе всю неотсортированную часть массива, чтобы найти в ней следующий наименьший элемент. Различие между этими методами заключается в том, что пузырьковая сортировка меняет местами каждую попавшуюся неупорядоченную пару соседних элементов, а сортировка выбором сразу помещает минимальный элемент в окончательную позицию. Это различие проявляется в том, что по мере выполнения пузырьковой сортировки неотсортированная часть массива становится все более упорядоченной.

Стандартная пузырьковая сортировка (слева) похожа на сортировку выбором тем, что на каждом проходе один элемент занимает свою окончательную позицию, но одновременно она асимметрично привносит упорядоченность в остальную часть массива. Поочередная смена направления просмотра массива (т.е. просмотр от начала до конца массива меняется на просмотр от конца до начала и наоборот) дает новую разновидность пузырьковой сортировки, получившей название шейкерной сортировки (справа), которая заканчивается быстрее (см. упражнение 6.30).

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

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

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

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

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

Для файлов небольших размеров сортировка вставками и сортировка выбором работают примерно в два раза быстрее пузырьковой сортировки, однако время выполнения любого из этих видов квадратично зависит от размера файла (если размер файла увеличивается в 2 раза, то время его сортировки возрастает в 4 раза). Ни один из этих методов не следует использовать для сортировки больших случайно упорядоченных файлов — например, для сортировки Шелла (см. раздел 6.6) показатели, соответствующие приведенным в таблице, не превышают 2. При большой трудоемкости сравнений — например, когда ключи представлены в виде строк — сортировка вставками работает гораздо быстрее, чем два других способа, т.к. в ней выполняется гораздо меньше сравнений. Здесь не рассмотрена ситуация, когда трудоемкими являются операции обмена; в таких случаях лучшей является сортировка выбором.

Обозначения:

Чтобы сделать выводы о времени выполнения на основании лемм 6.1—6.5, необходимо проанализировать относительную стоимость операций сравнения и обмена, а этот фактор, в свою очередь, зависит от размера элементов и ключей (см. таблицу 6.1). Например, если элементы представляют собой ключи из одного слова, то операция обмена (требующая четырех доступов к массиву) должна быть в два раза более трудоемкой, чем операции сравнения. В такой ситуации время выполнения сортировки вставками и сортировки выбором примерно соизмеримы, а пузырьковая сортировка работает медленнее. Но если элементы гораздо больше ключей, то лучшей является сортировка выбором.

Пусть, например, требуется отсортировать 1000 элементов, каждый из которых состоит из ключа длиной 1 слово и данных длиной 1000 слов, и нужно фактически переупорядочить эти элементы. Тогда трудно найти что-либо лучше сортировки выбором, поскольку время выполнения будет в основном определяться стоимостью перемещения всего миллиона слов данных. В разделе 6.8 будут рассмотрены альтернативы переупоря-дочиванию данных.

Упражнения

6.26. Какой из трех элементарных методов (сортировка выбором, сортировка вставками и пузырьковая сортировка) выполняется быстрее для файла со всеми одинаковыми ключами?

6.27. Какой из трех элементарных методов выполняется быстрее для файла, упорядоченного по убыванию?

6.28. Приведите пример файла из 10 элементов (используйте ключи от A до J), в процессе сортировки которого пузырьковая сортировка выполняет меньше сравнений, чем метод вставок — либо докажите, что такой файл не существует.

6.29. Покажите, что для любого элемента каждый проход пузырьковой сортировки уменьшает количество элементов слева, больших его, в точности на 1 (если оно не было равно 0).

6.30. Реализуйте вариант пузырьковой сортировки, который попеременно выполняет проходы по данным слева направо и справа налево. Этот (более быстродействующий, но и более сложный) алгоритм называется шейкерной сортировкой (shaker sort) .

6.31. Покажите, что лемма 6.5 не выполняется для шейкерной сортировки (см. упражнение 6.30).

6.32. Реализуйте сортировку выбором на PostScript (см. раздел 4.3 ) и воспользуйтесь полученной реализацией для построения рисунков вида 6.5—6.7. Можно применить рекурсивную реализацию или прочитать в руководстве по PostScript о циклах и массивах.

Сортировка Шелла

Сортировка вставками работает медленно, поскольку в ней выполняются обмены только соседних элементов, и любой элемент может сдвинуться лишь на одну позицию за один шаг. Например, если элемент с наименьшим ключом оказался в конце массива, потребуется N шагов, чтобы он занял нужное место. Сортировка Шелла (shellsort) представляет собой простое расширение метода вставок, быстродействие которого достигается за счет возможности обмена далеко отстоящих друг от друга элементов.

Идея заключается в переупорядочении файла таким образом, чтобы совокупность его h-ых элементов (начиная с любого) образовывала отсортированный файл. Такой файл называется h-упорядоченным (h-sorted). Другими словами, h-упорядоченный файл представляет собой h независимых, упорядоченных и перемежающихся файлов. В процессе h-сортировки при больших значениях h могут меняться местами элементы массива, расположенные далеко друг от друга — это облегчает последующую h-сортировку при меньших значениях h. Использование такой процедуры для любой последовательности значений h, которая заканчивается значением 1, дает упорядоченный файл. В этом и заключается суть сортировки Шелла.

Один из способов реализации сортировки Шелла заключается в независимой сортировке вставками каждого из h подфайлов для каждого h. Несмотря на очевидную простоту этого процесса, возможен еще более простой подход — именно благодаря независимости подфайлов. В процессе h-сортировки файла каждый элемент просто вставляется среди предшествующих элементов в соответствующем h-подфайле, сдвигая большие элементы вправо (см. рис 6.8). Для этого применяется сортировка вставками, только в ней перемещение по файлу выполняется увеличением или уменьшением индекса на h, а не на 1. Тогда реализация сортировки Шелла сводится к обычным проходам сортировки вставками, как в программе 6.5, но для ряда приращений h. Работа программы показана на рис 6.9.

А вот какую последовательность шагов следует использовать? В общем случае на этот вопрос трудно найти правильный ответ.

Программа 6.5. Сортировка Шелла

Если отказаться от использования сигнальных ключей и заменить в сортировке вставками каждое " 1 " на " h " , то полученная программа будет выполнять h-сортировку файла. Добавление внешнего цикла, изменяющего значение шага, дает компактную реализацию сортировки Шелла, в которой используется последовательность шагов 1 4 13 4 0 121 364 1093 3280 9841 . . .

template <class Item>
void shellsort(Item a[], int l, int r)
  { int h;
    for (h = 1; h <= (r-l)/9; h = 3*h+1) ;
    for ( ; h > 0; h /= 3)
      for (int i = l+h; i <= r; i++)
        { int j = i; Item v = a[i];
while (j >= l+h  v < a[j-h])
  { a[j] = a[j-h]; j -= h; }
a[j] = v;
        }
  }
      

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

В верхней части данной диаграммы показан процесс 4-сортировки файла из 15 элементов. Сначала выполняется сортировка вставками подфайла в позициях 0, 4, 8, 12, затем сортировка вставками подфайла в позициях 1, 5, 9, 13, потом сортировка вставками подфайла в позициях 2, 6, 10, 14 и, наконец, сортировка вставками подфайла в позициях 3, 7, 11. Но все четыре подфайла независимы друг от друга, так что тот же результат можно получить, вставляя каждый элемент в соответствующую позицию в его подфайле и перемещаясь назад шагами через четыре элемента (внизу). Нижняя диаграмма получается из первых рядов каждой части верхней диаграммы, затем из вторых рядов каждой части и т.д.

Сортировка файла при помощи 13-сортировки (сверху), затем 4-сортировки (в центре) и 1-сортировки (внизу) не требует выполнения большого количества сравнений (судя по количеству неза-штрихованных элементов). Завершающий проход — обычная сортировка вставками, но при этом ни один из элементов не перемещается далеко, в силу упорядоченности, внесенной двумя первыми проходами.

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

Многие другие последовательности шагов позволяют получить еще более эффективную сортировку, однако программу 6.5 трудно ускорить более чем на 20% даже в случае сравнительно больших значений N. Одной из таких последовательностей является 1 8 2 3 77 281 1073 4193 16577 . . . , т.е. последовательность 4i+1 + 3 • 2i + 1 для i > 0 , которая, похоже, работает быстрее в худшем случае (см. лемму 6.10). На рис 6.11 показано, что эта последовательность — а также последовательность Кнута и многие другие последовательности шагов — обладают похожими динамическими характеристиками для файлов больших размеров. Вполне возможно, что существуют лучшие последовательности. Несколько идей по улучшению последовательностей шагов рассматриваются в упражнениях.

Но существуют и плохие последовательности шагов: например, 1 2 4 8 16 32 64 128 256 512 1024 2048 ... (первоначальная последовательность, предложенная Шеллом еще в 1959 г. (см. раздел ссылок)), обычно приводит к низкой производительности, поскольку элементы в нечетных позициях не сравниваются с элементами в четных позициях вплоть до последнего прохода. Этот эффект заметен для случайно упорядоченных файлов и становится катастрофическим в худшем случае: время выполнения вырождается до квадратичного, если, например, половина элементов с меньшими значениями находится в четных позициях, а половина элементов с большими значениями — в нечетных позициях (см. упражнение 6.36).

Программа 6.5 вычисляет следующий шаг, разделив текущий шаг на 3 после инициализации, гарантирующей использование одной и той же последовательность шагов. Другой вариант — начать сортировку с h = N/3 или с какой-то другой функции от N. Но лучше избегать таких стратегий, т.к. некоторые значения N могут дать плохие последовательности шагов наподобие описанной выше.

Наше описание эффективности сортировки Шелла не отличается особой точностью, поскольку никто не смог выполнить анализ данного алгоритма. Этот пробел в наших знаниях затрудняет не только вычисление различных последовательностей шагов, но и аналитическое сравнение сортировки Шелла с другими методами.

Каждый проход сортировки Шелла вносит упорядоченность в файл как целое. Сначала выполняется 40-сортировка файла, затем 13-сортировка, потом 4-сортировка, и, наконец, 1-сортировка. Каждый проход приближает файл к окончательному состоянию.

Не известно даже функциональное выражение для времени выполнения сортировки Шелла (более того, это выражение зависит от выбора последовательности шагов). Кнут обнаружил, что неплохо описывают ситуацию функциональные формы N (logN)2 и N1,25 , а дальнейшие исследования показали, что некоторые виды последовательностей описываются более сложными выражениями вида $$N^{1+l/ \sqrt{lgN}}$$ .

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

Представленный на рисунке процесс выполнения сортировки Шелла можно сравнить с закрепленной в углах резиновой лентой, стягивающей все точки ленты к диагонали. Здесь показаны две последовательности шагов: 121 40 13 4 1 (слева) и 209 109 41 19 5 1 (справа). Вторая последовательность требует на один проход больше, но выполняется быстрее, поскольку каждый ее проход более эффективен.

Нижний ряд изображает массив, где заштрихованные квадратики обозначают элементы, которые должны быть меньше или равны крайнему правому элементу, если массив 4- и 13-упорядочен. 4 верхних ряда показывают происхождение нижнего ряда. Если правый элемент находится в массиве в позиции i, то 4-упорядочение означает, что элементы массива в позициях i — 4, i — 8, i — 12, ... меньше или равны ему (верхний ряд). 13-упорядочение означает, что меньше или равен ему элемент i — 13, а вместе с ним, в силу 4-упорядочения, и элементы i — 17, i — 21, i — 25, ... (второй ряд сверху). Аналогично меньше или равен ему элемент в позиции i — 26, а вместе с ним, в силу 4-упорядочения, и элементы i — 30, i — 34, i — 38, ... (третий ряд сверху), и т.д. Оставшиеся незаштрихованными квадратики — те, которые могут быть больше, чем элемент слева; здесь их не более 18 (самый дальний элемент находится в позиции i — 36). Поэтому для сортировки вставками 13- и 4-упорядоченного файла из N элементов нужно выполнить не более 18N сравнений.

Последовательности шагов, которые рассматривались до сих пор, эффективны потому, что в них соседние элементы взаимно просты. Другое семейство последовательностей шагов эффективно именно благодаря тому, что такие элементы не являются взаимно простыми.

В частности, из доказательства леммы 6.8 следует, что в процессе завершающей сортировки вставками 2- и 3-упорядоченного файла каждый элемент перемещается не более чем на одну позицию. Это значит, что такой файл можно упорядочить одним проходом пузырьковой сортировки (а дополнительный цикл сортировки вставками не нужен). Далее, если файл 4-упорядочен и 6-упорядочен, то каждый элемент также перемещается максимум на одну позицию при его 2-сортировке (поскольку каждый подфайл 2- и 3-упорядочен). И если файл 6-упорядочен и 9-упорядочен, то каждый элемент перемещается не более чем на одну позицию при его 3-сортировке. Продолжая эти рассуждения, мы приходим к идее, которую опубликовал Пратт в 1971 г. (см. раздел ссылок).

Метода Пратта основан на использовании треугольника шагов, причем каждое входящее в этот треугольник число в два раза больше числа, стоящего сверху справа, и в три раза больше числа, стоящего в треугольнике сверху слева.

Если мы используем эти числа снизу вверх и справа налево как последовательность шагов в сортировке Шелла, то каждому шагу х в нижнем ряду предшествуют значения 2х и 3х. Поэтому каждый подфайл оказывается 2-упорядочен и 3-упорядочен, и в процессе всей сортировки ни один элемент не передвигается больше чем на одну позицию!

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

Задача построения хорошей последовательности шагов для сортировки Шелла представляет собой прекрасный пример сложного поведения простых алгоритмов. разумеется, мы не сможем выполнять такой же подробный анализ всех рассматриваемых алгоритмов: и место в книге ограничено, и, как и в случае сортировки Шелла, может понадобиться математический аппарат, выходящий за рамки книги; возможны даже незавершенные исследовательские задачи. Однако многие алгоритмы, рассматриваемые в данной книге, появились в результате интенсивных аналитических и эмпирических исследований, выполненных многими исследователями за несколько последних десятилетий, и мы просто воспользуемся плодами их трудов. Эти исследования показывают, что задача повышения эффективности сортировки может как представлять собой интересную научную проблему, так и давать практическую отдачу, даже в случаях простых алгоритмов. В таблица 6.2 приведены эмпирические данные, которые показывают, что некоторые способы построения последовательностей шагов хорошо работают на практике; относительно короткая последовательность 1 8 23 77 281 1073 4193 16577 . . . — одна из самых простых среди используемых в реализациях сортировки Шелла.

Сортировка Шелла работает в несколько раз быстрее других элементарных методов сортировки, даже если шаги являются степенями 2, а некоторые специальные последовательности шагов ускоряют ее в 5 и более раз. Три лучших последовательности, приведенные в данной таблице, существенно различаются по их построению. Сортировка Шелла вполне пригодна для практического применения даже в случае больших файлов — в отличие от сортировки выбором, сортировки вставками и пузырьковой сортировки (см. таблицу 6.1).

Обозначения:

Из рис 6.13 видно, что сортировка Шелла достаточно быстро работает на различных видах файлов, а не только на случайно упорядоченных. Построить файл, на котором сортировка Шелла работает медленно для заданной последовательности шагов — достаточно сложная задача (см. упражнение 6.42). Как уже было сказано, существуют плохие последовательности шагов, при использовании которых сортировка Шелла может выполнить квадратичное количество сравнений в худшем случае (см. упражнение 6.36), однако доказано, что для большого количества других последовательностей этот показатель намного ниже. После выполнения нескольких проходов все эти файлы упорядочены одинаково — значит, время выполнения сортировки не очень чувствительно к виду входных данных.

На представленных диаграммах показана работа сортировки Шелла с последовательностью шагов 2 09 109 41 19 5 1 для равномерного распределения, нормального распределения, почти упорядоченного файла, почти обратно упорядоченного файла и случайно упорядоченного файла с 10 различными значениями ключей (слева направо, сверху). Время выполнения каждого прохода зависит от степени упорядоченности файла перед началом прохода.

Сортировка Шелла хорошо работает во многих приложениях, поскольку она упорядочивает за приемлемое время даже довольно большие файлы и реализуется в виде компактной и легко отлаживаемой программы. В последующих нескольких главах мы ознакомимся с методами сортировки, которые более эффективны, но работают, допустим, лишь в два раза быстрее (а то и меньше) при небольших значениях N и существенно сложнее. В общем, если нужно быстрое решение задачи сортировки, но нет желания возиться с интерфейсом системной сортировки, воспользуйтесь сортировкой Шелла, а потом решите, стоит ли напрягаться, чтобы заменить его более совершенным методом.

Упражнения

6.33. Устойчива ли сортировка Шелла?

6.34. Покажите, как следует реализовать сортировку Шелла с последовательностью шагов 1 8 23 77 281 1073 4193 16577 . . . с непосредственным вычислением последовательных шагов — примерно как в коде для последовательности Кнута.

6.35. Приведите диаграммы, соответствующие рис 6.8 и рис 6.9 для ключей E A S Y Q U E S T I O N.

6.36. Определите время выполнения сортировки Шелла с последовательностью шагов 1 2 4 8 16 32 64 128 264 512 1024 2048 . . . для упорядочения файла, состоящего из целых чисел 1, 2, ..., N в нечетных позициях и N + 1, N + 2, ..., 2N в четных позициях.

6.37. Напишите программу-драйвер для сравнения последовательностей шагов сортировки Шелла. Введите последовательности из стандартного ввода (по одной в строке); затем используйте их для сортировки 10 файлов с произвольной организацией длиной N = 100, 1000 и 10000. Подсчитывайте количество сравнений или замеряйте фактическое время выполнения.

6.38. Экспериментально определите, позволяет ли добавление или удаление какого-то шага улучшить последовательность шагов 1 8 23 77 281 1073 4193 16577 . . . для N = 10 000.

6.39. Экспериментально определите значение х, которое обеспечивает минимальное время сортировки случайно упорядоченных файлов, если заменить на х шаг 13 в последовательности 1 4 13 40 121 364 1093 3280 9841 . . . для N= 10000.

6.40. Экспериментально определите значение а, которое обеспечивает минимальное время сортировки случайно упорядоченных файлов для последовательности шагов 1, $$$\lfloor \alpha\rfloor$$$, $$$\lfloor \alpha^{2}\rfloor$$$, $$$\lfloor \alpha^{3}\rfloor$$$, $$$\lfloor \alpha^{4}\rfloor$$$, ... и N = 10 000.

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

6.42. Подберите файл из 100 элементов, для которого сортировка Шелла с последовательностью шагов 1 8 2 3 77 выполняет максимальное количество операций сравнения.

6.43. Докажите, что если h и k — взаимно простые числа, то любое число, большее или равное (h — 1)(k — 1), можно представить в виде линейной комбинации h и k с неотрицательными коэффициентами. Совет: покажите, что если любые два из первых h — 1 чисел, кратных k, при делении на h дают при деления на h одинаковый остаток, то h и k должны иметь общий делитель.

6.44. Экспериментально определите значения h и k, которые обеспечивают минимальное время сортировки случайно упорядоченных файлов из 10 000 элементов, если в качестве шагов сортировки используется последовательность, подобная последовательности Пратта, построенная для этих h и k.

6.45. Последовательность шагов 1 5 19 41 109 209 505 929 2161 3905 . . . построена с помощью слияния последовательностей $$$9\cdot 4^{i}-9\cdot 2^{i}+1$$$ и $$$4^{i}-3\cdot 2^{i}+1$$$ для i > 0. Сравните результаты использования этих последовательностей по отдельности с результатом использования их слияния на примере сортировки 10 000 элементов.

6.46. Последовательность шагов 1 3 7 21 48 112 336 861 1968 4592 13776 . . . получена из последовательности, состоящей из взаимно простых чисел, скажем,

1371641101,с последующим построением треугольника на манер последовательности Пратта. Только теперь i-й ряд треугольника получается умножением первого элемента в (i — 1)-ом ряду на i-й элемент базовой последовательности и умножением каждого элемента в (i — 1)-ом ряду на (i + 1)-й элемент базовой последовательности. Найдите экспериментально базовую последовательность, которая превосходит указанную выше при сортировке 10 000 элементов.

6.47. Завершите доказательства лемм 6.7 и 6.8.

6.48. Напишите реализацию, основанную на алгоритме шейкерной сортировки (упражнение 6.30), и сравните ее со стандартным алгоритмом. Совет: последовательности шагов должны существенно отличаться от последовательностей, применяемых в стандартных алгоритмах.

Сортировка других типов данных

Большинство алгоритмов сортировки вполне можно рассматривать как упорядочение массивов чисел в числовом порядке или упорядочение символов в алфавитном порядке. Действительно, эти алгоритмы обычно не зависят от типа сортируемых элементов, и поэтому их нетрудно распространить на более общие случаи. Ранее мы подробно рассмотрели вопросы разбиения программ на отдельные независимые модули, что позволяет реализовать нужные типы данных, а также абстрактные типы данных (см. и ). В данном разделе обсуждаются способы применения этих понятий для создания реализаций, интерфейсов и клиентских программ для алгоритмов сортировки. А именно, будут рассматриваться интерфейсы для:

Тип данных " элемент " позволяет использовать программы сортировки для любых типов данных, для которых определены необходимые базовые операции. Такой подход позволяет эффективно создавать реализации как для простых, так и для абстрактных типов данных. Интерфейс " массив " менее критичен для нашей задачи; мы используем его в качестве примера работы с многомодульной программой, которая имеет дело с несколькими типами данных. Здесь будет рассмотрена только одна (примитивная) реализация интерфейса массива.

Программа 6.6 является клиентской программой с теми же обобщенными возможностями, что и функция main из программы 6.1, но с дополнительным кодом для работы с массивами и элементами, инкапсулированными в отдельных модулях. Это позволяет, в частности, тестировать различные программы сортировки на различных типах данных путем замены одних модулей на другие, не внося при этом никаких изменений в клиентскую программу. Программа 6.6 обращается также к интерфейсу, где описаны операции exch и compexch, используемые в реализациях алгоритмов сортировки. Можно было бы включить их в интерфейс Item.h, однако реализации в программе 6.1 имеют легко понятную семантику при определенных операциях = и <, поэтому проще содержать их в одном модуле, которым могут пользоваться все реализации сортировки для всех типов элементов. Чтобы завершить реализацию, необходимо вначале точно определить интерфейсы с типами массива и элемента.

Программа 6.6. Драйвер сортировки массивов

Данный драйвер для основных алгоритмов сортировки массивов использует три явных интерфейса: (1) для типа данных, который инкапсулирует операции для обобщенных элементов; (2) несколько более высокий уровень для функций exch и compexch, используемых в реализациях; и (3) для функций, которые инициализируют и выводят (а также сортируют!) массивы. Такое разбиение драйвера на модули позволяет без каких-либо изменений применять каждую реализацию сортировки для упорядочения различных типов данных, совместно использовать реализации операций обмена и сравнения-обмена, а также компилировать функции для массивов отдельно (возможно, для их использования в других драйверах).

#include <stdlib.h>
#include "Item.h"
#include "exch.h"
#include "Array.h"
main(int argc, char *argv[])
  { int N = atoi(argv[1]), sw = atoi(argv[2]);
    Item *a = new Item[N];
    if (sw) rand(a, N); else scan(a, N);
    sort(a, 0, N-1);
    show(a, 0, N-1);
  }
      

Интерфейс программы 6.7 определяет примеры высокоуровневых операций, которые могут понадобиться при работе с массивами. Необходима возможность инициализировать массив либо случайными ключами, либо ключами из стандартного ввода, необходима возможность сортировать элементы (естественно!), и необходима возможность вывода содержимого массива. Это лишь несколько примеров; в конкретном приложении может понадобиться определить и другие операции (примером подобного интерфейса может служить класс Vector из библиотеки стандартных шаблонов). Программа 6.7 позволяет подставлять различные реализации разных операций без внесения изменений в клиентскую программу, которая использует этот интерфейс — в данном случае, в функцию main программы 6.6. Реализациями функции sort могут служить различные рассматриваемые нами реализации сортировок. В программе 6.8 приведены простые реализации других функций. Модульная организация позволяет подставлять другие реализации, нужные в конкретных приложениях. Например, может понадобиться реализация функции show, которая выводит только часть массива при тестировании работы на очень больших массивах.

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

Программа 6.7. Интерфейс для типа данных " массив "

Данный интерфейс Array.h определяет высокоуровневые функции для массивов абстрактных элементов: инициализация случайными значениями, инициализация значениями из стандартного ввода, вывод содержимого и сортировку содержимого.

template <class Item>
  void rand(Item a[], int N);
template <class Item>
  void scan(Item a[], int N);
template <class Item>
  void show(Item a[], int l, int r);
template <class Item>
  void sort(Item a[], int l, int r);
      

Программа 6.8. Реализация типа данных " массив "

Данный код представляет собой реализацию функций, определенных в программе 6.7. Здесь используются типы данных и базовые функции для работы с ними, которые определены в отдельном интерфейсе (см. программу 6.9).

#include <iostream.h>
#include <stdlib.h>
#include "Array.h"
template <class Item>
  void rand(Item a[], int N)
    { for (int i = 0; i < N; i++) rand(a[i]); }
template <class Item>
  void scan(Item a[], int N)
    {
      for (int i = 0; i < N; i++)
        if (!scan(a[i])) break;
      N = i;
    }
template <class Item>
  void show(Item a[], int l, int r)
    { for (int i = l; i <=r; i++)
      show(a[i]);
      cout << endl;
    }
      

Программа 6.9. Пример интерфейса для типа данных " элемент "

Файл Item.h, включенный в программу 6.6, дает определение типа данных для сортируемых элементов. В этом примере элементами являются небольшие записи, состоящие из целочисленных ключей и информации в виде числа с плавающей точкой. Мы объявляем, что перегруженная операция < будет реализована отдельно, равно как и три функции: scan (считывает Item в свой аргумент), rand (сохраняет случайный Item в своем аргументе) и show (выводит Item).

typedef struct record { int key; float info; } Item;
  int operator<(const Item, const Item);
int scan(Item);
void rand(Item); void show(const Item);
      

Программа 6.10. Пример реализации типа данных " элемент "

Этот код является реализацией перегруженной операции < и функций scan, rand и show, которые объявлены в программе 6.9. Поскольку записи представляют собой небольшие структуры, в функции exch можно использовать встроенный оператор присваивания, не беспокоясь о затратах на копирование элементов.

#include <iostream.h>
#include <stdlib.h>
#include "Item.h"
int operator<(const Item A, const Item B)
  { return A.key < B.key; }
int scan(Item x)
  { return (cin >> x.key >> x.info) != 0; }
void rand(Item x)
  { x.key = 100 0*(1.0*rand()/RAND MAX);
  x.info = 1.0*rand()/RAND MAX; }
void show (const Item x)
  { cout << x.key << " " << x.info << endl; }
      

Например, тип Item может быть абстрактным типом данных, определенным в виде класса С++, а ключи могут быть функциями-членами класса, а не членами структуры. Такие АТД рассматриваются в .

Программы 6.6—6.10 вместе с любыми подпрограммами сортировки (без изменений) из разделов 6.2—6.6, выполняют проверку сортировки на небольших записях. Написав подобные интерфейсы и реализации для других типов данных, мы сможем применять наши реализации для сортировки различных видов данных — таких как комплексные числа (см. упражнение 6.50), векторы (см. упражнение 6.55) или полиномы (см. упражнение 6.56) — без каких-либо изменений в кодах программ сортировки. Для более сложных типов элементов придется написать более сложные интерфейсы и реализации, однако эта задача полностью отделена от вопросов построения алгоритмов сортировки, которые нас здесь интересуют. Одни и те же механизмы можно задействовать для большинства методов сортировки, которые рассмотрены в данной главе, а также будут изучаться в лекциях 7—9 . В разделе 6.10 мы подробно проанализируем одно существенное исключение — оно дает начало целому семейству важных алгоритмов сортировки, которые должны иметь совсем другое оформление; о них речь пойдет в .

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

Упражнения

6.49. Напишите версии программ 6.9 и 6.10, в которых вместо функций scan и show используются перегруженные операции << и >>, а также измените программу 6.8, чтобы учесть изменения в интерфейсе.

6.50. Напишите интерфейс и реализацию для обобщенного типа данных элемента, который позволит сортировать комплексные числа х + iy, используя в качестве ключа модуль $$$\sqrt{x^{2}+y^{2}}$$$. Совет: эффективность можно повысить, игнорируя квадратный корень.

6.51. Напишите интерфейс, который определяет абстрактный тип данных первого класса для обобщенных элементов (см. раздел 4.8 ), и реализацию, в которой, как и в предыдущем упражнении, элементами являются комплексные числа. Протестируйте полученную программу с помощью программ 6.3 и 6.6.

6.52. Добавьте в тип данных массива в программах 6.8 и 6.7 функцию check, которая проверяет, упорядочен ли массив.

6.53. Добавьте в тип данных массива в программах 6.8 и 6.7 функцию testinit, которая генерирует тестовые данные с распределениями, похожими на приведенные на рис 6.13. У этой функции должен быть целочисленный аргумент, через который клиентская программа сможет задать нужное распределение.

6.54. Измените программы 6.7 и 6.8, чтобы реализовать абстрактный тип данных. (Ваша реализация должна размещать массив в памяти и сопровождать его так, как в реализациях стеков и очередей из )

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

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

Сортировка индексов и указателей

Разработка реализации типа данных строки, наподобие программ 6.9 и 6.10, представляет особый интерес, поскольку строки символов широко используются как ключи сортировки. Строки могут иметь различные длины, в том числе и очень большие, поэтому создание, удаление и сравнение строк могут потребовать значительных затрат, и следует проявить особую осторожность, чтобы в реализации не было излишних операций этого вида.

С этой целью мы применяем такое представление данных, которое состоит из указателя (на массив символов) — стандартное представление строки в стиле языка С. А первая строка программы 6.9 изменяется на

typedef struct { char *str; } Item;
      

что превращает ее в интерфейс для строк. Указатель помещается в структуру потому, что C++ не позволяет перегружать операцию < для встроенных типов, к которым относятся указатели. Подобные ситуации не являются чем-то необычным в C++: класс (или структура), который приспосабливает интерфейс для другого типа данных, называется классом-оболочкой (wrapper class). В данном случае мы не требуем от класса-оболочки слишком многого, но в некоторых случаях возможны более сложные реализации. Вскоре будет рассмотрен еще один пример.

Программа 6.11 представляет собой реализацию для строковых элементов. Перегружен ная операция < легко реализуется с помощью функции сравнения строк из библиотеки С, но реализовать функцию scan (и rand) труднее, поскольку нужно учитывать распределение памяти для строк. Программа 6.11 использует метод, который был рассмотрен в (программа 3.17) — использование буфера в реализации типа данных. Другие варианты — динамическое выделение памяти для каждой строки, использование реализации класса вроде класса String из библиотеки стандартных шаблонов, либо использование буфера в клиентской программе. Для сортировки строк символов можно воспользоваться любым из этих подходов (с соответствующими интерфейсами), используя любую реализацию сортировки из рассмотренных нами.

Мы сталкиваемся с необходимостью подобного управления памятью всякий раз, когда разбиваем программу на модули. Кто будет отвечать за управление памятью, соответствующее конкретной реализации какого-то объекта — клиентская программа, реализация типа данных или система? На этот вопрос нет готового однозначного ответа (хотя некоторые разработчики языков программирования являются ярыми приверженцами одного из вариантов). В некоторых современных системах программирования (включая некоторые реализации С++) имеются встроенные механизмы автоматического управления памятью. Мы еще вернемся к этому вопросу в , при обсуждении реализации более сложных абстрактных типов данных.

Программа 6.11 представляет собой пример сортировки указателей (pointer sort), и мы вскоре рассмотрим этот принцип в более общем виде. Другой простой подход к сортировке без (непосредственных) перемещений элементов заключается во введении индексного массива, когда доступ к ключам элементов выполняется только для их сравнения.

Программа 6.11. Реализация типа данных для строковых элементов

Эта реализация позволяет упорядочивать строки в стиле языка С, используя наши программы сортировки. Для представления данных используется структура, которая содержит указатель на символ (см. в тексте), благодаря чему сортировка выполняется для массива указателей на символы, переупорядочивая их таким образом, что строки, на которые они указывают, выстраиваются в алфавитно-цифровом порядке. Чтобы наглядно продемонстрировать процесс управления памятью, здесь определен буфер памяти фиксированного размера, где хранятся символы строк; наверно, удобнее было бы динамическое распределение памяти. Реализация функции rand опущена.

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include "Item.h"
static char buf[100000];
static int cnt = 0;
int operator<(const Item a, const Item b)
  { return strcmp(a.str, b.str) < 0; }
void show(const Item x)
  { cout << x.str << " "; }
int scan(Item x)
  { int flag = (cin >> (x.str = buf[cnt])) != 0;
    cnt += strlen(x.str)+1;
    return flag;
  }
      

Предположим, что сортируемые элементы находятся в массиве data[0], ..., data[N-1], и по каким-то причинам мы не хотим перемещать их (возможно, из-за огромных размеров). Тогда для упорядочения используется второй массив а с индексами сортируемых элементов. Первоначально его элементы a[i] инициализируются значениями i для i = 0, ..., N-1. То есть вначале a[0] содержит индекс первого элемента данных, a[1] — второго элемента данных и т.д. А сама сортировка сводится к такому переупорядочению массива индексов, что a[0] будет содержать индекс элемента данных с наименьшим значением ключа, a[1] — индекс следующего элемента данных с минимальным значением ключа и т.д. Тогда эффект упорядочения достигается доступом к ключам через индексы — например, так можно вывести массив в порядке возрастания его ключей.

В этом случае нужно указать, что сортировка выполняет упорядочивание индексов массива, а не просто целых чисел. Тип Index следует определить так, чтобы можно было перегрузить операцию < следующим образом:

int operator<(const Index i, const Index j)
  { return data[i] < data[j]; }
      

Теперь при наличии массива a объектов типа Index любая из наших функций сортировки переупорядочит индексы в массиве a так, что значение a[i] будет равно числу ключей, меньших, чем ключ элемента data[i] (индекс a[i] в отсортированном массиве). (Для простоты здесь предполагается, что данные представляют собой просто ключи, а не элементы в полном объеме; этот принцип можно распространить на более крупные и сложные элементы — нужно лишь изменить операцию < для доступа конкретно к ключам таких элементов, либо воспользоваться функцией-членом класса для вычисления ключей.) Для определения типа Index используется класс-оболочка:

struct intWrapper
  {
    int item;
    intWrapper(int i = 0)
      { item = i; }
    operator int() const
      { return item; }
  };
  type def intWrapper Index;
      

Конструктор в данной структуре преобразует любое значение типа int в Index, а операция приведения типа int() преобразует любое значение Index обратно в int — значит, объекты типа Index можно использовать везде, где возможно применение объектов встроенного типа int.

Пример индексации, где одни и те же элементы сортируются по двум различным ключам, представлен на рис 6.14. Одна клиентская программа может определить операцию < для работы с одним ключом, а другая — для использования другого ключа, но обе они могут воспользоваться одной и той же программой сортировки для построения массива индексов, который обеспечит доступ к элементам в порядке возрастания их ключей.

Работая с индексами, а не с самими записями, можно упорядочить массив одновременно по нескольким ключам. В этом примере данные могут быть фамилиями студентов и их оценками, второй столбец представляет собой результат индексной сортировки по именам, а третий столбец — результат индексной сортировки по убыванию оценок. Например, Wilson — фамилия, идущая по алфавиту последней, и ей соответствует десятая оценка, а фамилия Adams является первой по алфавиту, и ей соответствует шестая оценка. Переупорядочение N различных неотрицательных целых чисел, меньших N, в математике называется перестановкой, т.е. индексная сортировка выполняет перестановку. В математике перестановки обычно определяются как переупорядочения целых чисел от 1 до N; мы же будем употреблять числа от 0 до N— 1, чтобы подчеркнуть прямую связь между перестановками и индексами массивов в С++.

Такой поход с использованием массива индексов вместо реальных элементов работает в любом языке программирования, который поддерживает массивы. Другая возможность заключается в использовании указателей, как в реализации недавно рассмотренного строкового типа данных (программа 6.11). В случае сортировки массива элементов фиксированного размера сортировка указателей практически эквивалентна индексной сортировке, только к каждому индексу прибавляется адрес массива. Однако сортировка указателей — гораздо более общий вид сортировки, т.к. указатели могут указывать на что угодно, а сортируемые элементы не обязательно должны иметь фиксированный размер. Как и в случае индексной сортировки, если а есть массив указателей на ключи, то результатом вызова функции sort будет такое переупорядочение указателей, что последовательный доступ к ним означает доступ к отсортированным ключам. Операции сравнения реализуются с помощью обращений по указателям, а операции обмена реализуются как обмен указателей.

Функция qsort из стандартной библиотеки C представляет собой сортировку указателей (см. программу 3.17), которая принимает функцию сравнения в качестве аргумента (а не использует перегруженную операцию <, как мы обычно делаем). У этой функции четыре аргумента: массив, количество сортируемых элементов, размер элементов и указатель на функцию, которая выполняет сравнение двух элементов, обращаясь к ним через заданные указатели. Например, если тип Item определен как char*, то приведенный ниже код реализует сортировку строк в соответствии с принятыми нами соглашениями:

int compare (void *i, void *j)
  { return strcmp(*(Item *)i, *(Item *)j); }
void sort (Item a[], int l, int r)
  { qsort(a, r-l+1, sizeof(Item), compare); }
      

В этом интерфейсе не указан работающий алгоритм, хотя на практике широко применяется быстрая сортировка см. . В мы рассмотрим многие причины, почему это так. В данной главе, а также в главах 7—11, мы постепенно разберемся, почему в некоторых конкретных случаях более удобны другие методы сортировки. Кроме того, мы рассмотрим возможности ускорения вычислений в тех случаях, когда время выполнения сортировки является критическим фактором в приложении.

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

struct record { char[30] name; int num; }
      

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

Программа 6.12. Интерфейс типа данных для элементов в виде записей

Записи содержат два ключа: ключ строкового типа (например, фамилия) в первом поле и целое число (например, оценка) — во втором поле. Мы считаем, что эти записи слишком большие, чтобы их копировать, поэтому Item определяется как структура, содержащая указатель на запись.

struct record { char name[30]; int num; };
typedef struct { record *r; } Item;
int operator<(const Item, const Item);
void rand(Item);
void show(const Item);
int scan(Item);
      

Программа 6.13. Реализация типа данных для элементов в виде записей

Приведенные ниже реализации функций scan и show для записей работают в стиле реализации строкового типа данных из программы 6.11: они выделяют память для хранения строк и работают с этой памятью. Реализация операции < находится в отдельном файле, чтобы подставлять различные реализации и таким образом менять ключи сортировки без изменения остального кода.

static record data[maxN];
static int cnt = 0;
void show(const Item x)
  { cout << x.r->name << " " << x.r->num << endl; }
int scan(Item x)
  {
    x.r = data[cnt++];
    return (cin >> x.r->name >> x.r->num) != 0;
  }
      

Например, если откомпилировать программу 6.13 вместе с файлом, содержащим код

#include "Item.h"
int operator<(const Item a, const Item b)
  { return a.r->num < b.r->num); }
      

то получим тип данных элементов, для которых любая из наших реализаций функции sort выполнит сортировку указателей по целочисленному полю; а если откомпилировать программу 6.13 вместе с файлом, содержащим код

#include "Item.h" include <string.h>
int operator<(const Item a, const Item b)
  { return strcmp(a.r->name, b.r->name) < 0; }
      

то получим тип данных элементов, для которых любая из наших реализаций функции sort выполнит сортировку указателей по строковому полю.

Индексы или указатели используются в основном для того, чтобы не перемещать сортируемые данные. Можно " отсортировать " файл, даже если разрешено только его чтение. Более того, используя несколько массивов индексов или указателей, можно сортировать один и тот же файл по нескольким ключам (см. рис 6.14). Такая возможность обработки данных без их изменения полезна во многих ситуациях.

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

Во многих случаях нет необходимости физического переупорядочения данных в соответствии с порядком размещения соответствующих индексов, и данные можно выбирать по порядку с помощью индексного массива. Если такой подход почему-то не годится, то возникнет обычная задача классического программирования: каким образом переупорядочить записи файла, если для него выполнена индексная сортировка? Код

for (i=0; i < N; i++) datasorted[i] = data[a[i]];
      

тривиален, однако требует дополнительной памяти, достаточной для размещения еще одной копии массива. А что делать, если для второй копии не хватает места? Ведь нельзя же просто записать data[i] = data[a[i]], ибо тогда предыдущее значение data[i] окажется затертым — вполне возможно, что преждевременно.

На рис 6.15 показан способ решения этой проблемы за один проход по файлу. Чтобы переместить первый элемент на то место, где он должен быть, мы переносим элемент из этой позиции на его место и т.д. В процессе этих перемещений однажды попадется элемент, который нужно переместить в первую позицию, после чего на своих местах окажется некоторый цикл элементов. Далее мы перейдем ко второму элементу и выполним те же операции для его цикла, и так далее (любые элементы, которые уже находятся в своих окончательных позициях (a[i] = i), принадлежат циклам длиной 1 и не перемещаются).

Чтобы упорядочить массив на месте, мы просматриваем его слева направо, циклически перемещая элементы, которые находятся не на своих местах. Врассмат-риваемом примере имеются четыре цикла, причем первый и последний являются вырожденными циклами из одного элемента. Второй цикл начинается с позиции 1. Элемент S запоминается во временной переменной, оставляя в позиции 1 пустое место. Перемещение второго А приводит к появлению пустого места в позиции 10. Это пустое место заполняется элементом Р, который оставляет пустое место в позиции 12. Это пустое место должно быть заполнено элементом в позиции 1, поэтому туда переносится запомненный элемент S, тем самым завершая цикл 1 10 12, который помещает эти элементы в окончательные позиции. Аналогично выполняется цикл 2 8 6 13 4 7 11 3 14 9, который и завершает сортировку.

Конкретно, для каждого значения i сохраняется значение data[i], и в индексную переменную k заносится значение i. Теперь можно считать позицию i свободной и найти элемент, который должен заполнить это место. Таким элементом является data[a[k]], и операция присваивания data[k] = data[a[k]] перемещает это пустое место в a[k]. Теперь пустое место появилось в позиции data[a[k]], и в k заносится значение a[k]. Повторяя эти действия, мы в конце концов оказываемся в ситуации, когда пустое место должно быть заполнено предварительно сохраненным значением data[i]. Когда мы помещаем элемент в какую-либо позицию, мы вносим соответствующие изменения в массив а. Для любого элемента, который уже занимает свою позицию, a[i] равно i, и вышеописанный процесс сводится к пустой операции. Перемещаясь по массиву и начиная новый цикл всякий раз, когда встречается элемент, который еще не находится на своем месте, мы перемещаем каждый элемент не более одного раза. Программа 6.14 представляет реализацию рассмотренного процесса.

Этот процесс называется перестановкой на месте (in situ permutation) или обменным упорядочением (in-place rearrangement) файла. Отметим еще раз: хотя сам по себе алгоритм весьма интересен, во многих приложениях в нем нет необходимости, ибо вполне достаточно косвенного доступа к элементам. Кроме того, если записи слишком велики относительно их количества, наиболее эффективным может оказаться вариант упорядочения обыкновенной сортировкой выбором (см. лемму 6.5).

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

Программа 6.14. Обменная сортировка

Массив data[0], ..., data[N-1] должен быть упорядочен на месте в соответствии с массивом индексов a[0], ..., a[N-1]. Любой элемент, для которого a[i] == i, уже находится на своем месте, и с ним ничего не надо делать. Иначе значение data[i] сохраняется в v, и в цикле перемещаются элементы a[i], a[a[i]], a[a[a[i]]] и т.д., пока индекс i не встретится опять. Далее этот процесс повторяется для следующего элемента, который находится не на месте, и все это продолжается в том же духе, пока не будет упорядочен весь файл, причем каждая запись будет перемещена не более одного раза.

template <class Item>
void insitu(Item data[], Index a[], int N)
  { for (int i = 0; i < N; i++)
      { Item v = data[i];
        int j, k;
        for (k = i; a[k] != i; k = a[j], a[j] = j)
{ j = k; data[k] = data[a[k]]; }
        data[k] = v; a[k] = k;
      }
  }
      

Упражнения

6.57. Приведите реализацию типа данных для элементов, которые представляют собой записи, а не указатели на записи. Такая организация данных может оказаться удобной для работы программ 6.12 и 6.13 с небольшими записями. (Учтите, что язык C++ поддерживает присваивание структур.)

6.58. Покажите, как можно использовать функцию qsort для решения задач сортировки, на которые ориентированы программы 6.12 и 6.13.

6.59. Приведите массив индексов, который получается при индексной сортировке ключей E A S Y Q U E S T I O N.

6.60. Приведите последовательность перемещений данных, необходимых для перестановки ключей E A S Y Q U E S T I O N на месте после выполнения индексной сортировки (см. упражнение 6.59).

6.61. Опишите перестановку размера N (набор значений для массива а), для которой условие a[i] != i в процессе работы программы 6.14 выполняется максимальное число раз.

6.62. Докажите, что в процессе перемещения ключей и пустых мест в программе 6.14 мы обязательно вернемся к ключу, с которого начат цикл.

6.63. Реализуйте программу, аналогичную программе 6.14, для сортировки указателей, если указатели указывают на массив из N записей типа Item.

Сортировка связных списков

Как мы знаем из , массивы и связные списки представляют собой два самых основных способа структурирования данных. Кроме того, в качестве примера обработки списков мы уже рассмотрели реализацию сортировки вставками связных списков (см. программу 3.11 в разделе 3.4 ). Во всех реализациях сортировок, рассмотренные к этому моменту, предполагается, что сортируемые данные представлены в виде массива. Эти реализации нельзя использовать непосредственно, если для организации данных используются связные списки. Сами алгоритмы могут оказаться полезными, но только если они выполняют последовательную обработку данных, которую могут эффективно поддерживать связные списки.

Программа 6.15 задает интерфейс типа данных связного списка, похожий на приведенный в программе 6.7. Программа 6.15 позволяет написать драйвер, соответствующий программе 6.6, в одной строке:

main(int argc, char *argv[])
  { showlist(sortlist(scanlist(atoi(argv[1])))); }
      

Большая часть работы (включая и распределение памяти) ложится на реализации связного списка и функции sort. Как и в случае драйвера для массива, необходимо иметь возможность инициализировать этот список (из стандартного ввода либо случайными значениями), выводить его содержимое и, разумеется, сортировать его. Как обычно, в качестве типа данных сортируемых элементов используется Item — как и в разделе 6.7. Код, реализующий подпрограммы для этого интерфейса, стандартен для связных списков, которые были подробно рассмотрены в , и поэтому оставлен в качестве упражнения.

Программа 6.15. Определение интерфейса для типа связного списка

Данный интерфейс для связных списков похож на интерфейс для массивов, представленный в программе 6.7. Функция randomlist строит список случайно упорядоченных элементов (выделяя для них память). Функция showlist выводит ключи из этого списка. Программы сортировки используют перегруженную операцию < для сравнения элементов и работы с указателями при упорядочении элементов. Представление данных для узлов реализовано обычным способом (см. ) и включает конструктор узлов, который заполняет каждый новый узел заданным значением и пустой ссылкой.

struct node
  { Item item; node* next;
    node(Item x)
      { item = x; next = 0; }
  };
  typedef node *link;
  link randlist(int);
  link scanlist(int);
  void showlist(link); link sortlist(link);
      

Программа 6.15 — это низкоуровневый интерфейс, в котором нет различий между ссылкой (указателем на узел) и связным списком (указатель, который либо равен 0, либо указывает на узел, содержащий указатель на список). Конечно, для списков и реализаций можно было бы выбрать АТД первого класса, который в точности определяет все соглашения по фиктивным узлам и т.д. Однако мы выбрали низкоуровневый подход, поскольку он позволяет больше сосредоточиться на работе со ссылками, которые характеризуют сами алгоритмы и структуры данных — ведь именно они являются предметом изучения настоящей книги.

Существует фундаментальное правило, которое касается работы со связными структурами и критично для многих приложений, но не всегда четко просматривается в наших кодах. В более сложных средах указатели на узлы списка, с которыми мы работаем, могут изменяться другими частями прикладной системы (т.е., они принадлежат мультиспискам). Тот факт, что на узлы, к которым мы обращаемся через указатели, могут влиять части приложения вне программы сортировки, означает, что наши программы могут менять в узлах только ссылки и не должны изменять ключи или другую информацию. Например, если нужно выполнить обмен, то вроде бы проще обменять значения элементов (что мы и делали при сортировке массивов). Но в таком случае любое обращение к любому из этих узлов по какой-то другой ссылке обнаружит, что значение изменилось, а это недопустимо. Необходимо изменить только ссылки таким образом, чтобы при просмотре списка по доступным нам ссылкам узлы были упорядочены, но чтобы сохранился прежний порядок при обращениях по любым другим ссылкам. Реализации при этом усложняются, но обычно это необходимо.

Для работы со связными списками можно приспособить сортировку вставками, сортировку выбором и пузырьковую сортировку, хотя в каждом случае возникают интересные проблемы. Сортировка выбором реализуется достаточно просто: имеется входной список (в котором находятся исходные данные) и выходной список (в котором собирается результат сортировки), и выполняются просмотры списка, чтобы найти максимальный элемент, который затем удаляется из входного списка и помещается в начало выходного (см. рис 6.16). Реализация этой операции является несложным упражнением по обработке связных списков и представляет собой полезный метод сортировки коротких списков. Эта реализация приведена в программе 6.16. Другие методы оставлены для проработки в качестве упражнений.

На этой диаграмме показан один шаг сортировки выбором связного списка. Имеется входной список, на который указывает h->next, и выходной список, на который указывает out (вверху). Входной список просматривается так, чтобы t указывал на узел, содержащий максимальный элемент, а max указывал на предшествующий узел. Эти указатели необходимы для исключения t из входного списка (с уменьшением его длины на 1) и помещения его в начало выходного списка (с увеличением его длины на 1), сохраняя упорядоченность выходного списка (внизу). Процесс завершается, когда будет исчерпан весь входной список, а выходной список будет содержать упорядоченные элементы.

Программа 6.16. Сортировка выбором связного списка

Сортировка выбором связного списка достаточно проста, но несколько отличается от сортировки массива тем же методом, поскольку помещение элемента в начало списка выполняется проще. Используются входной список (на него указывает h->next) и выходной список (на который указывает out). Если входной список не пуст, выполняется его просмотр, чтобы найти максимальный элемент, который затем удаляется из входного и помещается в начало выходного списка. В данной реализации используется вспомогательная подпрограмма findmax, возвращающая ссылку на узел, ссылка которого указывает на максимальный элемент в списке (см. упражнение 3.34).

link listselection(link h)
  { node dummy(0); link head = dummy, out = 0;
    head->next = h;
    while (head->next != 0)
      { link max = findmax(head), t = max->next;
        max->next = t->next;
        t->next = out; out = t;
      }
    return out;
  }
      

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

Упражнения

6.64. Приведите содержимое входного и выходного списков при упорядочении программой 6.15 ключей A S O R T I N G E X A M P L E.

6.65.разрабо тайтереализациюинтерфейсадлятипасвязно го списка,приведенно го впро грамме6.15.

6.66. Напишите клиентскую программу-драйвер для вызова программ сортировки связных списков (см. упражнение 6.9).

6.67. Разработайте АТД первого класса для связных списков (см. раздел 4.8 ), который включает конструктор для инициализации случайными значениями, конструктор для инициализации с помощью перегруженной операции <<, вывод данных с помощью перегруженной операции >>, деструктор, конструктор копий и функцию-член sort. Для реализации функции sort используйте алгоритм сортировки выбором с приватной функцией-членом findmax.

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

6.69. Оформите программу сортировки вставками 3.11 таким образом, чтобы она обладала теми же возможностями, что и программа 6.16.

6.70. Для некоторых входных файлов вариант сортировки вставками, использованный в программе 3.11, выполняет сортировку связных списков значительно медленнее, чем сортировку массивов. Опишите один из таких файлов и объясните, в чем заключается проблема.

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

6.72. Реализуйте АТД для последовательностей, который позволит использовать одну и ту же клиентскую программу для отладки реализаций сортировки как связных списков, так и массивов. То есть клиентские программы должны иметь возможность генерировать последовательности из N элементов (случайно сгенерированных или из стандартного ввода), сортировать последовательности и выводить их содержимое. Например, АТД в файле SEQ.cxx должен работать со следующим программным кодом:

#include "Item.h"
#include "SEQ.cxx"
main(int argc, char *argv[])
  { int N = atoi(argv[1], sw = atoi(argv[2]);
    if (sw) SEQrand(N); else SEQscan();
    SEQsort();
    SEQshow();
  }
      

Напишите одну реализацию, в которой используется представление в виде массива, и другую, где используется представление в виде связного списка. Воспользуйтесь сортировкой выбором.

6.73. Расширьте реализацию из упражнения 6.72 так, чтобы она стала АТД первого класса. Совет: поищите решение в библиотеке стандартных шаблонов.

Метод распределяющего подсчета

Некоторые алгоритмы сортировки достигают повышения эффективности, используя особые свойства ключей. Вот, например, такая задача: требуется выполнить сортировку файла из N элементов, ключи которых принимают различные значения в диапазоне от 0 до N — 1. Эту проблему можно решить одним оператором, если воспользоваться временным массивом b:

for (i = 0; i < N; i++) b[key(a[i])] = a[i];
      

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

Если все ключи равны 0, то сортировка тривиальна. Теперь предположим, что возможны два различных значения ключа — 0 и 1. Такая задача может возникнуть, когда требуется выделить элементы файла, удовлетворяющие некоторому (возможно, сложному) критерию: допустим, ключ, равный 0, означает, что элемент следует " принять " , а равный 1 — что элемент должен быть " отвергнут " . Один из способов сортировки состоит в том, что сначала подсчитывается количество нулевых ключей, затем выполняется второй подход по исходному массиву a, распределяющий его элементы во временном массиве b. Для этого используется массив из двух счетчиков. Вначале в cnt[0] заносится 0, а в cnt[1] — количество нулевых ключей в файле. Это означает, что в исходном файле нет ключей, меньших 0, и имеется cnt[1] ключей, меньших 1. Понятно, что массив b можно заполнить следующим образом: в начало массива записываются нулевые ключи (начиная с b[[cnt[0]], т.е. с b[0]), а потом единичные, начиная с b[cnt[1]]. Таким образом, код

for (i = 0; i < N; i++) b[cnt[a[i]]++] = a[i];
      

правильно распределяет элементы из a в массиве b. Здесь опять ускорение сортировки достигается за счет использования ключей в качестве индексов (для выбора между cnt[0] и cnt[1]).

Этот подход нетрудно распространить на общий случай. Ведь чаще встречается подобная, но более реальная задача: отсортировать файл, состоящий из N элементов, ключи которого принимают целые значения в диапазоне от 0 до M — 1. Базовый метод, описанный в предыдущем параграфе, можно расширить до алгоритма, получившего название распределяющего подсчета (key-indexed counting), который эффективно решает эту задачу для не слишком больших M. Как и в случае двух ключей, идея состоит в том, чтобы подсчитать количество ключей с каждым конкретным значением, а затем использовать счетчики для перемещения в соответствующие позиции во время второго прохода по сортируемому файлу. Сначала подсчитывается число ключей для каждого значения, а затем вычисляются частичные суммы, эквивалентные количеству ключей, меньших или равных каждому такому значению. Далее, как и в случае двух значений ключа, эти числа используются как индексы при распределении ключей. Для каждого ключа величина связанного с ним счетчика рассматривается как индекс, указывающий на конец блока ключей с тем же значением. Этот индекс используется при размещении ключей в массиве b, после чего выполняется его сдвиг на одну позицию вправо. Описанный процесс изображен на рис 6.17, а реализация приведена в программе 6.17.

Сначала для каждого значения определяется количество ключей в файле, имеющих это значение. В данном примере имеется шесть значений 0, четыре значения 1, два значения 2 и три значения 3. Затем подсчитываются частичные суммы, т.е. количества ключей со значениями меньше данного значения: 0 ключей меньше 0, 6 ключей меньше 1, 10 ключей меньше 2 и 12 ключей меньше 3 (таблица в середине). Потом эти частичные суммы используются в качестве индексов для записи ключей в соответствующие позиции: 0 из начала файла помещается в позицию 0, после чего указатель для 0 увеличивается на единицу и указывает на позицию, куда будет записан следующий 0. Затем 3 из следующей позиции исходного файла помещается в позицию 12 (поскольку в файле имеются 12 ключей со значением, меньшим 3), и соответствующий счетчик увеличивается на 1, и т.д.

При сортировке очень больших файлов вспомогательный файл b может привести к проблеме нехватки памяти. Программу 6.17 можно изменить так, чтобы она выполняла сортировку на месте (т.е., без необходимости построения вспомогательного файла), используя метод, похожий на применяемый в программе 6.14. Эта операция тесно связана с базовыми методами, которые будут рассматриваться в и 10, так что мы отложим ее изучение до упражнений 12.16 и 12.17 из раздела 12.3 . Как будет показано в , эта экономия памяти достигается за счет устойчивости алгоритма, из-за чего область применения этого алгоритма существенно сужается. Ведь в приложениях, использующих большое количество повторяющихся ключей, часто используются другие ключи, относительный порядок которых должен быть сохранен. Исключительно важный пример такого приложения приведен в .

Программа 6.17. Распределяющий подсчет

Первый цикл for выполняет начальное обнуление всех счетчиков. Второй цикл for подсчитывает во втором счетчике количество 0, в третьем счетчике — количество 1 и т.д. Третий цикл for складывает все эти числа, после чего каждый счетчик содержит количество ключей, меньших или равных соответствующему ключу. Теперь эти числа представляют собой индексы концов тех частей результирующего файла, к которым эти ключи принадлежат. Четвертый цикл for перемещает ключи во вспомогательный массив b в соответствии со значениями этих индексов, а последний цикл возвращает отсортированный файл в файл a. Для работы этого кода необходимо, чтобы ключи были целыми значениями, не превышающими M, хотя его можно легко изменить так, чтобы извлекать ключи из элементов с более сложной структурой (см. упражнение 6.77).

void distcount(int a[], int l, int r)
  { int i, j, cnt[M];
    static int b[maxN];
    for (j = 0; j < M; j + +) cnt[j] = 0;
    for (i = l; i <= r; i++) cnt[a[i]+1]+ + ;
    for (j = 1; j < M; j + +) cnt[j] += cnt[j-1];
    for (i = l; i <= r; i++) b[cnt[a[i]]++] = a[i];
    for (i = l; i <= r; i++) a[i] = b[i];
  }
      

Упражнения

6.74. Напишите специализированную версию метода распределяющего подсчета для сортировки файлов, элементы которых могут принимать только одно из трех значений (a, b или c).

6.75. Предположим, что выполняется сортировка вставками случайно упорядоченного файла, элементы которого принимают одно из трех возможных значений. Каков порядок времени выполнения сортировки: линейный, квадратичный или где-то между ними?

6.76. Покажите процесс сортировки файла A B R A C A D A B R A методом распределяющего подсчета.

6.77. Реализуйте сортировку распределяющим подсчетом для элементов, которые представляют собой потенциально большие записи с целочисленными ключами из небольшого диапазона.

6.78. Реализуйте сортировку распределяющим подсчетом в виде сортировки указателей.