Эшу быдлокодит

Обещанный пост о вариации быстрой сортировки, использующейся в c# в коробочном методе Array.Sort.

Суть алгоритма заключается в следующем: Берется опорный элемент, примерно по середине массива. Элементы, большие него помещаются справа от него, меньшие - слева.

Над половинками рекурсивно проводится та же операция, до тех пор, пока массив не отсортируется.

Нашел реализацию в репозитории Майкрософт с прошлой версией .Net. Ниже прикладываю вырванный оттуда рабочий кусок кода.

На первый взгляд он выглядит диковато: каскад из двух операторов do... while и двух простых while являются антитезой понятия "читаемый и понятный код".

При этом, вырванный кусок обходит все другие найденные и написанные мной реализации сортировок в несколько раз, уступая только коробочному решению (на 40%), в основе которого и лежит (видимо обвешан какими-то оптимизациями на этапе компиляции).

Программисты Microsoft таки едят хлеб недаром.

#csharp

Telegram

Эшу быдлокодит

Начал оптимизировать сортировку в своем диссертационном проекте, всплыла прекрасная иллюстрация такого понятия как вычислительная сложность алгоритма.

Тестовый массив - 4 миллиона элементов (классов, содержащих поле типа double, по которому и осуществляется…

www.tgoop.com/eshu_coding/153

209 viewsEshu Marabo, edited  Jan 6, 2021 at 19:41

Обещанный пост о вариации быстрой сортировки, использующейся в c# в коробочном методе Array.Sort.

Суть алгоритма заключается в следующем: Берется опорный элемент, примерно по середине массива. Элементы, большие него помещаются справа от него, меньшие - слева.

Над половинками рекурсивно проводится та же операция, до тех пор, пока массив не отсортируется.

Нашел реализацию в репозитории Майкрософт с прошлой версией .Net. Ниже прикладываю вырванный оттуда рабочий кусок кода.

На первый взгляд он выглядит диковато: каскад из двух операторов do... while и двух простых while являются антитезой понятия "читаемый и понятный код".

При этом, вырванный кусок обходит все другие найденные и написанные мной реализации сортировок в несколько раз, уступая только коробочному решению (на 40%), в основе которого и лежит (видимо обвешан какими-то оптимизациями на этапе компиляции).

Программисты Microsoft таки едят хлеб недаром.

#csharp

BY Эшу быдлокодит