Нашли или выдавили из себя код, который нельзя назвать нормальным,
на который без улыбки не взглянешь?
Не торопитесь его удалять или рефакторить, — запостите его на
говнокод.ру, посмеёмся вместе!
Крайне тупая по своей сути рекурсивная сортировка. Есть ли у нее название?
Вряд ли она имеет какое-то практическое применение именно как сортировка, но зато можно ее переписать на какой-нибудь Coq и об нее доказывать другие сортировки. Типа если какая-то там другая сортировка на всех возможных входных массивах выдает то же, что и выдает вот эта сортировка, то сортировка правильная.
Рассмотрим массив [3 2 1].
На первой строке (s_sort(a + 1, sz - 1)) второй элемент всплывает на место третьего: [3 1 2].
На второй строке первый элемент всплывает на место второго: [1 3 2].
Наконец, на третьей строке второй элемент всплывает на место третьего: [1 2 3].
Увеличим массив: [4 3 2 1].
Первая строка изначального вызова «запузырит» последние три элемента по своим местам: [4 1 2 3].
Вторая строка выпнет четвёрку на место второго элемента: [1 4 2 3].
Третья строка повторит базовое всплывание: [1 4 2 3] -> [1 2 4 3] -> [1 2 3 4].
Таким образом, на каждом вызове берётся один элемент (*a) и рекурсивно «всплывается» до нужного места.
Кстати, это можно было бы ещё оптимизировать, отключив выполнение третьей строки в случае, если вторая ничего не поменяла (т.е. порядок не нарушился).
Ну вот смотри, попросили тебя отсортировать табличку из 64 строк за 1 евроцент. Первым алгоритмом ты её отсортируешь за секунды. А по второму ты просто никогда не дождёшься своего евроцента.
З.Ы. Хотя можно взять готовый sort() и не париться.
Ну например если ты умеешь оценивать асимптотическую сложность всяких алгоритмов, этим знанием можно выебнуться на собеседовании, и тебя за эти знания с большей вероятностью возьмут на работу в какой-нибудь условный гугл.
А еще надо, чтоб массив до и после сортировки состоял из той же хуйни в том же количестве. Если все изменения, которые с массивом можно делать - обмен двух элементов, это должно быть тривиальным.
j123123 # 0
Оптимизировал.
j123123 # 0 ⇈
gost # 0 ⇈
Рассмотрим массив [3 2 1].
На первой строке (s_sort(a + 1, sz - 1)) второй элемент всплывает на место третьего: [3 1 2].
На второй строке первый элемент всплывает на место второго: [1 3 2].
Наконец, на третьей строке второй элемент всплывает на место третьего: [1 2 3].
Увеличим массив: [4 3 2 1].
Первая строка изначального вызова «запузырит» последние три элемента по своим местам: [4 1 2 3].
Вторая строка выпнет четвёрку на место второго элемента: [1 4 2 3].
Третья строка повторит базовое всплывание: [1 4 2 3] -> [1 2 4 3] -> [1 2 3 4].
Таким образом, на каждом вызове берётся один элемент (*a) и рекурсивно «всплывается» до нужного места.
Кстати, это можно было бы ещё оптимизировать, отключив выполнение третьей строки в случае, если вторая ничего не поменяла (т.е. порядок не нарушился).
bormand # 0 ⇈
O(n^2) против O(2^n).
guest # 0 ⇈
defecate-plusplus # 0 ⇈
подставь n=1000 например
bormand # 0 ⇈
Я думаю ему и 48 или 64 на всю жизнь хватит.
guest # 0 ⇈
bormand # 0 ⇈
З.Ы. Хотя можно взять готовый sort() и не париться.
guest # 0 ⇈
О чём и речь.
j123123 # 0 ⇈
gost # 0 ⇈
guest3 # 0 ⇈
Придьош?
gost # 0 ⇈
guest # 0 ⇈
defecatinho # 0
Сортировка правильная, если a[i] <= a[i + 1]
Хуле тут доказывать?
j123123 # 0 ⇈
guest3 # 0 ⇈
DypHuu_niBEHb # 0 ⇈