- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <stdbool.h>
struct two_val
{
const int32_t a[2];
};
struct two_val_and_status
{
const bool is_swap;
const struct two_val t_v;
};
struct array
{
const int32_t a[10];
};
struct array_and_status
{
const bool is_swap;
const size_t pos;
const struct array arr;
};
// Эта суперфункцональная функция сортировки двух элементов не просто сортирует два элемента
// но и еще сообщает о том, нужно ли было для этого обменивать два значения
struct two_val_and_status sort2(const struct two_val a)
{
return (a.a[0] > a.a[1]) ? (struct two_val_and_status){true, {{a.a[1], a.a[0]}}} : (struct two_val_and_status){false, a};
}
struct two_val read_two_val(const struct array arr, const size_t pos)
{
return (struct two_val){{arr.a[pos], arr.a[pos+1]}};
}
struct array store_val(const struct array arr, const int32_t val, size_t pos)
{
return (struct array) // Царский анролл
{{
pos != 0 ? arr.a[0] : val,
pos != 1 ? arr.a[1] : val,
pos != 2 ? arr.a[2] : val,
pos != 3 ? arr.a[3] : val,
pos != 4 ? arr.a[4] : val,
pos != 5 ? arr.a[5] : val,
pos != 6 ? arr.a[6] : val,
pos != 7 ? arr.a[7] : val,
pos != 8 ? arr.a[8] : val,
pos != 9 ? arr.a[9] : val
}};
}
struct array store_two_val(const struct array arr, const struct two_val val, const size_t pos)
{
return store_val(store_val(arr,val.a[0],pos),val.a[1],pos+1);
}
// суперохуительная рекурсивная функция сортировки пузырьком
struct array_and_status bubble_sort_rec(struct array_and_status state)
{
if (state.pos == 9)
{
if (state.is_swap == false) // Ура! Сортировка пузырьком завершена!
{
return state;
}
else
{ // а иначе нам надо по-новой сортировать!
return bubble_sort_rec((struct array_and_status){.is_swap = false, .pos=0, .arr = state.arr});
}
}
else
{
const struct two_val_and_status tmp = sort2(read_two_val(state.arr, state.pos));
return bubble_sort_rec(
(struct array_and_status)
{
.is_swap = tmp.is_swap || state.is_swap,
.pos=state.pos+1,
.arr = store_two_val(state.arr, tmp.t_v, state.pos)
}
);
}
}
int main(void)
{
const struct array_and_status a = {.is_swap = false, .pos = 0, .arr = {{8,2,4,1,3,5,7,0,6,9}} };
const struct array_and_status a_sort = bubble_sort_rec(a);
for(size_t i = 0; i < 10; i++) // ох уж это убогое императивное программирование!!!
{
printf("%" PRIu32 ", ", a_sort.arr.a[i]);
}
return EXIT_SUCCESS;
}
Мне почему-то кажется, что пузырёк самый сложный в этом плане. Очень неочевидный алгоритм.
Достаточно доказать, что после одного прохода один элемент гарантированно встанет на своё место и что при применении его на массив с одним элементом он будет отсортирован.
Дальше — индукция.
хуейкер
При наивном алгоритме нужно пройти n² элементов. При подрезании границы получится треугольник, т. е. в два раза меньше элементов.
Я сэкономил не байт, а половину процессорного времени.
хуяйт
Хуил.
Фекальный.
В Осседу Ксотя перводил..
если у тебя массив из одного миллона элементов, и ты сортируешь его сто тысяч раз в секунду, но это важно
С квадратичным алгоритмом миллион так быстро не раскидать...
> или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны
>
ttps://ru.wikipedia.org/wiki/Сортировка_пузырьком
1. Отрезаем уже отсортированный хвост.
2. Если массив уже отсортирован полностью, досрочно выходим.
Удобно для частично отсортированных массивов.
Или ты про конкретное доказательство на «Coq»?
Угу. Тут ещё рекурсия неопределённой длины. Придётся пруфать,что она остановится за N проходов.
Лучше применить well-founded recursion [1]. В качестве well-founded relation взять количество неупорядоченных элементов, например.
[1] http://adam.chlipala.net/cpdt/html/Cpdt.GeneralRec.html
А то, если забыть, можно будет просто забить выходной массив нулями и сказать "я отсортироваль"
https://coq.inria.fr/library/Coq.Sorting.Sorted.html
https://coq.inria.fr/library/Coq.Sorting.Permutation.html
хуёрт
На дешманских питух-машинах возможно.
А на царской машине с оракулом сортировка Бога гарантировано отрабатывает за O(n).
Царской машине — царский алгоритм. Питухи пишут целые томы про сортировку, дрочат на O(log N *N).
А пацаны решают задачу за O(N) простым однострочником
> потому что у тебя массив уже в нужном порядке
Кстати я уже размышлял на эту тему
https://govnokod.ru/26433#comment526710
* Если компилятор смог доказать, что ранее отсортированный массив, во время исполнения не изменился до момента сортировки. Он будет отсортирован за O(0).
* Bead sort
в нем есть макросы
Избавился от вонючих императивных ифов, оставив лишь чисто функциональные тернарники
https://wandbox.org/permlink/BUon7nyVppRUvXYz
Напиши функцию реализующую ветвление.
Напиши функцию, реализующую массив.
Кстати, попадалась недавно работа, где чуваки массив (не список) на лямбда-исчислении пилили.
https://web.archive.org/web/20170705090734/http://smt2012.loria.fr/paper1.pdf
Вот тут например описывается на 98 стр. такая функциональная хуй-ня
read : array × index → element
write : array × index × element → array
Т.е. функция чтения должна принимать константный массив по значению и индекс, возвращая при этом значение по индексу:
а функция записи в массив принимает на вход массив, индекс и записываемое значение, возвращает новый массив с записанной хуйней:
Притом массивы тут бесконечные, функции никаких ошибок не возвращают и никаких побочных эффектов не имеют. И как по-вашему это реализуется в Си? Очевидно, что никак, и даже во всяких там хаскелях это на самом-то деле никак не реализуется т.к. память у ЭВМ конечна. ФП это наёбка.
Увы, «бесконечный» массив без ленивости и без генераторов не поддержать.
Но это конечно недостаточно функционально.
Можно еще сделать фукнцию, которая ищет в таком связном списке "перезаписывание" и удаляет лишнее
Вместо нула нужно сделать undefined, получится жопаскрипт
Течёт ручей, бежит ручей...
Или я какой-то из вызовов не вижу?
А это уже на следующем такте.
> стек порвётся
Ну хвостовая рекурсия же, зачем тут стек? У тебя функция или останавливается и возвращает стейт или готовит новый стейт и идёт на следующий такт.
Компилятор этого может не понять
З.Ы. Или я гоню и нельзя каждый слой сортировки параллелить внутри: 01 23 45, потом 0 12 34 5, потом 01 23 45?
Но не проебутся ли нужные пузырьку свойства от такой модификации?