[Перевод] Самый простой (и неожиданный) алгоритм сортировки?09.02.2022 14:16

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

1. Алгоритм

Большинству из нас хорошо известны такие простые алгоритмы сортировки, как сортировка пузырьком. По крайней мере, нам так кажется. Оказывались ли вы когда-нибудь в ситуации, когда вам нужно записать псевдокод сортировки пузырьком, и вы осознавали, что он не так прост, как кажется, и с первого раза правильно написать его не удаётся? Нужно внимательно следить за тем, чтобы индексы циклов начинались и заканчивались нужными значениями и не выходили за границы, а также правильно обрабатывать флаговые переменные. Разве не было бы здорово иметь простой алгоритм без всей этой возни? Ниже представлен такой алгоритм, сортирующий массив A из n элементов в неубывающем порядке. Для простоты доказательства массив начинается с 1, то есть имеет элементы A[1],…, A[n].

Алгоритм 1 ICan«tBelieveItCanSort (A[1…n]):

for i = 1 to n do
  for j = 1 to n do
    if A[i] < A[j] then
      swap A[i] and A[j]

Вот, собственно, и всё. Он просто обходит в цикле каждую пару значений (i, j) стандартным способом из двойного цикла for, выполняет сравнение и обмен значениями. Разве можно придумать что-то ещё более простое? Возможно первой реакцией увидевшего этот алгоритм будет что-то типа «это не может быть верно» или «знак неравенства направлен в другую сторону, да и индексы цикла указаны неверно». Но нет, он действительно правильно сортирует в возрастающем порядке. Алгоритм может составить впечатление, что сортирует в убывающем порядке, потому что он выполняет обмен значениями, когда A[i] меньше A[j]. Однако в отличие от других похожих алгоритмов сортировки в циклах индекс j необязательно должен быть меньше i. На самом деле, из представленного ниже доказательства видно, что большинство обменов значениями происходит когда i > j, то есть A[i] $Θ(n^2)$ в худшем, среднем и наилучшем случае. Он без необходимости сравнивает все пары позиций, да ещё и делает это дважды (но см. Раздел 3). Кажется, за ним не стоит никакого интуитивного понимания, а его правильность очевидна не сразу. Определённо не стоит использовать этот алгоритм в качестве первого примера для знакомства студентов с алгоритмами сортировки. Он неустойчив, не очень хорошо подходит для внешней сортировки, не может сортировать данные, поступающие в реальном времени, и не получает никаких преимуществ от частично отсортированных данных. Его единственной привлекательной стороной является простота с точки зрения количества строк кода и «симметрии» двух циклов. Сложно представить, что его не обнаружили раньше, однако нам не удалось найти никаких его упоминаний.

2. Доказательство

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

Теорема 1: Алгоритм 1 сортирует массив в неубывающем порядке.

Доказательство. Докажем по индукции следующее свойство для 1 ≤ i ≤ n:

( $P_i$ ): Сразу после i-той итерации внешнего цикла первые i массива A находятся в неубывающем порядке, т.е. A[1] ≤ A[2] ≤… ≤ A[i]; более того, A[i] является максимумом всего массива.

Корректность алгоритма будет чётко следовать из ( $P_n$ ).

При i = 1 алгоритм последовательно проверяет каждый элемент в A[2…n], обменивая его на A[1], если он больше A[1]. Очевидно, что к концу этого процесса A[1] содержит наибольший элемент массива A. Следовательно, ( $P_1$ ) истинно.

Допустим, что ( $P_i$ ) истинно, тогда сразу после i-той итерации внешнего цикла у нас получится A[1] ≤… ≤ A[i]. Теперь рассмотрим (i+1)-тую итерацию и докажем ( $P_{i+1}$ ). Пусть k ∈ [1, i] — наименьший индекс, при котором A[i + 1] < A[k] (и следовательно A[k − 1] ≤ A[i + 1] при $k \neq 1$ ). Если A[i + 1] ≥ A[i], то критерию не удовлетворяет никакое k и мы присваиваем k = i + 1. Рассмотрим три этапа внутреннего цикла j:

