О быстрой сортировке, сложности 2*N

Недавно был разработан алгоритм быстрой сортировки, сложность которого определяется как 2*N (2 умножить на N).

В данной статье не будем разбирать сам алгоритм сортировки, а, только проведя серию тестов, сравним его с сортировкой, используемой в Visual Studio (функция std::sort). Как говорится: только факты и минимум эмоций.

Сортировать будем текстовую информацию, в качестве которой будем рассматривать массив слов. Данный массив будем формировать на основе литературных произведений. Для этого все слова данных произведений по порядку заведем в данный массив. Разбиение на слова происходит без модернизации, признаком начала нового слова является пробел. Слова в массиве полностью соответствуют словам в тексте. Так как знаки препинания (точка, запятая и так далее) и управляющие символы пишутся за словами без пробелов, то, как следствие, они являются частью слов. Отдельно стоящие знаки препинания и управляющие символы рассматриваются как самостоятельные слова. В файлах присутствуют адреса сайтов, где эти файлы находятся. Данные адреса являются одним словом. Самое длинное слово состоит из 95 символов. В рассматриваемых произведениях присутствуют буквы латинского алфавита, кириллицы, знаки препинания и управляющие символы.

Сортируемая информация является произвольной, никаким образом не упорядоченной, и, как следствие, специальные сортировки не применяются.

Сравниваются два метода сортировки: вновь разработанный алгоритм сортировки со сложностью 2*N и алгоритм, используемый в Visual Studio 2017 (функция std::sort). Интересуют время сортировки и количество используемой для этого памяти каждого из методов на каждом тесте.

Программы написаны в среде — Visual Studio 2017, на платформе — Windows x64. Тестирование проводилось в 2-х конфигурациях. Результаты тестирования в конфигурации Debug и конфигурации Release представлены в таблицах 1 и 2 соответственно. В таблицах представлены результаты тестирования двух методов сортировки.

Так как результаты по времени вычисления — плавающие (значения меняются в пределах 10%), то по каждому тесту проводилась серия вычислений, из которых выбирались наименьшие значения и эти значения ставились в таблицы. Время, указанное в 4 и 6 колонках, является только временем сортировки. Дополнительные процессы (такие как считывание и запись в файл, формирование массива) в указанное время не входят.

Эффективность по времени $E_t $ и по памяти $E_m$ рассчитывается по следующим формулам соответственно:

$E_t =100\frac{T_1 - T_2}{T_1}, \qquad \qquad \qquad E_m =100\frac{M_1 - M_2}{M_1},$


где $T_1, T_2$ — количество временных тактов, за которые выполняется функция std::sort, используемой в Visual Studio, и новый алгоритм сортировки соответственно; $M_1, M_2$ — количество используемой памяти, необходимой для выполнения функции std::sort, используемой в Visual Studio, и нового алгоритма сортировки соответственно.

Таблица 1.
image

Таблица 2.
image

