Комбинаторные алгоритмы для программистов



             

Внутренняя сортировка


Существует по крайней мере пять широких классов алгоритмов внутренней сортировки.

  1. Вставка. На
    i
    -м этапе
    i
    -е имя помещается на надлежащее место между
    i - 1

    уже отсортированным именами:


  1. Обмен. Два имени, расположение которых не соответствует порядку, меняются местами (обмен). Эти процедуры повторяются до тех пор, пока остаются такие пары.


  1. Выбор. На
    i
    -м этапе из неотсортированных имен выбирается
    i
    -е наибольшее (наименьшее) имя и помещается на соответствующее место.


  1. Распределение. Имена распределяются по группам, и содержимое групп затем объединяется таким образом, чтобы частично отсортировать таблицу; процесс повторяется до тех пор, пока таблица не будет отсортирована полностью.
  2. Слияние. Таблица делится на подтаблицы, которые сортируются по отдельности и затем сливаются в одну.


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

Сосредоточим внимание на первых четырех классах алгоритмов сортировки. Алгоритмы, основанные на слиянии, приемлемы для внутренней сортировки, но более естественно рассматривать их как методы внешней сортировки.

В описываемых алгоритмах сортировки имена образуют последовательность, которую будем обозначать

x_1,x_2,\ldots,x_n
независимо от возможных пересылок данных; таким образом, значением
x_i
является любое текущее имя в
i
-й позиции последовательности. Многие алгоритмы сортировки наиболее применимы к массивам; в этом случае
x_i
обозначает
i
-й элемент массива. Другие алгоритмы более приспособлены для работы со связанными списками: здесь
x_i
обозначает
i
-й элемент списка. Следующие обозначения используются для пересылок данных:

x_i \leftrightarrow x_j
значения
x_i
и
x_j
меняются местами.

x_i \leftarrow y
значение
y
присваивается имени
x_i
.

y \leftarrow x_j
значение имени
x_j
присваивается
y
.

Таким образом, операция

x_i \leftarrow x_j
, которая встречается в различных алгоритмах сортировки, временно нарушает предположение о том, что никакие два имени не имеют одинаковых значений.


Содержание  Назад  Вперед