Нашли или выдавили из себя код, который нельзя назвать нормальным, на который без улыбки не взглянешь? Не торопитесь его удалять или рефакторить, — запостите его на говнокод.ру, посмеёмся вместе!
0
void s_sort(int *a, size_t sz)
{
if ((sz == 0) || (sz == 1))
{
return;
}
if (sz == 2)
{
int a_max = a[0] > a[1] ? a[0] : a[1];
int a_min = a[0] > a[1] ? a[1] : a[0];
a[0] = a_min;
a[1] = a_max;
return;
}
s_sort(a, sz - 1);
s_sort(a + 1, sz - 1);
s_sort(a, sz - 1);
}
Крайне тупая по своей сути рекурсивная сортировка. Есть ли у нее название?
Вряд ли она имеет какое-то практическое применение именно как сортировка, но зато можно ее переписать на какой-нибудь Coq и об нее доказывать другие сортировки. Типа если какая-то там другая сортировка на всех возможных входных массивах выдает то же, что и выдает вот эта сортировка, то сортировка правильная.
Запостил: 
j123123,
03 Января 2021
Follow us!
Оптимизировал.
Рассмотрим массив [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) и рекурсивно «всплывается» до нужного места.
Кстати, это можно было бы ещё оптимизировать, отключив выполнение третьей строки в случае, если вторая ничего не поменяла (т.е. порядок не нарушился).
O(n^2) против O(2^n).
подставь n=1000 например
Я думаю ему и 48 или 64 на всю жизнь хватит.
З.Ы. Хотя можно взять готовый sort() и не париться.
О чём и речь.
Придьош?
Сортировка правильная, если a[i] <= a[i + 1]
Хуле тут доказывать?