Что такое глупая сортировка?
1,00
р.
Помогите, пожалуйста, разобраться, что такое глупая сортировка. Википедия не даёт однозначного ответа на этот вопрос. Поиск по словам глупая сортировка и stupid sort дают совершенно разные результаты.
Что же такое глупая сортировка?
Можно ли привести в качестве примера реализацию глупой сортировки на C#?
Ответ
Глупая сортировка это вполне законный термин, использующийся для обозначения некоторых алгоритмов сортировки. Путаница возникает потому, что им обозначают несколько различных алгоритмов, ничего общего между собой не имеющих. Давайте разберёмся, что имеют в виду, когда используют этот термин.
Есть как минимум два алгоритма сортировки, которые обычно называются глупой сортировкой. Это gnome sort и bogosort. Рассмотрим оба из них, отсортировав их в порядке увеличения глупости.
Gnome sort
Я так полагаю, что речь в вашем вопросе идёт, вероятнее, о гномьей сортировке (gnome sort).
Описание алгоритма в двух словах (сделанное голландским учёным Диком Груном, благодаря которому алгоритм и получил своё название):
Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд если нет следующего горшка, он закончил.
То есть алгоритм очень простой: берём число, идём назад и смотрим, больше оно или меньше, и если меньше, меняем всё время пока число не станет "на своё место". Потом берём следующее число и так далее (действительно, — ну а что вы хотели от садового гнома — глупее уже сложно сортировать, но как вы увидите чуть позже, это возможно).
Визуализация работы алгоритма гномьей сортировки, Источник: Википедия
В этом случае на C# это будет выглядеть так:
public static void gnomeSort(ref int[] a) { int i = 1 int j = 2
while (i < a.Length) { if (a[i - 1] <= a[i]) { i = j j++ } else { int tmp = a[i - 1] a[i - 1] = a[i] a[i] = tmp i -= 1 if (i == 0) { i = 1 j = 2 } } } } <br>Я думаю, то как работает в данном случае сортировка, очевидно, но если нужно, я прокомментирую и объясню.
Подробности об этом методе сортировки:
http://en.wikipedia.org/wiki/Gnome_sort (англ.) https://ru.wikipedia.org/wiki/Гномья_сортировка (рус.)
Bogosort
Теперь, расскажу о втором методе сортировки, который также часто называют глупой сортировкой (хотя, как по мне, то правильнее было бы назвать эту сортировку не глупой, а сортировкой для полных дебилов). Это bogosort.
Суть метода заключается в том, что вы перемешиваете все значения в массиве случайным образом в надежде, что у вас все значения выстроятся в отсортированном порядке (как вы сами понимаете, с таким же успехом можно тасовать колоду карт, пока все карты не выстроятся по мастям и значению или читать /dev/random, пока биты не выстроятся в пиратскую копию винды).
На псевдокоде это будет выглядеть так:
while not массив_отсортирован?(массив) { перемешать(массив) }
Перемешать массив на C# можно следующим образом:
System.Random rnd = new System.Random() var numbers = Enumerable.Range(1, 4).OrderBy(r => rnd.Next()).ToArray()
(как проверить, отсортирован ли массив, то есть реализацию функции массив_отсортирован? писать не буду, оставляю вам в качестве самостоятельного задания).
Алгоритмическая сложность данного метода в среднем составляет O((n+1)!), в худшем случае, как вы понимаете, сложно не ограничена, потому что вам может просто не везти, и числа упорно не будут случайно сортироваться в правильном порядке.
Подробнее об этом чуде инженерной мысли вы можете прочитать здесь:
http://en.wikipedia.org/wiki/Bogosort (англ.) https://ru.wikipedia.org/wiki/Bogosort (рус.)
PS. Bogobogosort: Глупой, ещё глупее
Конечно, только потому что эти алгоритмы называются глупыми, не стоит думать, что в них пик глупости достигнут, и ничего более неэффективного придумать невозможно (хотя Bogosort ставит действительно высокую планку).
Как совершенно справедливо замечает VladD (спасибо за очень ценное замечение!), нет пределов человеческой глупости, а следовательно нет пределов и глупости глупых сортировок.
Примером следующего milestone на этом пути может по праву считаться Bogobogosort, по сравнению с которой Bogosort с её O((n+1)!) это просто верх алгоритмической эффективности.
У Bogobogosort получилось довести эффективность до O(n!^n!).
Подробнее:
Bogobogosort (англ.)
Что же такое глупая сортировка?
Можно ли привести в качестве примера реализацию глупой сортировки на C#?
Ответ
Глупая сортировка это вполне законный термин, использующийся для обозначения некоторых алгоритмов сортировки. Путаница возникает потому, что им обозначают несколько различных алгоритмов, ничего общего между собой не имеющих. Давайте разберёмся, что имеют в виду, когда используют этот термин.
Есть как минимум два алгоритма сортировки, которые обычно называются глупой сортировкой. Это gnome sort и bogosort. Рассмотрим оба из них, отсортировав их в порядке увеличения глупости.
Gnome sort
Я так полагаю, что речь в вашем вопросе идёт, вероятнее, о гномьей сортировке (gnome sort).
Описание алгоритма в двух словах (сделанное голландским учёным Диком Груном, благодаря которому алгоритм и получил своё название):
Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд если нет следующего горшка, он закончил.
То есть алгоритм очень простой: берём число, идём назад и смотрим, больше оно или меньше, и если меньше, меняем всё время пока число не станет "на своё место". Потом берём следующее число и так далее (действительно, — ну а что вы хотели от садового гнома — глупее уже сложно сортировать, но как вы увидите чуть позже, это возможно).
Визуализация работы алгоритма гномьей сортировки, Источник: Википедия
В этом случае на C# это будет выглядеть так:
public static void gnomeSort(ref int[] a) { int i = 1 int j = 2
while (i < a.Length) { if (a[i - 1] <= a[i]) { i = j j++ } else { int tmp = a[i - 1] a[i - 1] = a[i] a[i] = tmp i -= 1 if (i == 0) { i = 1 j = 2 } } } } <br>Я думаю, то как работает в данном случае сортировка, очевидно, но если нужно, я прокомментирую и объясню.
Подробности об этом методе сортировки:
http://en.wikipedia.org/wiki/Gnome_sort (англ.) https://ru.wikipedia.org/wiki/Гномья_сортировка (рус.)
Bogosort
Теперь, расскажу о втором методе сортировки, который также часто называют глупой сортировкой (хотя, как по мне, то правильнее было бы назвать эту сортировку не глупой, а сортировкой для полных дебилов). Это bogosort.
Суть метода заключается в том, что вы перемешиваете все значения в массиве случайным образом в надежде, что у вас все значения выстроятся в отсортированном порядке (как вы сами понимаете, с таким же успехом можно тасовать колоду карт, пока все карты не выстроятся по мастям и значению или читать /dev/random, пока биты не выстроятся в пиратскую копию винды).
На псевдокоде это будет выглядеть так:
while not массив_отсортирован?(массив) { перемешать(массив) }
Перемешать массив на C# можно следующим образом:
System.Random rnd = new System.Random() var numbers = Enumerable.Range(1, 4).OrderBy(r => rnd.Next()).ToArray()
(как проверить, отсортирован ли массив, то есть реализацию функции массив_отсортирован? писать не буду, оставляю вам в качестве самостоятельного задания).
Алгоритмическая сложность данного метода в среднем составляет O((n+1)!), в худшем случае, как вы понимаете, сложно не ограничена, потому что вам может просто не везти, и числа упорно не будут случайно сортироваться в правильном порядке.
Подробнее об этом чуде инженерной мысли вы можете прочитать здесь:
http://en.wikipedia.org/wiki/Bogosort (англ.) https://ru.wikipedia.org/wiki/Bogosort (рус.)
PS. Bogobogosort: Глупой, ещё глупее
Конечно, только потому что эти алгоритмы называются глупыми, не стоит думать, что в них пик глупости достигнут, и ничего более неэффективного придумать невозможно (хотя Bogosort ставит действительно высокую планку).
Как совершенно справедливо замечает VladD (спасибо за очень ценное замечение!), нет пределов человеческой глупости, а следовательно нет пределов и глупости глупых сортировок.
Примером следующего milestone на этом пути может по праву считаться Bogobogosort, по сравнению с которой Bogosort с её O((n+1)!) это просто верх алгоритмической эффективности.
У Bogobogosort получилось довести эффективность до O(n!^n!).
Подробнее:
Bogobogosort (англ.)