Когда 1 ≤ j ≤ k − 1, алгоритм сравнивает A[i + 1] с каждым из A[1],…, A[k − 1]. Так как A[i + 1] не меньше каждого из них, обмена значениями не происходит.
Далее рассмотрим k ≤ j ≤ i. (Если k = i + 1, этот этап не существует.) Мы утверждаем, что (1) каждое сравнение приведёт к обмену значениями (если только два элемента не равны, что в нашем случае не важно); (2) после итерации j элементы A[1…j] находятся в отсортированном порядке; и (3) при каждой итерации $j \neq 1$ элемент, обменянный значениями в позицию i + 1 не меньше всех элементов в A[1…j] (включая тот, с которым он только что обменялся значениями в A[j]), но не больше, чем A[j + 1].
Когда j = k (и $\neq 1$ ), так как A[i + 1] < A[k] по определению k, алгоритм обменивает их значениями. Для понятности мы обозначим как A[ ] и A′[ ] элементы массива до и после обмена значениями, то есть A′[i + 1] = A[k] и A′[k] = A[i + 1]. У нас есть A′[k] = A[i + 1] ≥ A[k − 1] = A′[k − 1], а поэтому A′[1..k] находится в отсортированном порядке. Также A′[i + 1] = A[k] > A[i + 1] = A′[k] и A′[i + 1] = A[k] ≤ A[k + 1] = A′[k + 1]. Следовательно, все свойства удовлетворяются. Аналогично, когда j = k+1 (и $\neq 1$ ), A′[i+1] сравнивается с A′[k+1]. Так как A′[i + 1] ≤ A′[k + 1], алгоритм обменивает их значениями (если они неравны). Используем A′′[ ] для обозначения содержимого массива после этого обмена. Вне зависимости от того, обменялись ли они значениями, у нас получается A′′[k + 1] = A′[i + 1] ≥ A′[k] = A′′[k], а поэтому A′′[1…k + 1] находится в отсортированном порядке. Также A′′[i + 1] = A′[k+ 1] ≥ A′[i+ 1] = A′′[k+ 1] и A′′[i+ 1] = A′[k+ 1] ≤ A′[k+ 2] = A′′[k + 2]. Следовательно, все три свойства снова удовлетворяются.
То же самое происходит на каждом последующем этапе. Наконец, когда j = i, то же самое происходит относительно свойства (1), (2) и первой части (3). Вторая часть (3) не требуется, поскольку она используется только для установления свойств следующей итерации на этом этапе. Обратите внимание, что по () A[i] является наибольшим элементом в A, поэтому после этого этапа A[i + 1] должен быть наибольшим элементом в A.
Когда i + 1 ≤ j ≤ n: к этому моменту A[1] ≤ A[2] ≤… ≤ A[i + 1], и A[i+ 1] является наибольшим элементом в A. Следовательно, все дальнейшие сравнения между A[i + 1] и A[j] не приведут к обмену значениями.

Следовательно, мы установили, что ( $P_{i+1}$ ) истинно.

3. Комментарии

3.1. Взаимосвязь с другими алгоритмами сортировки

Алгоритмы сортировки часто классифицируют на различные типы, например, на основе обменов, на основе выбора, на основе вставок и т.д. (см. [1]). Вот стандартная сортировка обменами для справки:

Алгоритм 2 ExchangeSort (A[1…n]):

for i = 1 to n do
  for j = i + 1 to n do
    if A[i] > A[j] then
      swap A[i] and A[j]

Алгоритм 1 был обнаружен, когда автор статьи писал ошибочные алгоритмы сортировки и заменил цикл j из Алгоритма 2 на цикл от 1 до n, и был поражён, увидев, что он выполняет сортировку в убывающем порядке.

Хотя по псевдокоду Алгоритма 1 кажется, что это сортировка на основе обменов, на самом деле первая итерация внешнего цикла (i = 1) выбирает максимум, а затем каждая из остальных итераций работает как сортировка вставками. Таким образом, это в некотором смысле сочетание алгоритмов на основе выбора и вставок.

3.2. «Улучшаем» алгоритм

