Добрый вечер всем! Есть алгоритм сортировки, который называется «глупая сортировка»:
http://algolab.valemak.com/stupid https <https://ru.wikipedia.org/w/index.php?title=Глупая_сортировка&oldid=80928900> ://ru.wikipedia.org/w/index.php?title=Глупая_сортировка&oldid=80928900 Его сложность в типичном случае O(n³), однако в наилучшем случае (по ссылке выше написано неправильно) — O(n), для уже отсортированной последовательности. Его можно написать на Рефале-5 (предполагается, что мы упорядочиваем макроцифры по возрастанию): StupidSort { e.Begin s.X s.Y e.End , <Compare s.X s.Y> : '+' = <StupidSort e.Begin s.Y s.X e.End>; e.Sorted = e.Sorted; } Алгоритм примечателен тем, что записывается всего одной функцией на Рефале-5. Он ещё и устойчивый. Сегодня мне придумался другой алгоритм сортировки, который тоже можно записать на Рефале-5 одной функцией и который немного умнее: Sort { e.Sorted s.X e.GrEqX s.Y e.Rest , <Compare s.X s.Y> : '+' = e.Sorted <Sort s.Y e.Rest s.X e.GrEqX>; e.Sorted = e.Sorted; } Интересно проанализировать его (многабукаф, можно сразу промотать до жирной строки). Начнём с образца первого предложения. * s.X — это самый левый терм в аргументе такой, что после него есть терм, меньший его (это s.Y). Утверждение следует из порядка удлинения открытых переменных. * Следовательно, для каждого терма левее s.X верно то, что термы правее рассматриваемого больше него. Т.е. если e.Sorted непустая, то самый первый её тем будет наименьшим (все последующие больше либо равны), следующий за ним — наименьший из оставшихся и т.д. Т.е. термы из e.Sorted упорядочены по неубыванию и меньше всех остальных термов аргумента. Т.е. они уже упорядочены, как надо. Поэтому её имя — e.Sorted и она выносится за угловую скобку в правой части. * s.Y — самый левый терм справа от s.X, который меньше s.X, тоже в силу семантики удлинения открытых переменных. Стало быть, все термы между ними больше или равны s.X. Имя e.GrEqX (greater equal X) отражает этот факт. * Термы после s.Y названы e.Rest, потому что про них ничего интересного сказать не можем (ну, кроме того, что они больше, чем e.Sorted). Сложность успешного сопоставления с левой частью первого предложения — O((|e.Sorted| + 1)×n), где n — длина аргумента, |e.Sorted| — длина переменной e.Sorted. «+1» в формуле подчёркивает тот факт, что если |e.Sorted| = 0 (как дальше увидим, это нередкий случай), сложность будет O((0 + 1)×n) = O(n). Сложность неудачного сопоставления O(n²). Неудачное сопоставление означает, что нельзя в образце выбрать два терма в позициях i < j, чтобы i-й терм был больше j-го, т.е. что аргумент уже отсортирован. В этом случае выполняется второе предложение, оно тривиально. Ещё раз рассмотрим первое предложение: e.Sorted s.X e.GrEqX s.Y e.Rest , <Compare s.X s.Y> : '+' = e.Sorted <Sort s.Y e.Rest s.X e.GrEqX>; Шаги выполнения можно условно разделить на «продвигающие» и «проворачивающие». В первых |e.Sorted| > 0, они уменьшают аргумент и, соответственно, добавляют к полю зрения очередную порцию упорядоченных термов, продвигают нас к результату. Во вторых |e.Sorted| = 0, они проворачивают аргумент, рассмотрим их подробнее. Когда |e.Sorted| = 0, s.X — первый терм аргумента, s.Y — первый терм аргумента, который больше s.X. Шаг вычислений в этом случае выглядит следующим образом: <Sort s.X e.GrEqX s.Y e.Rest> → <Sort s.Y e.Rest s.X e.GrEqX> Этот шаг выполняет циклический сдвиг аргумента, в результате чего первый терм становится меньше — был s.X, стал s.Y. Кроме того, порция термов, не меньшая первого терма (это s.X e.GrEqX) помещается в самый конец аргумента и потом долго не сканируется путём удлинения переменных. Сложность одного проворачивающего шага — O(|e.GrEqX|). Проворачивающие шаги в поле зрения выполняются до тех пор, пока в образце есть термы, большие первого. Как только первым термом окажется наименьший (все последующие больше или равны), следующий шаг будет уже продвигающим. Количество проворачивающих шагов до первого продвигающего не больше n−1 (худший случай — последовательность упорядочена по убыванию). Суммарная сложность всех проворачивающих шагов между двумя продвигающими — O(n), т.к. цепочка термов, предшествующих наименьшему, бьётся на куски s.X e.GrEqX, каждый из которых отдельным шагом переносится назад. Каждый продвигающий шаг выносит как минимум один терм и имеет сложность O(|e.Sorted|×n). Очевидно, что сумма всех |e.Sorted| с каждого шага и даёт в итоге n, поэтому суммарная сложность всех продвигающих шагов O(n²). Число продвигающих шагов не более n, между двумя продвигающими шагами последовательность проворачивающих, имеющая общую сложность O(n). Так что суммарная сложность всех проворачивающих шагов тоже будет O(n²). Так что сложность алгоритма будет O(n²), причём довольно жёстко, как и у классического алгоритма прямым выбором. Кстати, если приглядеться, то это и есть в некотором смысле сортировка прямым выбором. Алгоритм неустойчивый. Интересно рассмотреть поведение алгоритма на случаях уже отсортированной последовательности и отсортированной в обратном порядке. На отсортированной последовательности алгоритм завершится за один шаг, но зато сложность шага будет O(n²). На отсортированной в обратном порядке последовательности каждый проворачивающий шаг будет выполняться за константу (т.к. |e.GrEqX| всегда будет 0), их число всегда будет n − 1. Суммарное число проворачивающих шагов будет O(n²). Каждый продвигающий шаг будет выносить ровно по одному терму и иметь сложность O(n), так что их суммарная сложность тоже будет O(n²). Разумеется, первый случай будет наилучшим, а второй наихудшим, коэффициенты перед n² в обоих случаях будут сильно разными. Можно попытаться немного улучшить алгоритм, лишив его волшебного свойства состоять из одной функции: Sort { e.Sorted s.X e.GrEqX s.Y e.Rest , <Compare s.X s.Y> : '+' = e.Sorted <Sort <RotMin s.Y e.Rest> s.X e.GrEqX>; e.Sorted = e.Sorted; } RotMin { s.X e.GrEqX s.Y e.Rest , <Compare s.X s.Y> : '+' = <RotMin s.Y e.Rest> s.X e.GrEqX; e.Rest = e.Rest; } Прежде всего, результатом RotMin будет последовательность, первый терм которой имеет наименьшее значение, а значит, следующий шаг Sort будет продвигающим (т.е. |e.Sorted| будет не меньше 1). Так что непродвигающим может быть только первый шаг Sort. Здесь мы каждый раз для улучшаем аргумент для Sort — переупорядочиваем в обратном куски s.X e.GrEqX. Соответственно, все выкинутые термы s.X образуют между собой возрастающую последовательность, а за каждым из них располагается шлейф e.GrEqX с термами, которые больше него. Так что аргумент функции Sort становится в некотором смысле лучше упорядоченным, чем раньше, а значит, шанс на то, что e.Sorted будет длиннее единицы, будет выше. В остальном, сложность RotMin та же, что и у цепочки проворачивающих шагов предыдущей версии. Можно учесть, что RotMin всегда возвращает последовательность с наименьшим термом в начале, и тогда сортировка очевидно прямым выбором с эвристикой RotMin: Sort { /* пусто */ = /* пусто */; e.Numbers = <SortLoop <RotMin e.Numbers>>; } SortLoop { s.Min e.Sorted s.X e.GrEqX s.Y e.Rest , <Compare s.X s.Y> : '+' = s.Min e.Sorted <SortLoop <RotMin s.Y e.Rest> s.X e.GrEqX>; s.Min e.Sorted = s.Min e.Sorted; } RotMin { …см. выше… } Сложность всё равно останется квадратичной, но сильно ли это улучшит коэффициент — не очевидно. Ну и напоследок напишу алгоритм сортировки вставками: InsSort { e.Numbers = <InsSortLoop e.Numbers ()> } InsSortLoop { e.Unsorted s.Last (e.Sorted-B s.Before s.Sorted-E) , <Compare s.Before s.Last> : '-' = <InsSortLoop e.Unsorted (e.Sorted-B s.Before s.Last e.Sorted-E)>; e.Unsorted s.Last (e.Sorted) = <InsSortLoop e.Unsorted (s.Last e.Sorted)>; /* пусто */ (e.Sorted) = e.Sorted; } и алгоритм сортировки пузырьком: BubbleSort { e.Numbers = <Pass () e.Numbers> } Pass { (e.Scanned) e.Begin s.X s.Y e.End , <Compare s.X s.Y> : '+' = <Pass (e.Scanned e.Begin s.Y) s.X e.End>; () e.Sorted = e.Sorted; (e.Scanned) e.Sorted = <BubbleSort e.Scanned> e.Sorted; } Они оба O(n²), в наилучшем случае O(n) (уже отсортированная последовательность), оба стабильные. Но состоят из двух функций, т.к. вынуждены иметь формат. И все сегодняшние примеры существенно используют открытые переменные с условиями. Особенно первый. Да, тестировать мне было лень, так что в алгоритмах могут быть ошибки. Тестируйте, прежде чем использовать их в своих программах. С уважением, Александр Коновалов
