
Представляем вашему вниманию чрезвычайно простой алгоритм сортировки. Может показаться, что он очевидно ошибочен, но мы докажем, что на самом деле он корректен. Мы сравним его с другими простыми алгоритмами сортировки и проанализируем некоторые его любопытные свойства.
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] < A[j] на самом деле является транспозицией и требует обмена значениями. В этом алгоритме нет ничего хорошего. Он медленный — очевидно, что он выполняется за время
2. Доказательство
Несмотря на кажущуюся поначалу контринтуитивность, немного поразмыслив, мы можем понять, почему алгоритм корректен. Тем не менее, мы представим очень подробное доказательство.
Теорема 1: Алгоритм 1 сортирует массив в неубывающем порядке.
Доказательство. Докажем по индукции следующее свойство для 1 ≤ i ≤ n:
(
Корректность алгоритма будет чётко следовать из (
При i = 1 алгоритм последовательно проверяет каждый элемент в A[2..n], обменивая его на A[1], если он больше A[1]. Очевидно, что к концу этого процесса A[1] содержит наибольший элемент массива A. Следовательно, (
Допустим, что (
- Когда 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) при каждой итерации
элемент, обменянный значениями в позицию i + 1 не меньше всех элементов в A[1..j] (включая тот, с которым он только что обменялся значениями в A[j]), но не больше, чем A[j + 1].
Когда j = k (и), так как 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 (и
), 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] не приведут к обмену значениями.
Следовательно, мы установили, что (
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], и очевидно, что для алгоритма сортировки (для сортировки в возрастающем порядке) нет никаких причин делать это. Извлечение максимума даёт нам вторую часть свойства (
Следовательно, мы можем убрать ненужные итерации, получив следующий «улучшенный» алгоритм, который тоже выполняет правильную сортировку, совершая при этом меньше сравнений и обменов значениями:
Алгоритм 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(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), где
Аналогично, в фазе вставок, если A[i] и A[j] обмениваются значениями, все другие числа между A[i] и A[j] больше, чем они оба (это связано с тем, как работает алгоритм). То есть единственное изменение в количестве транспозиций возникает из самих пар, которые меняются из транспозиции в не-транспозицию.
Теорема 2: Алгоритм 1 выполняет не больше
Доказательство. Рассмотрим варианты того, где во входных данных находится максимальный элемент n.
- Если n находится в A[1], то в фазе выбора обмена значениями не происходит. В фазе вставок происходит не более
обменов значениями, так как каждый обмен устраняет одну транспозицию.
- Если n находится в A[2], то в фазе выбора происходит один обмен значениями, а в фазе вставок происходит не более
обменов значениями. Следовательно в сумме не более
+ 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, количество транспозиций уменьшается откак минимум на 1. Следовательно, на этом этапе количество транспозиций не больше
− (j − 2). В этой фазе не будет происходить новых обменов значениями, поэтому это также является количеством транспозиций на конец фазы выбора.
В противном случае, если n − 1 находится в A[j + 1..n] прямо перед шагом j, то на шаге j произойдёт перенос какого-то другого числа в позицию j, но опять же дальнейших обменов значениями не будет, поэтому n−1 будет ещё дальше от позиции 2. Следовательно, количество транспозиций может быть только меньше. В фазе выбора алгоритм выполняет не более j − 1 обменов значениями, а в фазе вставок он выполняет не более− (j − 2) обменов значениями. Следовательно, с сумме получается не более
+ 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.
Комментарии (35)
AntonioXXX
09.02.2022 13:56+42Выглядит не как ошибочный, а как пузырёк, в который забыли добавить убывание на 1 элемент на каждом следующем проходе. Скажите сразу, в чём отличие от пузырька, а то не очень пока понятно нужно ли читать целиком статью.
Bedal
09.02.2022 14:41+9ну, промолотит циклы лишние 100500 раз — банальным пузырьком от этого быть не перестанет.
xi-tauw
09.02.2022 14:46+14У пузырьковой сортировки меняются местами соседние элементы, а тут два независимых индекса.
domix32
09.02.2022 18:55+1Да мне кажется каждый изобретал что-то похожее, если его спрашивали можно ли оптимизировать пузырёк.
KingDog25
11.02.2022 18:25Точно, именно таким алгоритмом я пользовался, когда решал простые задачки в универе на с++, тогда и не знал что другие вообще существуют, кроме пузырьковой.
Всё просто , нет смысла проходить по уже отсортированным, элементам, поэтому во вложенном цикле i=j.
Да, алгоритм сравнительно не эффективен, но для малых чисел очень полезен.
anatolii_kostrygin
09.02.2022 19:18+5О, это очень прикольный алгоритм, и у меня реакция была такой же, когда я первый раз видел статью.
Он, конечно, неэффективный, никто ни спорит
Но прикольным этот алгоритм становится именно тогда, когда пытаешься доказать его корректность.
Смотрите: стандартная сортировка вставками за n^2 устроена так, что каждый раз сравниваются i-й и j-й элементы массива, где i < j. Соответственно после каждого сравнения число инверсий уменьшается.for i from 0 to n: for j from i to n: if a[i] > a[j]: swap(a[i], a[j])
А в алгоритме из статьи оба цикла от 1 до n, поэтому, иногда (если i > j) алгоритм переставляет элементы, которые уже в правильном порядке. А теперь попробуйте доказать, что после этих операций массив будет отсортирован. Вот и получаем симпатичное упражнение по комбинаторике=)
TimsTims
10.02.2022 01:45+1Я бы ещё во всех этих алгоритмах не сравнивал a[i] с a[j] , когда i==j
for i from 0 to n: for j from i+1 to n: if i != j: if a[i] > a[j]: swap(a[i], a[j])
Sulerad
10.02.2022 10:06+5Но ведь конкретно в этом случае
из цикла на второй строчке. Они не могут быть равны.
А для алгоритима из статьи лишнее условие совсем не нужно, оно лишь впустую его усложнит, как мне думается (всё равно никто же не собирается использовать его?).
Dier_Sergio_Great
10.02.2022 18:07А это на каком языке написано?
anatolii_kostrygin
10.02.2022 18:49Это псевдокод - его точно каждый может скомпилировать... в голове=)
Dier_Sergio_Great
09.02.2022 15:30?! а как этот скрипт сортировки на JS выглядит?
walkman7
09.02.2022 17:14+6function sort (arr) { for (let i = 1, l = arr.length; i < l; i++) { for (let j = 0; j <= (i - 1); j++) { if (arr[i] < arr[j]) { [arr[i], arr[j]] = [arr[j], arr[i]] } } } }
Dier_Sergio_Great
10.02.2022 17:27Спасибо огромное.
думаю можно упростить:j <= (i - 1)
кj < i
Спасибо еще раз.walkman7
10.02.2022 17:28верно, поздно увидел. а коментировать могу только раз в 24 часа :)
function sort (arr) { for (let i = 1, l = arr.length; i < l; i++) { for (let j = 0; j < i; j++) { if (arr[i] < arr[j]) { [arr[i], arr[j]] = [arr[j], arr[i]] } } } }
Vitter
09.02.2022 16:36+1Этот "простой" алоритм сортировки - сильно прожорливый О(n^2)
zuko3d
09.02.2022 16:48+3Как и пузырёк. За простоту приходится платить.
ftp27
09.02.2022 17:44+1А че за нее платить, запилил нормальный алгоритм, засунул в функцию и пользуешь. Тоже достаточно просто с учетом того, что готовых решений уже полно
zuko3d
09.02.2022 21:04+4Готовых решений... на вашем любимом языке под вашу привычную платформу?
Вообще некоторые алгоритмы имеют не столько практическую, сколько теоретическую ценность. А некоторые полезны в педагогических целях. Приведённый в статье (как и оригинальный пузырёк), имеет именно педагогическую ценность, поэтому "засунул в функцию и пользуешь" - не релевантно.
abar
09.02.2022 22:52-3Я ещё со школы запомнил и способен написать сортировку слиянием под любой язык, регулярно это делаю в качестве упражнения. Но мне интересно - что это у вас за любимые языки (и платформы) такие, что на них нет стандартных реализаций того же квиксорта?
zuko3d
09.02.2022 23:26+1Я ещё со школы запомнил и способен написать сортировку слиянием под любой язык, регулярно это делаю в качестве упражнения.
Это прекрасно, но какое это отношение имеет к моему сообщению?
Но мне интересно - что это у вас за любимые языки (и платформы) такие, что на них нет стандартных реализаций того же квиксорта?
Раз уж спросили (не знаю, зачем), мои любимые языки - С++ и Python, на них есть всё что мне нужно. Но иногда приходится работать на платформах, где нет ни плюсов, ни питона (в эмбеде такое часто). А есть только какой-то ассемблер или урезанный С. И на весь
программныймашинный код у вас 16 килобайт. И когда ты заранее знаешь, что будешь сортировать массивы на 50 элементов, то заморачиваться с квиксортом на ассемблере совсем не хочется. Да, такое редко встречается, но всё ещё не вымерло.
aamonster
10.02.2022 10:22+1Не имеет. Алгоритм работает неочевидным образом, для объяснений не особо. С этим можно было бы смириться, если бы он был эффективнн, но нет.
zuko3d
10.02.2022 15:43Согласен, что его результат неочевиден, но на мой взгляд это было бы прекрасным домашним заданием вида "а вот такая штука - сортировка или нет?" Он не слишком зубодробительный (всего 4 строки, Карл!), но при этом требуется некая аккуратность для строгого доказательства. По-моему, для студентов младших курсов - идеально, т.к. надо не только знать хорошие алгоритмы, но и научиться проверять "неизвестные" алгоритмы на предмет корректности.
aamonster
10.02.2022 17:14Заменой 1 символа алгоритм из непрозрачного превращается в абсолютно прозрачный алгоритм сортировки максимумом (ну и заодно ускоряется вдвое).
zuko3d
10.02.2022 18:26Да, всё верно. Вы много пользы видите от того, чтобы в качестве самостоятельных заданий давать что-то очевидное и прозрачное?
aamonster
10.02.2022 19:15Да, много. Программист должен видеть очевидные и прозрачные алгоритмы и стремиться к ним: его код потом кому-то читать.
Вот как задачка по математике сошло бы.
PNSpasskiy
11.02.2022 09:46Не уверен что тут может вызывать удивление? По сути имеем кривую, хоть и довольно простую, сортировку выбором. Плюс явный косяк в выборе индексов. j нет смысла пробегать всё что идёт до i включительно. А i нет смысла заходить в последний элемент.
Я честно не понимаю, что тут может хоть как-то удивлять? И уж тем более не понимаю, почему кто-то с какого-то перепугу решил, что это "потерянное" и "недостающее" звено в эволюции древних сортировок которое по какой-то "неизведанной" причине проморгали великие умы древности.
hamMElion
11.02.2022 09:50У вас все 3 вычислительные сложности обозначены как большая тета, хотя это только про среднюю сложность. Худший случай обозначается большой О, лучший - большой омегой.
da411d
11.02.2022 09:54Самый простой (и неожиданный) алгоритм сортировки?
Действительно неожиданный. Ожидал увидеть stalin-sort :D
syfim
"Сложно представить, что его не обнаружили раньше" - с "неуловимыми Джо" всегда такая истоия)
altman
Как сейчас помню, этот алгоритм принес на сдачу одноклассник в 11м классе (93 год), я тогда глядя на него так и не смог осознать, почему он работает, учитель, кажется, тоже был в задумчивости. Где он его взял, не представляю, во всех книгах по программированию, которыми мы обменивались, его не было, интернета тоже не было. Я тогда что-то не спросил, решил что придумал самостоятельно, восхитился (на бумаге выглядит красиво и абсолютно неочевидно). Поэтому как минимум один человек обнаружил его в 1993 году :)
Но сейчас все же думаю что посмотрел где-то или кто-то подсказал