Насколько вновь разработанный алгоритм сортировки со сложностью 2*N является более эффективным (как по времени, так и использованию памяти) алгоритма, используемого в Visual Studio 2017 (функция std::sort) судите сами.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 154

    +17

    Что за алгоритм? Кем разработан?
    Знакома ли авторам big-O нотация? Если вы говорите об асимптотической сложности алгоритма, выражение 2*N не имеет смысла, пишут O(N). Иначе вам придется пояснять что такое N. Операции? Сравнения?

      –4
      Я специально написал, что сложность 2*N. Я нигде не понимал это как O(2*N). Прекрасно знаю, что означает O(N). Это может быть и 2*N, и 10*N, и 1000*N. Вообще запись O(N) означает k*N, где k много меньше N (k<<N). Почему я написал, что сложность 2*N. Алгоритм линейный, в нем нет сравнений элементов друг с другом. С каждым элементом выполняются определенные действия. Это одно N. Второе N – это накладные расходы. В реальности они много меньше N, но я поднял границу до N. Вот почему я написал, что сложность алгоритма 2*N. Если бы накладные расходы были сравнимы с N или кратны N, тогда я бы написал, что сложность алгоритма O(N). Но накладные расходы много меньше N.
        +4
        Я поддерживаю вашу увлечённость алгоритмами и ни в коем случае не стремлюсь охладить ваш энтузиазм. Но если вы хотите чтобы ваш анализ воспринимали серьезно, желательно придерживаться строгой общепринятой терминологии. Если вы используете big-O нотацию, читателю сразу понятно что речь идёт об асимптотической сложности, которая растёт линейно с увеличением объема входных данных. Если вы пишете «сложность алгоритма 2*N», это можно интерпретировать как угодно. Есть хорошие причины почему в научных исследованиях пользуются строгими метриками, например системой СИ. Если бы в каждой статье по астрофизике использовались произвольные аршины и попугаи, сравнивать результаты было бы чрезвычайно сложно. И ваше пояснение про накладные расходы не делает картину более понятной.

        По поводу алгоритма и сложности. Давно известно что алгоритмы основанные только на сравнениях имеют оптимальную сложность O(nlogn). Любые варианты с меньшей сложностью так или иначе используют ограниченность пространства ключей, либо другие свойства данных. Скорее всего вы изобрели radix, или counting sort, или trie, или какой-то вариант другой известной идеи. Может быть вы придумали что-то новое и полезное, в таком случае снимаю шляпу! Но из статьи этого не видно.

        Сам факт того что какой-то кастомный алгоритм сортировки для определенного типа данных может быть быстрее std::sort никого не удивит. std::sort это универсальный алгоритм основанный только на сравнениях, который не использует знания о типах данных никаким образом. Когда программист вызывает std::sort, он как бы говорит системе: интерпретируй мои данные как абстрактные ключи и используй operator< для их сравнения, я знаю что я делаю. Создатели stl не пытались предоставить наибыстрейший алгоритм сортировки для всех возможных типов данных.
          +3
          Прекрасно знаю, что означает O(N).
          С каждым элементом выполняются определенные действия. Это одно N.

          Нет, вы явно не знаете, что означает O(N).


          в нем нет сравнений элементов друг с другом

          Значит, это не универсальный алгоритм сортировки. Что и требовалось доказать.

        +14
        Четырех миллионов строк недостаточно чтобы сравнить эти алгоритмы.
        Сложность std:sort — O(N·log(N)).
        log(4 500 000) = 6,6.
        Т.е сравниваются алгоритмы сложности (как бы) «О(6N)» и «O(2N)», а это по сути одна и та же сложность. Так же при такой схожей сложности еще влияет и качество реализации алгоритма.

        Чтобы их сравнить нужно чтобы log(N) был как минимум на порядок больше двух.
        Это речь о 10^20 строк. Как часто нам приходится сортировать такое количество данных? Не думаю что в реальном использовании этих алгоритмов можно почувствовать значительную разницу.
          –5
          Четыре миллиона это только слова. Каждое слово состоит из букв. Сортировка полная, т.е. сортировка не только по первой букве, а по всем буквам. Если в среднем каждое состоит из, предположим, состоит k-букв, то нужно умножить 4 миллиона на k. Тогда будет столько сортировок. Максимальная длина слова равна 96 символам. Нет сортировка сложности не «O(2N)», а именно 2N.
            +5
            тогда что такое N?
            количество слов? букв? бит? разрядность регистра в процессоре?
              –7
              N — это количество элементов массива, которые сортируются за каждый проход.
                +4
                Тогда при чём тут буквы?
                  –5
                  В статье написано, что в сортировке были и латиница, и кириллица, и знаки препинания, и управляющие символы. Сортировать возможно все — абсолютно все. Главное, чтобы было задано правило сортировки, правило, по которому сортировать.
                    +8
                    Но всё это не имеет никакого отношения к сложности алгоритма
                      –6
                      Да, не имеет. Я упоминул, что в сортировке есть и латиница, и кириллица, и знаки препинания, и управляющие символы, чтобы показать универсальность метода.
            +2
            Справедливости ради логарифм там ближе к двоичному чем к десятичному, но учитывая смысл O-нотации разницы нет.
            +3

            Ссылку бы на алгоритм… А так какой-то конь сферический. И еще бы описание методики измерения — как мерялось время? Как память? И уж вообще шикарно бы код выложить.

              –9
              К сожалению не все от меня зависит. Разрешили выложить только сравнительные результаты, которые приведены в таблицах.
              Описание методики измерения времени — стандартное (код ниже)
              start = clock();
              программа сортировки (сначала одна, потом другая);
              finish = clock();
              duration = (double)(finish — start);
              std::cout << "\n Время сортировки — ", std::cout << duration, std::cout << "\n";
                +4

                А сколько раз проверяли? А память как считали? А что с одинаковыми значениями? А сложность у вас наихудшая, средняя, ещё какая?

                  –6
                  Очень много раз прогонял. Память показана в «сеанс диагностики — память процессора».
                  В 7-ом тесте «Война и мир» представлена 4-ре раза, а весь текст дублирован дважды.
                    +4

                    Очень много — это сколько? 100, 1000, 100000, миллион,…? Вообще такие вещи делают в цикле сотни тысяч раз.


                    А что будет на уже отсортированном массиве? На отсортированном в обратную сторону? На случайном?


                    Память — обычно делают свой heap и считают, плюс максимальный размер стека...

                      +3

                      Такие вещи сначала в псевдокоде анализируют, как мне кажется.

                  +13
                  У нас есть такие ракеты… но мы вам о них не расскажем…
                    +2
                    Не надо, а то сейчас еще автор мультфильм покажет, как его алгоритм быстро сортирует)
                    +13
                    А какой смысл от статьи если она не раскрывает тему? Какая от алгоритма польза, если его нельзя применить даже теоретически потому, что применять нечего? Почитал коменты и ни в одном ответе не видел конкретики. Если нельзя выкладывать конкретику то и не нужна такая статья. Ну или напишите статью о методиках тестирования новых методов сортировок, от нее хоть польза будет.
                  +10

                  Это какая сложность? Худшего случая? Матожидание? Что-то ещё?

                    –10
                    Это сложность каждого прогона. Что значит худшего случая? Первоначальный массив — он абсолютно произвольный, никаким образом неупорядоченный, без каких-либо закономерностей — это худший случай?
                      +14

                      Гм, дискуссия обещает быть интересной.


                      А сколько у вас этих прогонов?

                        –8
                        Не знаю, меня это не очень интересует. Просто как происходит сортировка текста: сначала сортируется массив по 1-ому символу, затем данный массив разбивается на подмассивы, у которых 1-ая буква одинакова. После этого каждый подмассив сортируете заново. И так до последней буквы. И по этой же схеме работают все алгоритмы сортировки текста.
                          +3
                          Не знаю, меня это не очень интересует.

                          Это зря.


                          А не тексты эта сортировка сортировать умеет?

                            –4
                            Умеет. Есть программа для сортировки чисел (в том числе десятичных, отрицательных). Возможна сортировка любых объектов, главное задать правило для сортировки.
                            +3

                            По Вашему описанию звучит, будто это все же O(nlog(n)) алгоритм. Такая себе вариация QuickSort, только вместо одного базисного элемента на каждом шаге выбираются 33 по количеству букв русского алфавита.


                            Но точно не 2n, так как слово длины k символов Вы считываете k раз.

                              +5
                              Это, скорее, либо поразрядная сортировка (англ. radix sort, в комментах ниже упомянутый), либо блочная сортировка (англ. bucket sort). Они бывают вполне себе линейны (O(N)), но не для произвольных данных, а только для «подходящих» (например, много-много объектов, среди которых много-много повторов, или значения ограничены узкими рамками, и т. п.) Разницы между O(2n) и O(kn) тут не будет, потому что k не зависит от объёма данных (т. е. оба варианта сводятся к O(n)). Вполне себе тема, но если автор(ы) претендуют на универсальность алгоритма, то хотя бы результаты тестов надо было привести на разных типах данных, а не только на строках. А если авторы изобрели более эффективный алгоритм именно для сортировки строк (либо какого-то класса объектов со сходными ограничениями), то и сравнивать надо не с универсальными quicksort/mergesort из std::sort(), а со специализированными функциями сортировки строк.
                                +3

                                Я в курсе и про radix, и про bucket sort. Свой комментарий я писал на основе того куска описания алгоритма, что автор поста раскрыл.


                                По поводу разницы между O(2n) и O(kn). Когда кто-то говорит, что его алгоритм имеет сложность 2n, то понимающие люди осознают, что человек подчеркивает тот факт, что его алгоритм совершает подряд именно две линейные процедуры. Не три, не пять, а именно две.


                                Безусловно, на асимптотическую сложность это не влияет, но если для какой-то задачи были известны только алгоритмы с безумной константой впереди, а кто-то нашел алгоритм с небольшой константой, то этот факт заслуживает того, чтоб на него ставить ударение. И поэтому в таких случаях вполне допустимо писать O(2n).

                            +4

                            Судя по описанию, вы изобрели Поразрядную сортировку или Radix sort. (https://ru.m.wikipedia.org/wiki/%D0%9F%D0%BE%D1%80%D0%B0%D0%B7%D1%80%D1%8F%D0%B4%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0) И да, она хорошо работает в задаче о сортировке слов.

                              –7
                              В Visual Studio используется, по моим данным, сортировка TimSort. Там та самая схема сортировки: первоначально сортируются все слова по первой букве, далее выбираются все слова с одинаковой первой буквой и начинают их сортировать по второй букве и т.д. Это стандартная схема сортировки текстовых данных на современном этапе хоть в python, хоть в java. Она никак не связана с Поразрядной сортировкой или Radix-сортировкой.
                                +3

                                Вики говорит, что TimSoft заточен под случаи, когда у нас нередки упорядоченные или частично упорядоченные подмассивы и что это сочетание сортировок слиянием и вставкой. В описании алгоритма приводится всё по шагам. Выглядит, как оптимизированный под конкретные случаи merge sort.
                                Ничего о сортировке по первой букве, затем по второй не увидел https://ru.m.wikipedia.org/wiki/Timsort
                                Да и доступная визуализация алгоритма это показывает.


                                Признаться, я не понимаю, что вы говорите.

                                  –5
                                  У нас массив, например, 50 слов, который необходимо отсортировать. Сортируем данный массив, в результате получаем: первые 10 слов начинаются, пускай, на букву «в», далее 14 слов — на букву «к», далее 8 слов на букву «c», и т.д. Отсортировав данный массив, переходим к следующему этапу: берем первые 10 слов и начинаем сортировать их по 2-ой букве, которые в свою очередь разбиваются на подмассивы, которые в свою очередь будут упорядочены. Получим, например, 4-ре слова вторая буква — «а», 4-ре слова вторая буква «е» и оставшиеся 2 слова — вторая буква «с». Далее берем 4-ре слова, начинающиеся на «ва» и сортируем их. И так далее, до последней буквы. Далее сортируем слова, начинающиеся на «ве», и также до последней буквы. Далее сортируем слова, начинающиеся на «вс», и также до последней буквы. После этого возвращаемся к 14 словам начинающимся на букву «к». И также по описанной выше схеме. Эта схема не привязана к какому-либо методу сортировки, она общая для текстовой сортировки. По данной схеме сортируются все тексты, независимо от того как сортировать, хоть TimSort, хоть пузырком или как там еще.
                                    +2

                                    TimSort описан иначе. По вашей схеме у вас будет M подмассивов, где M зависит от N, и каждый подмассивов будет сортироваться столько раз, сколько букв в самом длинном слове. Если сложность одной сортировки по одной букве N, длина наибольшего слова K, то мы получим, O(N^2*K).
                                    Товарищи по цеху, если я ошибаюсь, то поправите мою оценку описанного алгоритма.

                                      –3
                                      Данная схема — это не сортировка TimSort. TimSort можно применять, когда сортируете 50 слов, или 10 слов, или 14 слов и на каждом этапе в отдельности. По данной схеме просто происходит сортировка текстовой информации. Вместо TimSort-а можно использовать любой другой метод на каждом этапе. По поводу сложности O(N^2*K). Данная сложность справедлива, если мы используем метод сложности O(N^2) и все слова выравниваем по длине максимального слова. Реально, если мы используем метод сложности O(N^2), то, для нашего примера, — O(50^2) + O(10^2) + O(14^2) +…. Но O(50^2) больше всего остального, поэтому сложность считается, как O(50^2).
                                        +3

                                        Можно не писать штуки вроде O от конкретного числа?

                                          –2
                                          Это не я написал, как Вы выразились шутку, O(2N). Я говорю, именно, об 2*N.
                                            +2

                                            То есть у вас время всегда с одним и тем же коэффициентом, вы это имеете в виду? Ну ок, тогда O(N)

                                          +2

                                          Я вам написал, что такая оценка получается при использовании алгоритма сортировки O(N).
                                          Если взять O(nlog(n)), то в итоге получится O(N^2log(N)*K)

                                    +2
                                    Это стандартная схема сортировки текстовых данных на современном этапе хоть в python, хоть в java.

                                    Какой конкретно способ сортировки вы называете "стандартной схемой сортировки текстовых данных в python"? Приведите конкретную функцию.

                              +4

                              У "прогонов" сложности не бывает. У них только время выполнения бывает. Сложность бывает у алгоритмов. И у алгоритмов она бывает разной (амортизированная, средняя, для худшего случая и т.п.)

                                +5

                                Сейчас как раз готовлюсь к собесу. Повторяю оценку сложности алгоритмов. Про худший случай слышал, про прогон впервые. Вы не иначе как на изменение основ Computer Science замахнулись:)

                                  +7
                                  Уважаемый, ну вам же уже ответили. Я попытаюсь вас просветить. Математически доказано, что невозможно построить алгоритм, который бы мог отсортировать ЛЮБЫЕ данные быстрее, чем O(N log N).
                                  Т.е. ваше утверждение, что ваш алгоритм бытрее std:sort на ЛЮБЫХ данных — некорректен. СУЩЕСТВУЕТ контрпример, на которм стандартный алгоритм будет быстрее.
                                  Увы, без деталей реализации невозможно такой контрпример найти.
                                  Существует МАССА алгоритмов, которые быстрее стандратного на определенном типе данных. Ваш — один из них.
                                  Поймите, интерес к деталям обусловлен не желанием украсть вашу коммерческую тайну, а просто мы пытаемся подтолкнуть вас к осознанию положения вещей.
                                    +3
                                    Строго говоря — невозможно при наличии определённых ограничений («in-place» и всё такое). Так-то всякие зануды и буквоеды легко могут предъявить counting sort, который работает за O(N) в лучшем и худшем случаях.
                                      +3
                                      Там только одно ограничение: при сортировке используется сравнение объектов между собой. Counting sort, radix sort и прочие объекты между собой не сравнивают, потому и линеарифмическая нижняя граница на них не распространяется.
                                        +2
                                        Но чуда все равно не будет. Даже если не называть эти опреации сравнением, всё равно в реальной релизации БУДУТ примеры, когда специализированные алгоритмы будут медленнее универсального.
                                          +1
                                          нет — берем массив и раскладываем элементы из него в другой массив по индексу равному элементу — получаем упорядоченный массив за линейное время (может быть еще раз пройтись чтобы убрать неиспользуемые места)
                                          — ни одного сравнения, но нужно очень много памяти.
                                            +2
                                            — ни одного сравнения, но нужно очень много памяти.
                                            А ещё, сортировать так можно только чисел, диапазон значений которых не превышает размер доступного адресного пространства. И с количеством повторов, не превышающим диапазон значений адресуемой ячейки. И только если это прямо всамделишные массивы, во всякие списки, хэшы и прочие высоко-уровневые структуры скорость вставки и удаления тоже зависит от количества элементов.
                                              +4
                                              Нет, не получится. Контрпример:
                                              Берем массив [0, MAXINT_64], и сортируем вашим алгоритмом.
                                              Вам понадобится MAXINT_64 сравнений, чтобы пройти по «отсортированной» памяти и найти все (2) вставленных значения, а классическому алгоритму будет достаточно 1-го сравнения.
                                          +3
                                          А вы слышали про SleepSort? Она вообще за один проход сортирует.
                                        +2
                                        Что значит худшего случая?

                                        Без деталей алгоритма не скажешь. Где-то — полностью отсортированный массив. Где-то — отсортированный задом наперед. Где-то — полностью случайные данные. Где-то — массив, состоящий из одного значения элементов…
                                          –4
                                          Я же указал, что было первоначальными массивами. Какая закономерность есть в «Войне и мире», в «Тихом Доме» и в остальных произведениях. Это абсолютно случайные данные, без каких-либо закономерностей. Разве, что в 3-ем и 7-ом тестах: вторая часть полностью повторяет первую. Но поверьте: данная закономерность нигде не используется. В остальных тестах даже такой закономерности нет.
                                            +4
                                            Вот видите, вы уже сузили рамки своего алгоритма до «сортировка слов, слов много разных, они распеределены по определённому закону».
                                            На таких данных ваш алгоритм вполне может показывать линейную зависимость.
                                            Только именно это и надо указывать в заголовке.
                                              –5
                                              Ну по какому закону они распределены, где я об этом говорил или как-то там еще упоминал.
                                                +2
                                                По равномерному? Опровергайте.
                                                  –3
                                                  По равномерному, согласен. Но равномерное распределение не дает какой-то закономерности, которую можно использовать и применить какие-то специальные методы.
                                                    +3
                                                    А доказать сможете, что оно равномерное, распределение?
                                          +3

                                          Вы, случайно, с любителем анимированных флагов и определителем случайностей не знакомы?

                                            +2
                                            Сначала подумала, что это просто весна, но открыла профиль, и, вот это да, очередной повелитель brand new сортировок, приглашенный valemak'ом.
                                            Хмммммм… *подозрительно щурится*
                                              +2
                                              Я даже в профиль не смотрел, а оказалось, что товарищ valemak очередного гения призвал.
                                              Интересно услышать мотивацию, т.к. один раз ещё можно поверить в случайность, но второй подряд срыватель покровов.
                                              Подозрительно, очень подозрительно.
                                                +2
                                                Да вон парой веток ниже Валерий объяснил, что ему иногда пишут срыватели. Инвайтов ему не жалко, а дальнейшая их судьба — исключительно их же забота. И г-н Рыбинкин — его рук дело.
                                                  +3
                                                  Ясно.
                                                  Интересно, что товарищам кто-то довольно кучно ставит плюсики, что уже ставит под сомнение игнорирование их судеб «полноправными» пользователями.
                                            +9
                                            • Я построил самый быстрый самолёт!
                                            • А какую скорость замеряли: взлета, посадки, загрузки, максимальную полетную, воздушную (калиброванную, истинную, эквивалентную), путевую, сваливания, крейсерскую или другую какую может?
                                            • А что такое скорость?
                                              +2
                                              Хм…
                                              Допустим у нас есть некий алгоритм, реализован в виде функции, на вход которой приходит массив. Внутри этой функции есть 3 невложенных foreach:
                                              someFunction(someArray) {
                                              foreach(someArray){
                                              }
                                              foreach(someArray){
                                              }
                                              foreach(someArray){
                                              }
                                              return someResult
                                              }

                                              Какова сложность данного алгоритма в big-O нотации?
                                              Внутри циклов нет других циклов.
                                              А у такого варианта какова сложность:
                                              someFunction(someArray) {
                                              foreach(someArray){
                                              foreach(someArray){
                                              foreach(someArray){
                                              }
                                              }
                                              }
                                              return someResult
                                              }
                                            +9
                                            Очередной вечный двигатель? Алгоритмы сортировки, основанные на сравнении, в принципе не могут быть лучше O(N log N), это достаточно легко доказывается математически.
                                              +5

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

                                                –13
                                                К сожалению, я не могу раскрывать все нюансы алгоритма. Могу только сказать следующее. На двигателе внутреннего сгорания невозможно улететь в космос, для этого нужны реактивные двигатели. В новой сортировке используется другой подход, поэтому и получились такие результаты.
                                                  +10

                                                  У нас есть эликсир жизни, но мы вам его не покажем. Просто поверьте на слово.

                                                    +4
                                                    Если изобрели что-то вроде radix-сортировки для строк, сравнивать «другой подход» с сортировкой сравнениями (будь то std::sort или что-то ещё) некорректно и неинтересно.
                                                  +2

                                                  А если не сложно, объясните пожалуйста кто-нибудь, почему из серии тестов выбирается наименьшее значение? Почему не среднее?

                                                    –9
                                                    Если выбирать среднее или максимальное, тогда в 8 столбце значения получаются не 15%, а значительно больше
                                                    +4
                                                    Сортировать будем текстовую информацию, в качестве которой будем рассматривать массив слов. Данный массив будем формировать на основе литературных произведений.

                                                    Нет, не надо фокусничать, давайте сортировать одномерный массив целых чисел.
                                                      +1

                                                      А какая разница? В компьютерном представлении, что числа, что слова — суть одно и то же.

                                                        +6
                                                        Вот только распределение будет разным. Слова, если брать русский — очень много слов, начинающихся менее чем с 30 строчных букв (за минусом йыьъ), это уже 5 бит сравнения в самом частом случае, плюс довольно мало слов с заглавных. В случае с числами — много чисел, у которых первый байт в диапазоне от 0 до 255, что как бы уже вынуждает сравнивать 8 бит для каждого байта. В некоторых реализациях это способно хорошо ускорить процесс.
                                                          0

                                                          Надеюсь, Вы в курсе, что процессоры (во всяком случае Intel и AMD) не сравнивают числа побитово, всегда как минимум побайтово.


                                                          Да и по поводу распределения чисел. Есть какой-то эмпирический закон, который утверждает, что наиболее вероятны числа, у которых первая цифра — это единица. То есть числа, которые приходят из реального мира тоже как-бы не совсем равномерно распределены.


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

                                                            +1
                                                            Да даже недавние бенчмарки реализации wc на хаскелле —
                                                            habr.com/ru/post/489958
                                                            на «хороших» данных работает лучше всех, на случайных данных — уже не так уж и экстремально быстро.

                                                            На данный момент как раз почему-то в качестве набора данных для сортировки использован естественный текст. Причина?
                                                      +2
                                                      Смотрел выступление одного интересного профессора, он занимался вопросом максимального повышения точности подсчета производительности. Потому что на скорость влияет состояние операционной системы, многозадачность, текущие операции, особенности работы хранилища данных.

                                                      В итоге он реализовал немного допиленный arm qemu, который логирует в файл выполняемые инструкции в процессе работы программы. Почему ARM? бОльшая линейность и зависимость только от оптимизации компилятора, а не особенности предсказания ветвлений.

                                                      Подход позволяет посчитать с точностью до процессорной инструкции время вычисления, плюс заодно напрямую получить точное количество обработанных байт оперативной памяти.
                                                        +4

                                                        Для профессоров заниматься таким абсолютно нормально, чистая наука, все дела. Но на практике нам всем гораздо интереснее скорость работы с учётом всего того, что он хочет не учитывать.

                                                          +1
                                                          Отполированная в таких не-всё-учитывающих-условиях реализация алгоритма вполне возможно в естественных условиях будет себя тоже хорошо показывать.

                                                          Зато подсчет инструкций позволяет в один проход получить повторяемый результат, а не гонять набор тестов, прогревая процессорный кэш, дисковый кэш и потом занимаясь статистикой — минимальное время взять? среднее? медиану?

                                                          Здесь бенчмарк достаточно запустить один раз и все случайные факторы просто не оказывают влияние. Да, не нравится ограниченность именно RISC архитектурой, но…
                                                          +6
                                                          А вот на x86 нет смысла считать процессорные инструкции. Предсказание ветвлений и кэш дают огромный прирост в скорости, игнорировать его нельзя. Александреску рассказывал об этом, с примерами, когда «теоретически» более быстрый код с меньшим числом сравнений и инструкций выполняется медленнее, чем код с большим числом.
                                                          +3

                                                          "сравним его с сортировкой, используемой в Visual Studio (функция std::sort)."
                                                          Насколько я знаю VS закрытая IDE, и IDE не равно язык программирования!

                                                            +2
                                                            Ну, условия достаточные для повторения результатов — конкретная версия поставляется с конкретным компилятором и в комплекте идут вполне себе конкретные библиотеки.
                                                              +5

                                                              Вы видимо не поняли сарказм, я C# разработчик, о том что есть std::sort я лишь знаю опосредованно. А ещё есть F#, JavaScript и все это не поверите внутри VS и да, там нет std::sort

                                                              +8
                                                              Предлагаю автору сравнить свой алгоритм сортировки ещё с Intellij Idea, Eclipse, Vim, Emacs (функция M-x::sort-lines) и обязательно с «Microsoft Notepad».
                                                              +7
                                                              Судя по всему, мы наблюдаем результат лабораторной работы по алгоритмам и структурам данных. Был изобретен my_radix_sort.
                                                                +6

                                                                Уважаемый автор, вы предлагаете читателям судить ниочём. Нет ни алгориитма, ни описания его работы, ни упоминания на каком оборудовании проводились ваши опыты. Также видно, что для оценки сложности вы не использовали стандартных инструментов оценки сложности (нотация О большое для классов функций). Ознакомьте нас хотя бы с оценкой сложности алгоритма std:sort в вашей системе.

                                                                  +2
                                                                  Недавно был разработан алгоритм быстрой сортировки, сложность которого определяется как 2*N (2 умножить на N).

                                                                  Простой вопрос: это алгоритм общего назначения или специализированный?

                                                                    +7
                                                                    Я так понял, это новый уровень троллинга? Ну, что сортировка, которая умеет только сравнивать элементы, не может иметь сложность лучше O(N*log(N)) — это бог с ним, не будем догматиками. Но мы всерьез должны обсуждать тезис «у меня есть мифический алгоритм, существование которого не доказано, но вы должны в него верить, а, чтоб вам лучше верилость, я покажу вам табличку, красиво оформленную в Excel»? Как давно Хабр стал религиозным сайтом?
                                                                      +6
                                                                      А внутре у него, сталбыть, неонка?
                                                                      +2
                                                                      А все-таки, почему сведения о таком фундаментальном прорыве в теории алгоритмов сортировки вдруг публикуются не в каком-то уважаемом научном издании, а на Хабре, который вполне себе приличный сайт, но явно не то место, куда изначально отправляют такие разработки?)
                                                                        +3
                                                                        А где здесь прорыв? Алгоритмы сортировки с O(N) известны и используются.
                                                                        То, что radix sort лучше подходит для сортировки строк, чем сортировки сравнениями — тоже не новость. В особо секретных документах даже можно найти, почему так происходит ;)
                                                                        +3
                                                                        Напомнило)

                                                                        image
                                                                          +2
                                                                          Спасибо Бабушкину, что он подмышки бреет :-)
                                                                          +9

                                                                          Если я правильно предполагаю, то автор пишет про "Сортировку Таноса" (автор называл её "Русской сортировку половинками", но я категорически против использования такого названия), которая является велосипедом вариантом QuickSort. Видимо по некомпетентности valemak не распознал велосипед и написал вышеупомянутую статью (ничего страшного, бывает).


                                                                          Однако, дальше хуже:


                                                                          • valemak пригласил на Хабр пользователя Danilin78 (автор упомянутой сортировки), который умудрился отличится двумя вариантами своей статьи (1, 2) получившими недвусмысленную оценку "бред" и т.п.
                                                                          • Теперь valemak пригласил пользователя HabrArkady, который написал обсуждаемую статью о "вновь разработанном алгоритме сортировки", демонстрируя элементарное незнание темы, без описания алгоритма и/или демонстрации исходного кода, неся откровенную пургу в комментариях и т.д и т.п.

                                                                          Поэтому у меня вопрос к valemak: кто все эти люди и что вы там все употребляете?

                                                                            +2
                                                                            Прошу не забывать, что Владимир Рыбинкин (автор «сортировки воронкой») также был дважды приглашён по моим инвайтам.
                                                                              +4
                                                                              У вас там какая-то секта?
                                                                                +3
                                                                                Всё объясняется достаточно просто.

                                                                                Я люблю изучать сортировки (считайте, что это моё хобби) и время от времени публикую статьи об этих алгоритмах. Свои методы я не изобретаю, рассказываю о классических.

                                                                                Мне иногда пишут авторы собственных наработок, просят дать инвайт. Как правило, даю :-) За саморегулирующийся Хабр не переживаю. Также осмелюсь заметить, что в комментариях обсуждения статей моих «крестников» всегда получаются бурными и доставляющими :-)
                                                                                +2

                                                                                Ну так и что в итоге с "сортировкой воронкой"?


                                                                                Если дадите ссылку на исходный код референстной или оптимизированной реализации, то обещаю выложить результаты тестов с исходниками.

                                                                                  +1
                                                                                  Не в курсе, это к Рыбинкину (попробуйте ему написать на емайл). У меня так и не дошли руки как следует вникнуть в его алгоритм и сделать анимацию — но когда-нибудь реализация и этой сортировки пополнит мою коллекцию :-)
                                                                                    +5

                                                                                    Это модифицированная сортировка слиянием. Используется linked list.
                                                                                    Есть текущий подмассив, изначально пустой. Идем по исходному массиву, который сортируем.
                                                                                    Первый элемент просто добавляем в подмассив, следующие сравниваем с головой и хвостом подмассива, если меньше головы добавляем в голову, если больше хвоста добавляем в хвост. Для добавления в голову и нужен linked list, иначе придется сдвигать все элементы. Хотя наверно можно заменить его на массив в 2 раза больше исходного.
                                                                                    Если элемент находится между головой и хвостом, откладываем подмассив в буфер подмассивов, создаем новый пустой подмассив, добавляем туда.
                                                                                    После прохода по исходному массиву есть некоторое количество отсортированных подмассивов. Мержим их попарно, всегда берем самые минимальные по длине. Можно либо отсортировать по длине другим алгоритмом (автор предлагал пузырек), либо поддерживать отсортированность при добавлении. Но после каждого слияния длина результирующего массива меняется, надо это учитывать.
                                                                                    Изначально у автора было несколько рабочих подмассивов, они получаются каждый следующий короче предыдущего, поэтому он назвал алгоритм "сортировка воронкой". Для произвольных данных число сравнений в этом случае увеличивается, поэтому он сделал один подмассив, а название оставил.


                                                                                    В TimSort тоже есть определение отсортированных подмассивов (run), там они определяются в самом массиве, сравнение происходит с предыдущим элементом. В реализации MergeSort это тоже иногда добавляют, сам алгоритм от этого не меняется. Соответственно, от такого модифицированного MergeSort сортировка воронкой отличается только дополнительным сравнением с головой текущего run. Она значительно лучше работает на данных, специально для нее подходящих (2, 8, 2, 8, 1, 9, ...), на всех остальных работает чуть хуже, так как часто происходят 2 сравнения и потом все равно создание нового подмассива из одного элемента вместо одного сравнения на элемент для первоначального разбиения в модифицированном MergeSort. Может быть некоторый выигрыш от того, что мержатся минимальные подмассивы, а не соседние, но в TimSort это обрабатывается лучше.


                                                                                    В обычном MergeSort для первоначального разбиения будет ноль сравнений, так как просто всегда берется подмассив из 1 элемента, но в большинстве случаев это увеличивает число сравнений при слиянии. Для полностью случайных данных обычный MergeSort будет чуть лучше модифицированного (на N/2 сравнений), что заметно на небольших массивах. Для всех остальных случаев будет лучше модифицированный MergeSort или TimSort. Сортировка воронкой подходит для очень узкого круга вариантов.

                                                                                      +2

                                                                                      Спасибо.

                                                                                  –14
                                                                                  Нет, я не пишу про сортировку Таноса, с ней ничего общего нет и в помине. Это сначала. Во-вторых, не трогайте Valemak. В-третьих, для того, чтобы о чем-то рассуждать, надо знать, о чем рассуждаешь. В статье, самое главное, это результаты тестирования, приведенные в таблицах. Все остальное — это общие рассуждения, помогающие что-то понять, чтобы меньше задавать вопросов. Самый главный результат — это то, что по новому алгоритму, выигрыш по быстродействию более 15%, а по затратам на память — практически двукратный. И чем больше объем сортируемой информации, тем более стремительный выигрыш мы будем иметь.
                                                                                  И, наконец, если очень хочется ругаться, то пришли e-mail. Поругаемся. А хамить здесь, не надо!!!
                                                                                    +3
                                                                                    Самый главный результат — это то, что по новому алгоритму, выигрыш по быстродействию более 15%, а по затратам на память — практически двукратный.

                                                                                    … по сравнению с чем?


                                                                                    (это просто к разговору "надо знать, о чем рассуждаешь")

                                                                                      –8
                                                                                      По сравнению с функцией std::sort, используемой в Visual Studio 2017. По-моему, как в таблицах, так и в текстах об этом не единожды об этом упоминается.
                                                                                        +3

                                                                                        std::sort — функция сортировки общего назначения (она работает для любых элементов, для которых определено отношение "элемент a идет раньше элемента b"). Ваша сортировка является сортировкой общего назначения?

                                                                                          –8
                                                                                          Да, этой сортировкой можно, сортировать все. Там нет привязки, к чему-либо. Я об этом уже писал не единожды.
                                                                                            +5
                                                                                            Да, этой сортировкой можно, сортировать все.

                                                                                            Покажите результаты сравнения (и код бенчмарка) для сравнения объектов с интерфейсом a.GoesBefore(b). Или опишите, каким образом ваш алгоритм работает для таких объектов.

                                                                                              +3
                                                                                              Не верим! Это примерно то же самое, что сказать что Вы придумали вечный двигатель. Если Вы несогласны, то продемонстрируйте пожалуйста результаты релевантных тестов, а не что-то левое, что вы показали в статье.
                                                                                                –4
                                                                                                Что значит _релевантных_ тестов, и почему Вы решили, что данные тесты — это что-то левое.
                                                                                                  +4

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

                                                                                                    +4

                                                                                                    Если ваш алгоритм требует определения для элементов больше отношения "a < b", то мерятся скоростью следует не c std::sort (универсальной сортировкой), а чем-то менее универсальным. В этом случае рекомендую этот пост — там Travis Downs ничего нового не придумал, но итеративно с танцами и песнями пояснениями и иллюстрациями дошел до хороших показателей для radixsort. Соответственно, хотелось-бы увидеть сопоставление результатов с вашим алгоритмом.


                                                                                                    Кроме этого, при сравнении с std::sort следует измерять результаты для разных случаев (с разным распределением и упорядочиванием) исходных данных. В качестве заготовки могу предложить более-менее приемлемый тест и показать результаты (на всякий — сам тест критиковать не стоит, а просто сделать лучше/правильно и опубликовать).

                                                                                                      +2

                                                                                                      На всякий дополню — добавлять оцениваемые сортировки лучше в stresstest и запускать его-же.

                                                                                                        +3

                                                                                                        HabrArkady, вы покажите результаты stresstest с вашим алгоритмом или не намерены этого делать?

                                                                                                          –3
                                                                                                          Разъясните, пожалуйста, что Вы хотите, чтобы я сделал более подробно. Какие тесты я должен сделать.
                                                                                                            +5

                                                                                                            Вы ничего не должны, но я предлагаю проверить вашу сортировку простейшим набором тестов. Вам нужно:


                                                                                                            1. Клонировать git-репозиторий https://github.com/erthink/sort;
                                                                                                            2. Для проверки собрать проект посредством CMake и запустить runme;
                                                                                                            3. Добавить вашу реализацию сортировки по аналогии добавления radixsort;
                                                                                                            4. Запустить runme и показать результаты.

                                                                                                            Для информации:


                                                                                                            • это простейший бенчмарк сортировок сделанный сотрудником google ~10 лет назад.
                                                                                                            • я добавил несколько сценариев распределения данных (для оценки скорости yysort-сортировки сделанной для libmdbx.
                                                                                                            • только-что добавил сборку посредством CMake и упомянутую ранее реализацию radixsort.



                                                                                                            Пример результатов
                                                                                                            Running tests with random:
                                                                                                            extra.h yysort1_int64         - ok,   822818.0 usec
                                                                                                            extra.h yysort2_int64         - ok,   854933.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok,  1576849.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   185674.0 usec
                                                                                                            sort.h tim_sort               - ok,  1402058.0 usec
                                                                                                            sort.h quick_sort             - ok,  1077905.0 usec
                                                                                                            extra.h std_sort_int64        - ok,  1009962.0 usec
                                                                                                            extra.h std_stable_int64      - ok,  1059595.0 usec
                                                                                                            sort.h heap_sort              - ok,  1102937.0 usec
                                                                                                            sort.h merge_sort             - ok,  1421193.0 usec
                                                                                                            sort.h shell_sort             - ok,  1862364.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,  1246581.0 usec
                                                                                                            sort.h grail_sort             - ok,  1699774.0 usec
                                                                                                            sort.h sqrt_sort              - ok,  1455058.0 usec
                                                                                                            stdlib qsort                  - ok,  1927199.0 usec
                                                                                                            -------
                                                                                                            Running tests with random 50% duplicates:
                                                                                                            extra.h yysort1_int64         - ok,   810166.0 usec
                                                                                                            extra.h yysort2_int64         - ok,   849615.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok,  1572379.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   212029.0 usec
                                                                                                            sort.h tim_sort               - ok,  1398433.0 usec
                                                                                                            sort.h quick_sort             - ok,  1088323.0 usec
                                                                                                            extra.h std_sort_int64        - ok,  1065503.0 usec
                                                                                                            extra.h std_stable_int64      - ok,  1071353.0 usec
                                                                                                            sort.h heap_sort              - ok,  1093484.0 usec
                                                                                                            sort.h merge_sort             - ok,  1415888.0 usec
                                                                                                            sort.h shell_sort             - ok,  1838834.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,  1253441.0 usec
                                                                                                            sort.h grail_sort             - ok,  1693643.0 usec
                                                                                                            sort.h sqrt_sort              - ok,  1453816.0 usec
                                                                                                            stdlib qsort                  - ok,  1949698.0 usec
                                                                                                            -------
                                                                                                            Running tests with random two values:
                                                                                                            extra.h yysort1_int64         - ok,   248878.0 usec
                                                                                                            extra.h yysort2_int64         - ok,   122961.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok, 89906420.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   145132.0 usec
                                                                                                            sort.h tim_sort               - ok,   436794.0 usec
                                                                                                            sort.h quick_sort             - ok,   112741.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   272012.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   309151.0 usec
                                                                                                            sort.h heap_sort              - ok,   558226.0 usec
                                                                                                            sort.h merge_sort             - ok,   492002.0 usec
                                                                                                            sort.h shell_sort             - ok,   350249.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,   364930.0 usec
                                                                                                            sort.h grail_sort             - ok,   586547.0 usec
                                                                                                            sort.h sqrt_sort              - ok,   552624.0 usec
                                                                                                            stdlib qsort                  - ok,   772211.0 usec
                                                                                                            -------
                                                                                                            Running tests with random of 0..9:
                                                                                                            extra.h yysort1_int64         - ok,   391730.0 usec
                                                                                                            extra.h yysort2_int64         - ok,   301675.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok,  7404398.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   133223.0 usec
                                                                                                            sort.h tim_sort               - ok,   835698.0 usec
                                                                                                            sort.h quick_sort             - ok,   272618.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   417282.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   547843.0 usec
                                                                                                            sort.h heap_sort              - ok,   944833.0 usec
                                                                                                            sort.h merge_sort             - ok,   796068.0 usec
                                                                                                            sort.h shell_sort             - ok,   674562.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,   678547.0 usec
                                                                                                            sort.h grail_sort             - ok,  1639136.0 usec
                                                                                                            sort.h sqrt_sort              - ok,   868220.0 usec
                                                                                                            stdlib qsort                  - ok,  1242882.0 usec
                                                                                                            -------
                                                                                                            Running tests with mixed-pattern (1/2 sorted, 1/6 reverse, 1/3 random):
                                                                                                            extra.h yysort1_int64         - ok,   613579.0 usec
                                                                                                            extra.h yysort2_int64         - ok,   663289.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok,   657258.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   183325.0 usec
                                                                                                            sort.h tim_sort               - ok,   552537.0 usec
                                                                                                            sort.h quick_sort             - ok,   838606.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   792180.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   525126.0 usec
                                                                                                            sort.h heap_sort              - ok,  1032734.0 usec
                                                                                                            sort.h merge_sort             - ok,   748048.0 usec
                                                                                                            sort.h shell_sort             - ok,  1676758.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,   586180.0 usec
                                                                                                            sort.h grail_sort             - ok,   953395.0 usec
                                                                                                            sort.h sqrt_sort              - ok,   772525.0 usec
                                                                                                            stdlib qsort                  - ok,  1062228.0 usec
                                                                                                            -------
                                                                                                            Running tests with mixed-pattern 50% duplicates:
                                                                                                            extra.h yysort1_int64         - ok,   609025.0 usec
                                                                                                            extra.h yysort2_int64         - ok,   660484.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok,   659025.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   225606.0 usec
                                                                                                            sort.h tim_sort               - ok,   622718.0 usec
                                                                                                            sort.h quick_sort             - ok,   824485.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   788281.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   522923.0 usec
                                                                                                            sort.h heap_sort              - ok,  1031538.0 usec
                                                                                                            sort.h merge_sort             - ok,   754849.0 usec
                                                                                                            sort.h shell_sort             - ok,  1642628.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,   590366.0 usec
                                                                                                            sort.h grail_sort             - ok,   990525.0 usec
                                                                                                            sort.h sqrt_sort              - ok,   774448.0 usec
                                                                                                            stdlib qsort                  - ok,  1124386.0 usec
                                                                                                            -------
                                                                                                            Running tests with mixed-pattern two values:
                                                                                                            extra.h yysort1_int64         - ok,   200132.0 usec
                                                                                                            extra.h yysort2_int64         - ok,    83036.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok, 67483405.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   140106.0 usec
                                                                                                            sort.h tim_sort               - ok,   160123.0 usec
                                                                                                            sort.h quick_sort             - ok,    97190.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   225158.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   205413.0 usec
                                                                                                            sort.h heap_sort              - ok,   511215.0 usec
                                                                                                            sort.h merge_sort             - ok,   356849.0 usec
                                                                                                            sort.h shell_sort             - ok,   297061.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,   162143.0 usec
                                                                                                            sort.h grail_sort             - ok,   374851.0 usec
                                                                                                            sort.h sqrt_sort              - ok,   409156.0 usec
                                                                                                            stdlib qsort                  - ok,   566768.0 usec
                                                                                                            -------
                                                                                                            Running tests with mixed-pattern of 0..9:
                                                                                                            extra.h yysort1_int64         - ok,   285522.0 usec
                                                                                                            extra.h yysort2_int64         - ok,   203379.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok,  3868783.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   134041.0 usec
                                                                                                            sort.h tim_sort               - ok,   306421.0 usec
                                                                                                            sort.h quick_sort             - ok,   184143.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   312547.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   295135.0 usec
                                                                                                            sort.h heap_sort              - ok,   887521.0 usec
                                                                                                            sort.h merge_sort             - ok,   465153.0 usec
                                                                                                            sort.h shell_sort             - ok,   500991.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,   304824.0 usec
                                                                                                            sort.h grail_sort             - ok,   873295.0 usec
                                                                                                            sort.h sqrt_sort              - ok,   540994.0 usec
                                                                                                            stdlib qsort                  - ok,   746061.0 usec
                                                                                                            -------
                                                                                                            Running tests with sorted:
                                                                                                            extra.h yysort1_int64         - ok,   106663.0 usec
                                                                                                            extra.h yysort2_int64         - ok,    16666.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok,    69891.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   251164.0 usec
                                                                                                            sort.h tim_sort               - ok,    11735.0 usec
                                                                                                            sort.h quick_sort             - ok,   251402.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   173910.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   143127.0 usec
                                                                                                            sort.h heap_sort              - ok,   964730.0 usec
                                                                                                            sort.h merge_sort             - ok,   282217.0 usec
                                                                                                            sort.h shell_sort             - ok,   224989.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,    24654.0 usec
                                                                                                            sort.h grail_sort             - ok,   436444.0 usec
                                                                                                            sort.h sqrt_sort              - ok,   283779.0 usec
                                                                                                            stdlib qsort                  - ok,   456411.0 usec
                                                                                                            -------
                                                                                                            Running tests with sorted 93.75%:
                                                                                                            extra.h yysort1_int64         - ok,   278289.0 usec
                                                                                                            extra.h yysort2_int64         - ok,   289340.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok,   655408.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   260584.0 usec
                                                                                                            sort.h tim_sort               - ok,   468728.0 usec
                                                                                                            sort.h quick_sort             - ok,   637118.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   329171.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   336014.0 usec
                                                                                                            sort.h heap_sort              - ok,   984870.0 usec
                                                                                                            sort.h merge_sort             - ok,   519161.0 usec
                                                                                                            sort.h shell_sort             - ok,  1534410.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,   518192.0 usec
                                                                                                            sort.h grail_sort             - ok,   800571.0 usec
                                                                                                            sort.h sqrt_sort              - ok,   661784.0 usec
                                                                                                            stdlib qsort                  - ok,   888571.0 usec
                                                                                                            -------
                                                                                                            Running tests with reverse:
                                                                                                            extra.h yysort1_int64         - ok,   181535.0 usec
                                                                                                            extra.h yysort2_int64         - ok,   194451.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok,    84785.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   256737.0 usec
                                                                                                            sort.h tim_sort               - ok,    31284.0 usec
                                                                                                            sort.h quick_sort             - ok,   301640.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   177571.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   197487.0 usec
                                                                                                            sort.h heap_sort              - ok,   909687.0 usec
                                                                                                            sort.h merge_sort             - ok,   382207.0 usec
                                                                                                            sort.h shell_sort             - ok,   344173.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,   281081.0 usec
                                                                                                            sort.h grail_sort             - ok,   491918.0 usec
                                                                                                            sort.h sqrt_sort              - ok,   333204.0 usec
                                                                                                            stdlib qsort                  - ok,   511167.0 usec
                                                                                                            -------
                                                                                                            Running tests with 111......000:
                                                                                                            extra.h yysort1_int64         - ok,   157486.0 usec
                                                                                                            extra.h yysort2_int64         - ok,    20157.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok, 89831003.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   138863.0 usec
                                                                                                            sort.h tim_sort               - ok,    16507.0 usec
                                                                                                            sort.h quick_sort             - ok,    43632.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   183356.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   151969.0 usec
                                                                                                            sort.h heap_sort              - ok,   476663.0 usec
                                                                                                            sort.h merge_sort             - ok,   288034.0 usec
                                                                                                            sort.h shell_sort             - ok,   236196.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,    58724.0 usec
                                                                                                            sort.h grail_sort             - ok,   248106.0 usec
                                                                                                            sort.h sqrt_sort              - ok,   353212.0 usec
                                                                                                            stdlib qsort                  - ok,   458765.0 usec
                                                                                                            -------
                                                                                                            Running tests with 999..., 888..., ..., ...000:
                                                                                                            extra.h yysort1_int64         - ok,   149749.0 usec
                                                                                                            extra.h yysort2_int64         - ok,    19980.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok, 32356259.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   135767.0 usec
                                                                                                            sort.h tim_sort               - ok,    32825.0 usec
                                                                                                            sort.h quick_sort             - ok,    99056.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   175027.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   155548.0 usec
                                                                                                            sort.h heap_sort              - ok,   820527.0 usec
                                                                                                            sort.h merge_sort             - ok,   298793.0 usec
                                                                                                            sort.h shell_sort             - ok,   254553.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,   107271.0 usec
                                                                                                            sort.h grail_sort             - ok,   429893.0 usec
                                                                                                            sort.h sqrt_sort              - ok,   414603.0 usec
                                                                                                            stdlib qsort                  - ok,   493637.0 usec
                                                                                                            -------
                                                                                                            Running tests with all same:
                                                                                                            extra.h yysort1_int64         - ok,   166858.0 usec
                                                                                                            extra.h yysort2_int64         - ok,    21707.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok,    69098.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   113107.0 usec
                                                                                                            sort.h tim_sort               - ok,    12040.0 usec
                                                                                                            sort.h quick_sort             - ok,    18011.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   186969.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   141784.0 usec
                                                                                                            sort.h heap_sort              - ok,    66827.0 usec
                                                                                                            sort.h merge_sort             - ok,   287558.0 usec
                                                                                                            sort.h shell_sort             - ok,   225105.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,    24957.0 usec
                                                                                                            sort.h grail_sort             - ok,   199244.0 usec
                                                                                                            sort.h sqrt_sort              - ok,   295538.0 usec
                                                                                                            stdlib qsort                  - ok,   437948.0 usec
                                                                                                            -------
                                                                                                            Running tests with sorted blocks of length 10:
                                                                                                            extra.h yysort1_int64         - ok,   780905.0 usec
                                                                                                            extra.h yysort2_int64         - ok,   817650.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok,  1581537.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   182992.0 usec
                                                                                                            sort.h tim_sort               - ok,  1293210.0 usec
                                                                                                            sort.h quick_sort             - ok,  1029897.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   973319.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   924195.0 usec
                                                                                                            sort.h heap_sort              - ok,  1078477.0 usec
                                                                                                            sort.h merge_sort             - ok,  1267130.0 usec
                                                                                                            sort.h shell_sort             - ok,  1723112.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,  1112339.0 usec
                                                                                                            sort.h grail_sort             - ok,  1576277.0 usec
                                                                                                            sort.h sqrt_sort              - ok,  1324452.0 usec
                                                                                                            stdlib qsort                  - ok,  1722064.0 usec
                                                                                                            -------
                                                                                                            Running tests with sorted blocks of length 100:
                                                                                                            extra.h yysort1_int64         - ok,   653574.0 usec
                                                                                                            extra.h yysort2_int64         - ok,   689053.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok,  1564217.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   182998.0 usec
                                                                                                            sort.h tim_sort               - ok,   675106.0 usec
                                                                                                            sort.h quick_sort             - ok,   906428.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   832817.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   682833.0 usec
                                                                                                            sort.h heap_sort              - ok,  1047375.0 usec
                                                                                                            sort.h merge_sort             - ok,   933192.0 usec
                                                                                                            sort.h shell_sort             - ok,  1457265.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,   889346.0 usec
                                                                                                            sort.h grail_sort             - ok,  1296572.0 usec
                                                                                                            sort.h sqrt_sort              - ok,  1058781.0 usec
                                                                                                            stdlib qsort                  - ok,  1352663.0 usec
                                                                                                            -------
                                                                                                            Running tests with sorted blocks of length 10000:
                                                                                                            extra.h yysort1_int64         - ok,   324255.0 usec
                                                                                                            extra.h yysort2_int64         - ok,   376492.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok,   284086.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   184740.0 usec
                                                                                                            sort.h tim_sort               - ok,   124746.0 usec
                                                                                                            sort.h quick_sort             - ok,   625609.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   491734.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   250881.0 usec
                                                                                                            sort.h heap_sort              - ok,   986073.0 usec
                                                                                                            sort.h merge_sort             - ok,   393951.0 usec
                                                                                                            sort.h shell_sort             - ok,   551140.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,   322268.0 usec
                                                                                                            sort.h grail_sort             - ok,   652629.0 usec
                                                                                                            sort.h sqrt_sort              - ok,   465226.0 usec
                                                                                                            stdlib qsort                  - ok,   638257.0 usec
                                                                                                            -------
                                                                                                            Running tests with swapped size/2 pairs:
                                                                                                            extra.h yysort1_int64         - ok,   713246.0 usec
                                                                                                            extra.h yysort2_int64         - ok,   747018.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok,  1508257.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   265747.0 usec
                                                                                                            sort.h tim_sort               - ok,  1176319.0 usec
                                                                                                            sort.h quick_sort             - ok,   993433.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   852194.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   865713.0 usec
                                                                                                            sort.h heap_sort              - ok,  1074433.0 usec
                                                                                                            sort.h merge_sort             - ok,  1163080.0 usec
                                                                                                            sort.h shell_sort             - ok,  1831217.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,  1072136.0 usec
                                                                                                            sort.h grail_sort             - ok,  1438544.0 usec
                                                                                                            sort.h sqrt_sort              - ok,  1222052.0 usec
                                                                                                            stdlib qsort                  - ok,  1635037.0 usec
                                                                                                            -------
                                                                                                            Running tests with swapped size/8 pairs:
                                                                                                            extra.h yysort1_int64         - ok,   388071.0 usec
                                                                                                            extra.h yysort2_int64         - ok,   415601.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok,   920980.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   257616.0 usec
                                                                                                            sort.h tim_sort               - ok,   657143.0 usec
                                                                                                            sort.h quick_sort             - ok,   713389.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   451258.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   455000.0 usec
                                                                                                            sort.h heap_sort              - ok,  1009091.0 usec
                                                                                                            sort.h merge_sort             - ok,   667092.0 usec
                                                                                                            sort.h shell_sort             - ok,  1659759.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,   675202.0 usec
                                                                                                            sort.h grail_sort             - ok,   947886.0 usec
                                                                                                            sort.h sqrt_sort              - ok,   798388.0 usec
                                                                                                            stdlib qsort                  - ok,  1060413.0 usec
                                                                                                            -------
                                                                                                            Running tests with known evil data (odd/even swap):
                                                                                                            extra.h yysort1_int64         - ok,   106596.0 usec
                                                                                                            extra.h yysort2_int64         - ok,   119683.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok,    72005.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   247649.0 usec
                                                                                                            sort.h tim_sort               - ok,    93710.0 usec
                                                                                                            sort.h quick_sort             - ok,   280980.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   167934.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   163389.0 usec
                                                                                                            sort.h heap_sort              - ok,   954945.0 usec
                                                                                                            sort.h merge_sort             - ok,   312337.0 usec
                                                                                                            sort.h shell_sort             - ok,   232719.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,    21145.0 usec
                                                                                                            sort.h grail_sort             - ok,   438797.0 usec
                                                                                                            sort.h sqrt_sort              - ok,   285045.0 usec
                                                                                                            stdlib qsort                  - ok,   507681.0 usec
                                                                                                            -------
                                                                                                            Running tests with known evil data (odd/even hi/low swap):
                                                                                                            extra.h yysort1_int64         - ok,   113151.0 usec
                                                                                                            extra.h yysort2_int64         - ok,    71402.0 usec
                                                                                                            extra.h sort_rela589n_int64   - ok,   140752.0 usec
                                                                                                            extra.h radix_sort7_int64     - ok,   244312.0 usec
                                                                                                            sort.h tim_sort               - ok,   292957.0 usec
                                                                                                            sort.h quick_sort             - ok,   494097.0 usec
                                                                                                            extra.h std_sort_int64        - ok,   162164.0 usec
                                                                                                            extra.h std_stable_int64      - ok,   196847.0 usec
                                                                                                            sort.h heap_sort              - ok,   943394.0 usec
                                                                                                            sort.h merge_sort             - ok,   387820.0 usec
                                                                                                            sort.h shell_sort             - ok,   439202.0 usec
                                                                                                            sort.h merge_sort_in_place    - ok,   365635.0 usec
                                                                                                            sort.h grail_sort             - ok,   655214.0 usec
                                                                                                            sort.h sqrt_sort              - ok,   426086.0 usec
                                                                                                            stdlib qsort                  - ok,   669278.0 usec

                                                                                                            В том числе, видно как ведет себя "новый метод сортировки массива" от rela589n.

                                                                                                              +2
                                                                                                              Мне кажется, Вы сейчас просто подложили свинью хабру: теперь новые мастера сортировочных работ будут хакать конкретно этот бенчмарк для доказательства крутости своих алгоритмов.
                                                                                                              Но за репу спасибо: звездочку поставил.
                                                                                                                +3

                                                                                                                Уж лучше так, чем "хакать" мозг окружающих ;)

                                                                                                    +3
                                                                                                    Если этой сортировкой можно сортировать все, то откуда 2*N и как это стыкуется с теоремой о нижней оценке для сортировки сравнениями?
                                                                                                      +4

                                                                                                      Никаким.

                                                                                                        –3
                                                                                                        Данная сортировка не относится к классу сортировок посредством сравнений.
                                                                                                          +4

                                                                                                          Тогда каким образом вы с ее помощью сортируете объекты для которых определена только операция сравнения?

                                                                                                            +3
                                                                                                            Тогда каким образом это соотносится с другим Вашим утверждением:
                                                                                                            Да, этой сортировкой можно, сортировать все. Там нет привязки, к чему-либо.
                                                                                                              –5
                                                                                                              К чему вопрос? Как можно сортировать без сравнений? Разработан новый алгоритм, работающий по другим правилам. Можно сортировать текстовую информацию, целые и десятичные числа, положительные и отрицательные.
                                                                                                                +2
                                                                                                                К чему вопрос?

                                                                                                                К тому, что ваше утверждение, что ваша сортировка универсальна — некорректно.


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

                                                                                                                Но это не "все". Это текстовая информация, и некоторые виды чисел. У std::sort такого ограничения нет, и поэтому ваше сравнение некорректно.


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

                                                                                                                  +2
                                                                                                                  Можно сортировать текстовую информацию

                                                                                                                  О, кстати. Текстовую информацию, да. Любую?


                                                                                                                  Простой тест — вот есть три слова: linea, llamar, lonja. В каком порядке они будут после вашей сортировки?

                                                                                                                    –2
                                                                                                                    Если Вы работаете в кодировке ANSI и сортируете по возрастанию, то так и останется. Кода в кодировке ANSI: i-105, l-108, o-111. Первая буква «l» — у всех общая, поэтому сортироваться будет по 2-ой букве. Другие кодировки также работают.
                                                                                                                    И что подразумевается под «Любую?»?
                                                                                                                    К тому, что ваше утверждение, что ваша сортировка универсальна — некорректно. Почему? Я написал, что я могу сортировать текстовую информацию, целые и десятичные числа, положительные и отрицательные. Программа сортирует. После сортировки полностью, один в один, совпадает сортировкой, получаемой функцией std::sort.
                                                                                                                      +2
                                                                                                                      Если Вы работаете в кодировке ANSI и сортируете по возрастанию, то так и останется. Кода в кодировке ANSI: i-105, l-108, o-111. Первая буква «l» — у всех общая, поэтому сортироваться будет по 2-ой букве.

                                                                                                                      А это неправильно. Согласно правилам испанского языка (по-моему, в середине 90-х это отменили, правда, но не суть), должно быть вот так:


                                                                                                                      linea
                                                                                                                      lonja
                                                                                                                      llamar

                                                                                                                      А все потому, что ll — это диграф, на самом деле. И его нельзя сортировать просто по кодам в кодировке.


                                                                                                                      А если надо неотмененное правило, то пожалуйста: n ñ o, в Юникоде — 006E 00F1 006F.


                                                                                                                      И что подразумевается под «Любую?»?

                                                                                                                      А вот ровно пример выше: вы не смогли корректно отсортировать эту текстовую информацию.


                                                                                                                      Почему?

                                                                                                                      Потому что есть объекты, которые ваша сортировка сортировать не умеет.


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

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

                                                                                                                        +3
                                                                                                                        Можно и в русском языке пример найти: e (U+0435) → ё (U+0451) → ж (U+0436)
                                                                                                                        И в немецком: ss → ß → st
                                                                                                                        И, подозреваю, в любом другом языке, в котором используются грависы, акуты, циркумфлексы и прочие седильи и лигатуры.
                                                                                                                      +3
                                                                                                                      Как можно сортировать без сравнений?
                                                                                                                      ну вот же, например: radix sort, pigeonhole sort, counting sort. Эти сортировки имеют сложность худшего случая O(N), но у них у всех есть существенные ограничения, как и у Вашей. Вы же сами сказали, что Ваша сортировка «не относится к классу сортировок посредством сравнений». Зачем тогда спрашиваете?
                                                                                                            +3
                                                                                                            Функция std::sort является универсальной, ваша — специализированной для строк. Как ваш алгоритм ведет себя на сортировке чисел по сравнению с std::sort? Притом как целых, так и с плавающей запятой? Неизвестно.
                                                                                                              –4
                                                                                                              Пожалуйста, прочитайте комментарии. Я писал, уже, что она универсальна, на ней можно, и в том числе, числа (как десятичные, так и отрицательные).
                                                                                                                +3
                                                                                                                Э нет, так не пойдет, покажите результаты. Я не сомневаюсь в том, что это возможно, но я сомневаюсь, что вы сохраните 15% эффективности по сравнению с std::sort. Особенно в том, что касается чисел с плавающей запятой.
                                                                                                                  –5
                                                                                                                  15% — это реальные значения для текстовой информации, без всякого подгона, мухлежа. Для плавающей запятой сортировка также работает, но я не тестировал настолько, чтобы дать такую же информацию, как по текстовой.
                                                                                                                    +2
                                                                                                                    Это 15% по сравнению с относительно медленным алгоритмом, а потому неинтересно. А на плавающей запятой стоило бы потестировать.
                                                                                                                      +3
                                                                                                                      > без всякого подгона, мухлежа
                                                                                                                      Сознательного подгона и мухлежа. Подгон и мухлеж очень часто возникает в результате незнания, потому в университетах долго и сложно учат методикам проведения и анализа экспериментов, и годами два раза в неделю тренируют студентов практикумами, что бы они набрались опыта в этом деле. Правильные тесты — это сложно.
                                                                                                            +4
                                                                                                            для того, чтобы о чем-то рассуждать, надо знать, о чем рассуждаешь

                                                                                                            Вот-вот. Жаль, что вы сами не следуете этому принципу, путая IDE с языком программирования и не зная, как работает O-нотация (сложность 2*N)

                                                                                                            +3

                                                                                                            Вы попали в точку, судя по ответам ниже.

                                                                                                              +2
                                                                                                              фух, теперь понятно, что это мне напомнило.
                                                                                                              +3
                                                                                                              -50 за 12 часов — хорошее достижение, не каждому дано, приглашенные прогрессируют.
                                                                                                                +3
                                                                                                                Видимо, человек задался целью побить легендарные треды про BolgenOS
                                                                                                                +3
                                                                                                                Непонятна цель написания этой статьи. Похвастаться тайным алгоритмом, который у вас есть?
                                                                                                                  +2
                                                                                                                  Я проверил: ни одного комментария автора статьи без отрицательной оценки. Или флешмоб, или кому-то стоит подумать.
                                                                                                                    +2
                                                                                                                    А с какими комментариями автора Вы согласны?
                                                                                                                      +3
                                                                                                                      Откровенно говоря, я их даже не читал после второго. А имеет смысл?
                                                                                                                    +5
                                                                                                                    В Visual Studio используется, по моим данным, сортировка TimSort.

                                                                                                                    Я вообще-то не местный, к IT отношения не имею, больше так разнорабочим, грузчиком, кочегаром, дворником, иной раз газонокосильщиком и т.п. Но блин, последний же уборщик территории знает, что метод сортировки — это не к среде разработки VS, а к фрэймворк. Ну ведь гуглится же за секунду, что не TimSort, а introsort.
                                                                                                                    This method uses the introspective sort (introsort) algorithm as follows:
                                                                                                                    If the partition size is less than or equal to 16 elements, it uses an insertion sort algorithm.
                                                                                                                    If the number of partitions exceeds 2 * LogN, where N is the range of the input array, it uses a Heapsort algorithm.
                                                                                                                    Otherwise, it uses a Quicksort algorithm.
                                                                                                                    This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.
                                                                                                                    For arrays that are sorted by using the Heapsort and Quicksort algorithms, in the worst case, this method is an O(n log n) operation, where n is length.

                                                                                                                    Чувак пыжится что-то вякнуть против алгоритма в фрэймворк, но у него при этом нет даже тямы просто погуглить какой алгоритм он пытается обо*рать.

                                                                                                                    Я же указал, что было первоначальными массивами. Какая закономерность есть в «Войне и мире», в «Тихом Доме» и в остальных произведениях. Это абсолютно случайные данные, без каких-либо закономерностей. Разве, что в 3-ем и 7-ом тестах: вторая часть полностью повторяет первую. Но поверьте: данная закономерность нигде не используется. В остальных тестах даже такой закономерности нет.

                                                                                                                    Первоначальный массив — он абсолютно произвольный, никаким образом неупорядоченный, без каких-либо закономерностей — это худший случай?

                                                                                                                    Чувак над нами издевается. Чувак не видит разницу между набором слов русского языка и списком из элементов случайной длины от 1 до 96 байт (пар байт), где каждый байт — случайный от 0 до 255. I am speechless.

                                                                                                                    Закономерность, блин, в том, что элементов, которые сортируются — туева хуча, миллионы, миллиарды и т.д., но они нифига не разные все, их всего-то десяток, другой тысяч разных.

                                                                                                                    Загрузил словарь русского языка в кэш L1 современного процессора, а в L2 — ваш первоначальный нумерованный список. Пробегаете всего один раз по вашему нумерованному списку — если словаре в в кэше L1 нашли текущее слово — добавляете 1 в его счетчик, слово из списка удаляете. Если не нашли слова в словаре, — не удаляете, но при этом слове запоминаете номер позиции в словаре, куда бы это слово нужно было бы воткнуть. Используете встроенные ассоциативные возможности процессора по поиску в L1, если таковые имеются. Потом уже пробегаете по словарю, который уже не миллиарды элементов, а только десяток другой тысяч и собираете результат.

                                                                                                                    К сожалению, я не могу раскрывать все нюансы алгоритма. Могу только сказать следующее. На двигателе внутреннего сгорания невозможно улететь в космос, для этого нужны реактивные двигатели. В новой сортировке используется другой подход, поэтому и получились такие результаты.

                                                                                                                    А вот с пафосом у нас все OK. Хотя тоже можно было бы усилить, — добавить: Весь ход исторического процесса со всей убедительностью доказывает правоту ваших аргументов.
                                                                                                                      –1
                                                                                                                      Всем большое спасибо за интерес, проявленный к данной статье.
                                                                                                                      А как Вы отнесетесь, если я сообщу следующую информацию.

                                                                                                                      Я разработал алгоритм деления длинных чисел и написал программу на C++ в Visual Studio 2017. Также были проверены эти данные на MathLab, Java и других программах и языках.

                                                                                                                      Получил следующие результаты:
                                                                                                                      Разделил 100-значное десятичное число на 35-значное десятичное число в цикле 100 000 раз.
                                                                                                                      Время расчета на тестах (MathLab, Java и другие программы и языки) составляет — от 1/2 минуты и выше.
                                                                                                                      На моей программе рассчитывается на одном процессоре — 0,1 секунды.

                                                                                                                      Затем я разделил 225-значное десятичное число на 53-значное десятичное число в цикле 1 000 000 раз. На моей программе рассчитывается на одном процессоре – около 3 секунд.

                                                                                                                        +5
                                                                                                                        1. Вы так и не показали воспроизводимых результатов оценки вашей сортировки. Инструкции вам были предложены неделю назад.
                                                                                                                        2. Закодируйте и покажите ваш "бенчмарк деления" на актуальной версии python (там внутри GMP) и посмешите порадуйте нас результатами.

                                                                                                                        Пока вы этого не сделаете на ваши придумки не рационально обращать внимание.

                                                                                                                          +5
                                                                                                                          А как Вы отнесетесь, если я сообщу следующую информацию.

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

                                                                                                                            +5

                                                                                                                            А у меня есть алгоритм деления больших чисел, написанный на C лет 10 назад, я его запустил и получил следующие результаты.


                                                                                                                            Разделил 200-значное десятичное число на 73-значное десятичное число в цикле 100 000 раз.
                                                                                                                            На моей программе рассчитывается на одном процессоре — 0,07 секунды.


                                                                                                                            Затем я разделил 339-значное десятичное число на 117-значное десятичное число в цикле 1 000 000 раз.
                                                                                                                            На моей программе рассчитывается на одном процессоре – около 1 секунды.

                                                                                                                            +2
                                                                                                                            Господа, не кажется ли вам что это школьник/школьники на информатике рандомно сделали прогу и под острыми впечатлениями решили писать сюда? Где судя по комментам были раздавлены в пух и прах)))

                                                                                                                            Only users with full accounts can post comments. Log in, please.