Из доказательства видно, что во всех итерациях кроме i = 1 внутренний цикл j должен исполняться только от 1 до i − 1; остальная его часть не имеет никакого эффекта.

Однако единственное, что делает итерация при i = 1 — это извлечение максимума и перемещение его в A[1], и очевидно, что для алгоритма сортировки (для сортировки в возрастающем порядке) нет никаких причин делать это. Извлечение максимума даёт нам вторую часть свойства ( $P_i$ ), но эта часть никогда не требуется в доказательстве, за исключением того, чтобы продемонстрировать, что сравнения A[i] с любым элементом в A[i + 1…n] не приведёт к обмену значениями. Но если они обменяются значениями, то это только сделает A[i] больше, а A[i + 1…n] при этом не будет соответствовать ( $P_i$ ), поэтому всё, что произойдёт с этими элементами, не важно.

Следовательно, мы можем убрать ненужные итерации, получив следующий «улучшенный» алгоритм, который тоже выполняет правильную сортировку, совершая при этом меньше сравнений и обменов значениями:

Алгоритм 3 («улучшенный» Алгоритм 1):

for i = 2 to n do
  for j = 1 to i − 1 do
    if A[i] < A[j] then
      swap A[i] and A[j]

И так мы заново изобрели сортировку вставками!

Стандартная сортировка вставками находит точку вставки от конца отсортированной области, сдвигая по пути элементы, и останавливается, как только найдена правильная точка вставки. Алгоритм 3 проверяет все элементы в отсортированной области, начиная с начала, используя для перемещения многократные обмены значениями вместо сдвигов, и всегда проходит по всей длине отсортированной области. Поэтому Алгоритм 3 медленнее, чем стандартная сортировка вставками, а Алгоритм 1 — ещё медленнее. Тем не менее, мы выбираем наш исходный Алгоритм 1 за его «красоту».

3.3. Сортировка в убывающем порядке

Очевидно, что для сортировки в невозрастающем порядке можно просто перевернуть знак неравенства в Алгоритме 1. Или же благодаря симметрии i и j поменять местами два цикла for и получить такой же эффект.

4. Входные данные для наилучшего и наихудшего случаев

Какими будут входные данные для наилучшего и наихудшего случаев в Алгоритме 1? Очевидно, что он всегда выполняет ровно $n^2$ сравнений, так что будем учитывать количество обменов значениями.

Большинство алгоритмов сортировки выполняет не больше n (n−1)/2 сравнений/обменов. В конце концов, это количество пар сравниваемых разных элементов и максимальное количество транспозиций. (Здесь транспозиция — это пара (i, j), где i < j, но A[i] > A[j].) Нас не должно удивить, что этот алгоритм имеет показатели хуже. И в самом деле, мы докажем, что он может совершить больше обменов значениями, чем максимальное количество транспозиций, но всего на 1. Далее в этом разделе мы будем предполагать, что все элементы уникальны. Более того, так как это алгоритм на основании сравнений, мы без утери обобщённости можем предположить, что элементы являются 1, 2,…, n (перестановкой этих значений). Из разделов 3.1 и 3.2 вспомним, что алгоритм можно считать состоящим из двух фаз: фазы выбора максимума (i = 1) и фазы сортировки вставками (i = от 2 до n).

Лемма 1: Каждый обмен значениями в фазе выбора увеличивает количество транспозиций ровно на 1, а каждый обмен значениями в фазе вставок уменьшает количество транспозиций ровно на 1.

Доказательство. Допустим, что в фазе выбора A[1] обменивается значением с A[j]. Эта пара превращается из нетранспозиции в транспозицию. Из-за того, как работает фаза выбора, все числа от A[1] до A[j] на этом этапе меньше A[1], а следовательно, и меньше A[j]. То есть для любой пары индексов (i1, i2), где $i_1$ ∈ {1, j} и $i_2$ ∈ (1, j) её состояние транспозиции не изменится. Количество транспозиций задействованных пар, где $i_2$ > j, тоже не меняется.

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

Теорема 2: Алгоритм 1 выполняет не больше $I_{max}$ + 1 обменов значениями, где $I_{max}$ = n (n − 1)/2 — максимально возможное количество транспозиций для любых входных данных, и это жёсткая граница.

