- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
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.01.2021 05:48 # 0
Оптимизировал.
j123123 03.01.2021 06:40 # 0
gost 03.01.2021 08:06 # +2
Рассмотрим массив [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 03.01.2021 10:36 # +2
O(n^2) против O(2^n).
guest6 03.01.2021 10:49 # 0
defecate-plusplus 03.01.2021 10:54 # 0
подставь n=1000 например
bormand 03.01.2021 10:59 # 0
Я думаю ему и 48 или 64 на всю жизнь хватит.
guest6 03.01.2021 11:24 # 0
bormand 03.01.2021 11:26 # +1
З.Ы. Хотя можно взять готовый sort() и не париться.
guest6 03.01.2021 11:48 # 0
О чём и речь.
j123123 03.01.2021 16:38 # 0
gost 03.01.2021 17:02 # 0
guest3 03.01.2021 17:38 # 0
Придьош?
gost 03.01.2021 17:02 # 0
guest6 03.01.2021 17:42 # 0
defecatinho 03.01.2021 10:11 # 0
Сортировка правильная, если a[i] <= a[i + 1]
Хуле тут доказывать?
j123123 03.01.2021 15:20 # +2
guest3 03.01.2021 15:45 # 0
DypHuu_niBEHb 06.03.2021 00:55 # +2