По тегу сортировка - много фап контента
03.09.2019, 06:27
Quick сорт один из самых эффективных, но тут еще нужно учитывать момент того, какие именно данные вы сортируете.
к примеру, QuickSort предполагает, что сортировка будет применяться к массиву, сложность будет O(nlogn). При этом нужны все данные разом. Из плюсов то, что дополнительного места не нужно, сортировка происходит за счет обмена значениями между медианой.
А вот к примеру Insertation Sort не нужен массив, сортировать можно просто поток данных, данных приходят, ты через O(logn) вычисляешь позицию и вставляешь её в LinkedList'е, к примеру. Сложность такого алгоритма будет тоже O(nlogn), так как для каждого элемент (n) надо найти позицию через log(n)
Merge сорт довольно прикольный и простой метод, основанный на том принципе, что 2 сортированных массива можно легко объединить в 1 отсортированный, если у тебя есть неупорядоченный набор данных и ты будешь разбивать его пополам рекурсивно, то в какой то момент получится, что в каждый подмассив будет размером из 1ого элемента, который априори является упорядоченным и дальше все эти массивы рекурсивно объединяются. Минус такого алгоритма в том, что нужно дополнительная память для хранения промежуточных результатов, либо кучу итераторов
Проще говоря, важна не столько сложность, сколько эффективность применения для разных типов данных, QS так же может быть не всегда эффективным, к примеру, при первом проходе если медиана будет минимальное или максимальное значение, то получится, что первый проход будет холостой.
в С# и Java применяется QS
погугли, все эти алгоритмы сортировки только на 1ый взгляд кажутся сложными, на деле все они довольны просты и гениальны :)
к примеру, QuickSort предполагает, что сортировка будет применяться к массиву, сложность будет O(nlogn). При этом нужны все данные разом. Из плюсов то, что дополнительного места не нужно, сортировка происходит за счет обмена значениями между медианой.
А вот к примеру Insertation Sort не нужен массив, сортировать можно просто поток данных, данных приходят, ты через O(logn) вычисляешь позицию и вставляешь её в LinkedList'е, к примеру. Сложность такого алгоритма будет тоже O(nlogn), так как для каждого элемент (n) надо найти позицию через log(n)
Merge сорт довольно прикольный и простой метод, основанный на том принципе, что 2 сортированных массива можно легко объединить в 1 отсортированный, если у тебя есть неупорядоченный набор данных и ты будешь разбивать его пополам рекурсивно, то в какой то момент получится, что в каждый подмассив будет размером из 1ого элемента, который априори является упорядоченным и дальше все эти массивы рекурсивно объединяются. Минус такого алгоритма в том, что нужно дополнительная память для хранения промежуточных результатов, либо кучу итераторов
Проще говоря, важна не столько сложность, сколько эффективность применения для разных типов данных, QS так же может быть не всегда эффективным, к примеру, при первом проходе если медиана будет минимальное или максимальное значение, то получится, что первый проход будет холостой.
в С# и Java применяется QS
погугли, все эти алгоритмы сортировки только на 1ый взгляд кажутся сложными, на деле все они довольны просты и гениальны :)
В c# применяется qs, insert sort и heap sort в зависимости от количества элементов массива
https://docs.microsoft.com/en-us/dotnet/api/system.array.sort?redirectedfrom=MSDN&view=netframework-4.8#System_Array_Sort__1___0___System_Comparison___0__
https://docs.microsoft.com/en-us/dotnet/api/system.array.sort?redirectedfrom=MSDN&view=netframework-4.8#System_Array_Sort__1___0___System_Comparison___0__
Все кроме хипсорта, квиксорта и мержсорта на практике не используются, а эти между собой отличаются стабильностью, худшим случаем и количеством элементов на которых лучше использовать одно и другое. Остальное - для обучения студентов-первокурсников соответствующих специальностей.
1. написано же "it's comming all together" - таков изначальный замысел
2. Так, как делаются эти гифки, можно запилить любую скорость
> я делаю монтаж сортировок
> если тупо запустить в 9 окон будет галиматья
> сохраню результаты каждой сортировки как серию изображений
> выберу одинаковое количество изображений на каждую сортировку
> объединю их в gif
> ...
> PROFIT
2. Так, как делаются эти гифки, можно запилить любую скорость
> я делаю монтаж сортировок
> если тупо запустить в 9 окон будет галиматья
> сохраню результаты каждой сортировки как серию изображений
> выберу одинаковое количество изображений на каждую сортировку
> объединю их в gif
> ...
> PROFIT
их все подогнали, чтобы одновременно закончили
так то на разных данных и на разных объемах самыми быстрыми будут разные сортировки
так то на разных данных и на разных объемах самыми быстрыми будут разные сортировки
programmista otvet.
пошел нахуй
Лол блять.
Щас в институте учусь, нам глава кафедры дискретной математики рассказывал, что у них студент на плюсах создал программу, которая решает матрицы огромных размеров невероятно быстро.
Само забавное,что код был просто огромным, зато его эффективность была просто невероятной.
Этот студент кстати занял первое место в какой-то (мировой (или не мировой блять, но помню, что там челики из европы и китая тоже были)олимпиаде,уже не помню) среди студентов первых курсов.
Так что действительно не факт, код был довольно сложным у него
Щас в институте учусь, нам глава кафедры дискретной математики рассказывал, что у них студент на плюсах создал программу, которая решает матрицы огромных размеров невероятно быстро.
Само забавное,что код был просто огромным, зато его эффективность была просто невероятной.
Этот студент кстати занял первое место в какой-то (мировой (или не мировой блять, но помню, что там челики из европы и китая тоже были)олимпиаде,уже не помню) среди студентов первых курсов.
Так что действительно не факт, код был довольно сложным у него
есть более веселая история, как то продали одному заказчику программу, один из usecase'ов была выгрузка данных в excel, базы данных для этой программы хранились на компакт дисках, но суть не в этом. суть в том, что выгрузка не работала корректно и выгружались только те строки, которые прогрузились после ленивой загрузки в области видимости списка, а остальная часть тупо выгружалась без данных, то есть пустые строки. Я это заметил и офк исправил, передали программу и мне возвращают баг о том, что выгрузка данных стала адски тормозить и вообще всё ху...во :) объяснить дебилам то, что раньше данные вообще не выгружались оказалось сложнее чем кажется.
про оптимизацию доступа к данным на CD\DVD с базой SQLite я вообще молчу, пое...ся пришлось знатно, но таковы были требования заказчика
про оптимизацию доступа к данным на CD\DVD с базой SQLite я вообще молчу, пое...ся пришлось знатно, но таковы были требования заказчика
Чтобы написать коммент, необходимо залогиниться