Доказательство. Рассмотрим варианты того, где во входных данных находится максимальный элемент n.

Если n находится в A[1], то в фазе выбора обмена значениями не происходит. В фазе вставок происходит не более $I_{max}$ обменов значениями, так как каждый обмен устраняет одну транспозицию.
Если n находится в A[2], то в фазе выбора происходит один обмен значениями, а в фазе вставок происходит не более $I_{max}$ обменов значениями. Следовательно в сумме не более $I_{max}$ + 1.
Допустим, n находится в A[j], j ≥ 3. На шаге j фазы выбора оно обменом значений будет перенесено в A[1]. Рассмотрим, где находится второе по величине число n − 1 непосредственно перед обменом значениями. Если оно находится в A[1…j − 1], то оно на самом деле должно находиться в A[1], потому что после шага j − 1 элемент A[1] должен содержать наибольшее число в A[1…j − 1] из-за того, как работает фаза выбора.
На шаге j это число n − 1 переносится в позицию j массива A. Но конфигурация в максимальной транспозиции имеет вид [n, n−1,…, 2, 1], что помещает n−1 в позицию 2. Для каждой позиции, такой, что n − 1 отодвигается дальше от «идеальной» позиции 2, количество транспозиций уменьшается от $I_{max}$ как минимум на 1. Следовательно, на этом этапе количество транспозиций не больше $I_{max}$ − (j − 2). В этой фазе не будет происходить новых обменов значениями, поэтому это также является количеством транспозиций на конец фазы выбора.
В противном случае, если n − 1 находится в A[j + 1…n] прямо перед шагом j, то на шаге j произойдёт перенос какого-то другого числа в позицию j, но опять же дальнейших обменов значениями не будет, поэтому n−1 будет ещё дальше от позиции 2. Следовательно, количество транспозиций может быть только меньше. В фазе выбора алгоритм выполняет не более j − 1 обменов значениями, а в фазе вставок он выполняет не более $I_{max}$ − (j − 2) обменов значениями. Следовательно, с сумме получается не более $I_{max}$ + 1.

Этой границы достигают два набора входных данных: [n − 1, n, n − 2, n − 3,…, 2, 1] или [n − 2, n − 1, n, n − 3, n − 4,…, 2, 1]. Иными словами, они помещают второе/третье по величине числа в возрастающем порядке, а остальные следуют в убывающем порядке. Это два единственных набора данных, достигающих жёсткой границы; доказать это можно чуть более жёстким анализом для j ≥ 4.

Если входные данные имеют мало транспозиций, то Алгоритм 1 как бы «адаптируется»
к ним:

Теорема 3: Алгоритм 1 выполняет не более I + 2(n − 1) обменов значениями, где I — количество транспозиций во входных данных, и это жёсткая граница.

Доказательство. В фазе выбора алгоритм может совершить не более n − 1 обменов значениями, что увеличивает количество транспозиций до не более чем I + (n − 1). Тогда в фазе вставок выполняется не более I + (n − 1) обменов значениями, так как каждый обмен устраняет одну транспозицию. Следовательно, общее количество обменов значениями не превышает I + 2(n − 1).

Граница достигается, когда входные данные уже отсортированы, т.е., когда A = [1, 2,…, n]. Количество транспозиций увеличивается от 0 до n − 1 в фазе выбора.

Теорема 4: Алгоритм 1 выполняет не менее n−1 обменов значениями, и это жёсткая граница.

Доказательство. Сразу после фазы выбора максимальный элемент находится в A[1]. Следовательно, на этом этапе есть как минимум n − 1 транспозиций. Таким образом, фаза вставок требует не менее n − 1 обменов значениями.

Единственные входные данные, достигающие этой границы — это A = [n, 1, 2,…, n − 1]. В фазе выбора обмены значениями не выполняются, а в фазе вставок выполняется n − 1 обменов значениями.

Справочные материалы

[1] Donald E. Knuth. The Art of Computer Programming, Volume 3:
Sorting and Searching, second edition. Addison-Wesley, Reading, Massachusetts, 1998.