Сортировки. Сортировка методом прямого включения. Быстрые (улучшенные) методы сортировки. Сортировка методом Шелла

Сортировки

Общие понятия

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

Общие понятия

• Эффективность алгоритма сортировки может зависеть от ряда факторов, таких, как:
• Число сортируемых элементов
• Диапазон и распределение значений сортируемых элементов
• Степень отсортированности элементов
• Характеристики алгоритма (сложность, требования к памяти и т.д.)
• 5. Место размещения элементов (в оперативной памяти или на ВЗУ

Общие понятия

Методы сортировки разбивают на два класса: Внутренняя сортировка – сортировка массивов в ОЗУ. Внешняя сортировка – сортировка файлов или сортировка последовательностей. Метод сортировки называется устойчивым, если в процессе сортировки относительное расположение одинаковых (по ключу) элементов не изменяется.

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

• Основные требования к алгоритмам сортировки:
• По памяти – сортировка элементов массива выполняется на месте, без передачи их в результирующий массив.
• 2. По времени – мерой эффективности алгоритма по времени могут быть число необходимых сравнений ключей С и число пересылок М, которые зависят от числа элементов n.

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

• Прямые методы сортировки – требуют порядка O(n²) сравнений
• Прямые методы сортировки, не требующие дополнительной памяти, можно разбить на три категории:
  • Сортировка методом прямого включения
  • Сортировка методом прямого выбора
  • Сортировка методом прямого обмена
• Быстрые (улучшенные) методы сортировки – в самом благоприятном случае требуют O(n*log2n) сравнений

Сортировка методом прямого включения

Имеется последовательность элементов: А0, А1, А2, …, Аn-1 Эта последовательность делится на две последовательности: упорядоченную последовательность и исходную, неупорядоченную. Первоначально упорядоченная последовательность состоит из единственного элемента А0. При каждом шаге, начиная с i = 1 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент Аi и вставляется в готовую последовательность в место, при необходимости сдвигая элементы готовой последовательности на одну позицию вправо вплоть до i-й позиции.

Сортировка методом прямого включения

Для процедуры сортировки методом прямого включения число сравнений С и число пересылок М таковы: Cmin = n-1; Cсред = (n²+n-2); Cmax = (n²-n)/2-1; Mmin = 2(n-1); Mсред = (n²+9n-10)/4; Mmax = (n²+3n-4)/2. Алгоритм можно улучшить, если место включения искать методом двоичного (бинарного) поиска. Среднее число сравнений здесь С = O(n*log2n), а среднее число сдвигов М = O(n²).

Сортировка методом прямого включения

Пример 27 412 71 81 59 14 273 87 i=1 27 412 71 81 59 14 273 87 i=2 27 71 412 81 59 14 273 87 i=3 27 71 81 412 59 14 273 87 i=4 27 59 71 81 412 14 273 87 i=5 14 27 59 71 81 412 273 87 i=6 14 27 59 71 81 273 412 87 i=7 14 27 59 71 81 87 273 412

Сортировка методом прямого выбора

• Алгоритм сортировки:
• В исходной последовательности из n элементов отыскивается элемент с наименьшим ключом.
• Он меняется местами с первым элементом.
• 3. В оставшейся последовательности из n-1 элементов отыскивается минимальный элемент и меняется местами со вторым элементом и т.д., пока не останется один, самый большой элемент.

Сортировка методом прямого выбора

Для процедуры сортировки методом прямого выбора число сравнений С и число пересылок М таковы: Cсред = (n²-n); Mmin = n-1; Mсред = n(ln n+g); Mmax = n²/4+3(n-1), где g = 0.577216 – константа Эйлера Отсюда алгоритм с прямым включением несколько предпочтительнее алгоритма прямого включения. Однако, если ключи вначале упорядочены, то прямое включение будет несколько быстрее.

Сортировка методом прямого выбора

Пример 27 412 71 81 59 14 273 87 i=1 14 412 71 81 59 27 273 87 i=2 14 27 71 81 59 412 273 87 i=3 14 27 59 81 71 412 273 87 i=4 14 27 59 71 81 412 273 87 нет i=5 14 27 59 71 81 412 273 87 i=6 14 27 59 71 81 87 273 412 нет i=7 14 27 59 71 81 87 273 412

Сортировка методом прямого обмена

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

Сортировка методом прямого обмена

Для процедуры сортировки методом прямого обмена число сравнений С и число пересылок М таковы: Cmin = n, Cсред = (n²-n)/2; Mmin = 0; Mсред = 3(n²-n)/4; Mmax = 3(n²-n)/2

Сортировка методом прямого обмена

Пример. (Первый проход). 27 412 71 81 59 14 273 87 i=1 27 412 71 81 59 14 87 273 i=2 27 412 71 81 59 14 87 273 i=3 27 412 71 81 14 59 87 273 i=4 27 412 71 14 81 59 87 273 i=5 27 412 14 71 81 59 87 273 i=6 27 14 412 71 81 59 87 273 i=7 14 27 412 71 81 59 87 273

Сортировка методом прямого обмена

Пример. 27 412 71 81 59 14 273 87 j=1 14 27 412 71 81 59 87 273 j=2 14 27 59 412 71 81 87 273 j=3 14 27 59 71 412 81 87 273 j=4 14 27 59 71 81 412 87 273 j=5 14 27 59 71 81 87 412 273 j=6 14 27 59 71 81 87 273 412

Шейкерная сортировка

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