Методы сортировки с квадратичной трудоемкостью

2.1 Метод прямого выбора

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

Пример. Упорядочим слово методом прямого выбора.

Условные обозначения

сравнение элемента Х с текущим максимальным элементом

текущий максимальный элемент

Перестановка элементов

сортировка
Просмотреть
Рисунок 2. Метод прямого выбора

Алгоритм на псевдокоде

Метод прямого выбора

DO (i = 1, 2, ... n-1)
   k := <номер наименьшего элемента из ai,… an>
   ai ↔ ak
OD

Дадим оценку трудоёмкости метода прямого выбора. В данном случае можно найти точные выражения для М и С. Поскольку на каждой итерации происходит точно один обмен, то M = 3(n-1). Определим теперь количество сравнений. На первом этапе имеем (n-1) сравнений, на втором – (n-2) сравнений, на i-том этапе происходит (n- i) сравнений и т.д. Суммируя, получим C =

Отметим важные особенности метода прямого выбора. Метод не зависит от исходной отсортированности массива, т.е. значения М и С не меняются, даже если сортируется уже отсортированный массив. Сортировка методом прямого выбора неустойчива.

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

Популярный метод пузырьковой сортировки заключается в следующем. Двигаясь от конца массива к его началу, будем сравнивать между собой соседние элементы. При этом если правый элемент aj будет меньше чем левый aj-1, j=n, n-1, … ,2, то поменяем их местами. Таким образом, при первом проходе наименьший элемент переместится на первое место и можно не учитывать его при сортировке оставшейся части массива. При втором проходе наименьший элемент из оставшихся “всплывёт” на второе место. Через (n-1) итераций массив будет отсортирован.

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

сортировка
Просмотреть
Рисунок 3. Пузырьковая сортировка

Алгоритм на псевдокоде

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

Обозначим i – номер итерации, j – индекс правого элемента в текущей паре.
DO (i= 1, 2, ... n-1)
   DO (j= n, n-1, ... i+1)
      IF (aj < aj-1) aj ↔ aj-1 FI
   OD
OD

Проанализируем сложность пузырьковой сортировки. Количество сравнений в методе прямого выбора и в методе пузырьковой сортировки одинаково и не зависит от исходной отсортированности массива. Однако количество пересылок M зависит от того, как часто выполняется условие aj < aj-1. Можно определить максимальное и минимальное значения Мmin≤ Mсред≤ Mmax,. где

Мmin = 0, при сортировке упорядоченного по возрастанию массива.

Mmax = 3C = , при сортировке упорядоченного по убыванию массива.

Отсюда следует, что Mсред=О(n2), при n→∞

Таким образом, пузырьковая сортировка сильно зависит от исходной упорядоченности массива по количеству сравнений. Метод обеспечивает устойчивую сортировку.

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

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

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

сортировка
Просмотреть
Рисунок 4. Шейкерная сортировка

Алгоритм на псевдокоде

Метод шейкерной сортировки

Обозначим

L – левая граница рабочей части массива.

R – правая граница рабочей части массива.

n – количество элементов в массиве

L: = 1, R: = n, k: = n,
DO
  DO (j =R, R-1, ... L+1)
    IF (aj < aj-1) aj ↔ aj-1, k: = j FI
  OD
  L: = k
  DO (j: = L, L+1, ... R-1)
    IF (aj > aj+1) aj ↔ aj+1, k: = j, FI
  OD
  R: = k
OD (L < R)

Оценим трудоемкость метода. Количество пересылок такое же, как и в методе пузырьковой сортировки Mсред=О(n2), при n→∞ . Улучшения в методе шейкерной сортировки приводят к снижению количества сравнений. Точное выражение для величины С получить не удается, поэтому определим границы, в которых изменяется С. Если сортируется массив, в котором элементы расположены в порядке возрастания, то в методе шейкерной сортировки достаточно один раз просмотреть массив. Тогда Сmin = n-1, где n – количество элементов в массиве. Если массив отсортирован в обратном порядке, то на каждой итерации границы слева и справа сдвигаются на одну позицию и Сmax = . Следовательно, Ссред=О(n2), при n→∞ . Таким образом, как и пузырьковая сортировка, метод шейкерной сортировки сильно зависит от исходной упорядоченности массива по количеству сравнений. Метод обеспечивает устойчивую сортировку.