- 1
https://pastebin.com/ABfdEgS5-
Pascal / Говнокод #26433
0
Выкладываю не глядя мой код примерно 12-го года.
Запостил:
vistefan,
10 Февраля 2020
Говнокод: по колено в коде.
Нашли или выдавили из себя код, который нельзя назвать нормальным, на который без улыбки не взглянешь? Не торопитесь его удалять или рефакторить, — запостите его на говнокод.ру, посмеёмся вместе!
© 2008-2024 «Говнокод.ру»
Обратная связь | Лицензионное соглашение | 
Follow us!
Follow us!
Я помню, что в школе писал его так же, ну и на будущее после школы запомню. Стабильно квадратичный питух.
А вот в Википедии в качестве питузырька указан вариант, который питуроверяет массив на питузованность, из-за чего вовремя останавливается и выдаёт линейную питушню в некоторых случаях.
Какой питузырёк правильный? На Википедии расширенный неканон, или в школе изучаем зауженный никанон?
Рекурсивный, им. Хоара.
* Может переполнить стек
* В лучшем случае логарифм, когда у википитузырька - линия
* По памяти питушня (линия же?), когда у википитузырька - константа
* Худший случай - квадрат что там, что там
Питузырёк с вики его отпитузырит за линию (теоретический пердел).
Рекококорсивный питузырёк его отпитузырит за кваквадрат!
Какой анскил )))
А вот и не очевидно:
Именно поэтому я за «Python».
Именно поэтому я за "R".
Там кстати Timsort, который ищет частично отсортированные куски.
Потому я тоже за «Python».
Потому я за while(!sorted(array)) shuffle(array);
>Bogosort
А это сортировка Бога.
Тоже кстати неочевидно.
Думаю предел O(1).
sorted([1,1,1,1,...,1]) - O(N)
sorted({data: [1,1,1,1,...,1], sorted: true}) - O(N)
То есть он отсортирован.
То есть возможен O(1).
Забавную дрянь нашёл. Многопоточную
Но в общем случае алгоритм не обладает такими знаниями, если только не использовать зожатые массивы, для которых повторяющиеся питухи будут сворачиваться.
А когда призываем sort проверить его, если asc то возвращаем исходный массив, если desc возвращаем ленивый список наоборот. Тогда best-case будет O(1).
Ещё вариант, если у нас параллельная вычислительная машина (какая-то квантовая питушня). Тогда тоже можно проверить за константое время отсортирован ли массив.
Если компилятор крайне умён он вообще выкинет sort.
Сортировка за O(0)
То он легко и непринуждённо применит алгоритм моментальной сортировки.
Временна́я сложность функции — это количество элементарных операций, которые будут выполнены этой функцией при её вызове для каких-то входных данных. То есть, если мы хотим измерить временну́ю сложность некой функции, то нам необходимо посчитать количество элементарных операций, выполняемых этой функцией.
Любые оптимизации любых компиляторов основываются на генерации эквивалентного кода. Компилятор считает две программы эквивалентными, если эквивалентно их наблюдаемое поведение (в терминах сишки и крестов — «observable behavior»).
Таким образом, для задачи измерения временно́й сложности некой функции, количество выполняемых элементарных операций становится наблюдаемым поведением. Однако ни один оптимизирующий компилятор не вносит это количество в наблюдаемое поведение. Следовательно, для задачи измерения временно́й сложности функции любой оптимизирующий компилятор генерирует неэквивалентный код, а потому любые рассуждения о сложности исходных функций на основе анализа скомпилированного кода некорректны.
Я когда-то использовал и такой алгоритм.
Установка свойства это же O(1)
Кстати, приведу реальный пример некорректности оценки сложности по скомпилированному коду. Возьмём такую питушню:
Если мы сконпелируем её с «-O0» — мы получим функцию, которая выполняется за время O(b). Если возьмём хороший конпелятор и поставим «-O3» — получим функцию со сложность O(1): https://gcc.godbolt.org/z/3zpFqD.
Но ведь это совершенно не значит, что наш питушарский алгоритм внезапно меняет сложность с линейной на константную! Он как жрал O(b), так и продолжает жрать O(b) элементарных операций языка «C».
А конпелятор — молодец, конечно.
Её в любом случае придётся делать, согласно логике программы.
Шутка про quicksort очевидно не была понята.
Но я квадрата там в упор не вижу. Будет N*logN
Он же идеально поровну разделит куски.
На [1,1,1,1,1,1,1,...,1] будет фактически best-case.
А если брать центральный элемент в качестве опорного — тогда да, будет идеальный NlogN (а квадрат образуется для очень хитро сформированных массивов — таких, что на каждой итерации будет выбираться минимальный/максимальный элемент).
Да.
>стёб над worst-case квиксорта )))
Изначально всё было правильно понятно. Ну и с практической точки зрения лучший пузырёк, это именно quicksort.
Если питушить по (<), (>=) или по (<=), (>), какую из единиц в качестве пива ни возьми, он пропитушит все единицы в один бок от неё (линия) и пойдёт питушить массив единиц без одной (линия раз по убывающей линии), в результате чего получится треугольная сложность как раз как у питузырька.
Я хотел сказать что зависит от реализации.
Кстати вот quicksort (с википедии!), который отсортирует [1,1,1,1,1,1,1,...,1] за O(N)
Так там же просто за счёт наличия этих питушень происходит эта питушня. А можно было и внутри массива всё заменить.
А оно будет их постоянно ресайзить ибо ArrayList<Integer>() по дефолту 10 элементов.
А вот насчёт автобоксинга в inta Integer, это фигня просто константа у O(N) будет больше. Это ж джава.
> пополам бьёт (start+end)/2
Питушня какая-то. Это число адекватно только когда элемент с таким номером - медианный.
Не совсем.
[1,2,3,4,5,6...]
Царский пузырёк и сортировка Бога O(N), а qsort O(N*logN).
И ещё по памяти жрёт дофига.
А если попробовать сэкономить память и применять питушню Хоара для инплейсного питушения, чтобы не плодить временные питушни для хранения подпитушень сортируемой питушни, то сложность возрастёт до квадрата!
https://govnokod.ru/26433#comment526688
Кстати это моя любимая сортировка, поскольку она одновременно и самая тормозная и самая быстрая.