Алгоритм сортировки строк

    Привет, Хабр! Предлагаю на ваш суд новый алгоритм сортировки. Не теоретические изыскания, а именно практическая реализация. Сортировка внутренняя и внешняя, «в одном флаконе», автоматически переходящая одна в другую в зависимости от наличия доступного ОЗУ. Сортировка строк, чисел, структур, «а также всего, что понадобится впредь».

    Сортировка воронкой является существенно улучшенным вариантом алгоритма сортировки слиянием. Принципиальное отличие состоит в том, что отсортированные массивы данных для слияния формируются динамически, а их размер определяется самой последовательностью входных данных. В частности, если массив уже отсортирован (в прямом или обратном порядке — это почти безразлично), сразу после окончания загрузки данных в ОЗУ они уже будут организованы в виде полностью отсортированного единого списка, который остаётся лишь отправить в выходной поток.

    Алгоритм можно условно разделить на несколько шагов:

    Шаг 1. Чтение исходных данных


    Воронка представляет собой набор из k упорядоченных списков (первоначально пустых). Чтобы минимизировать количество сравнений, текущий входной элемент, вне зависимости от числа элементов в списке, сравнивается лишь с головой и хвостом соответствующего списка: если он меньше или равен первому элементу — становится его головой, если больше или равен последнему — дописывается в хвост. Если ни то, ни другое — переходит к сравнению с головой и хвостом следующего списка (если такой имеется) либо сам образует очередной список, являясь в нём одновременно головой и хвостом. Таким образом, элементы этих списков образуют «воронку»: голова каждого следующего списка гарантированно больше головы предыдущего, а его хвост, соответственно, меньше. А потому при движении по «воронке» вероятность того, что очередной элемент будет куда-нибудь пристроен без увеличения размера воронки, довольно высока.

    Элементы входного потока размещаются в ОЗУ, которое также заказывается динамически, блоками не менее максимального размера элемента (как правило намного большими), по исчерпанию уже заказанного ОЗУ. Каждый элемент предваряется паспортом вида «размер элемента в байтах» (определяется при чтении элемента) и «адрес следующего элемента» (изначально обнулён), то есть входной поток данных преобразуется в список. Такая организация данных позволяет проводить сортировку без перемещения самих элементов и обеспечивает экономное расходование памяти для хранения неоднородных данных (обычно это строки, которые могут отличаться по длине в тысячи раз), и под каждый из них выделяется лишь тот объём, который требуется данному конкретному элементу.

    Шаг 2. Слияние списков


    Необходимость слияния списков возникает, если:

    • элемент не удаётся пристроить в воронку (все k списков воронки заполнены);
    • входной поток исчерпан (все данные загружены в ОЗУ);
    • исчерпано доступное ОЗУ (некуда размещать очередной элемент).

    Алгоритм слияния упорядоченных массивов хорошо известен: на каждом шаге берётся меньший из текущих элементов подмассивов и отправляется в результирующий массив. Счётчики номеров элементов результирующего массива и подмассива, из которого был взят элемент, увеличиваются на единицу. Когда один из подмассивов закончился, оставшиеся элементы второго подмассива добавляются в результирующий массив. Поскольку массивы в ОЗУ представлены в виде списков, слияние двух подмассивов происходит без перемещения самих элементов данных, что гораздо быстрее.

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

    В случае исчерпания входного потока данных или доступного ОЗУ все списки вначале попарно сливаются в один, начиная с самых мелких, а затем этот список отправляется в выходной поток. Процесс сортировки завершён.

    Шаг 3. Слияние файлов


    Этот шаг выполняется лишь при нехватке ОЗУ для размещения всего сортируемого массива данных. Слияние временных файлов производится в новый файл с последующим удалением двух сливаемых, до полного исчерпания временных файлов. Алгоритм слияния тот же, как и при слиянии списков.

    Оценка сложности алгоритма

    Алгоритм сортировки воронкой относится к классу алгоритмов, основанных на сравнении элементов. Они отличаются гибкостью применения, но имеют фундаментальное ограничение производительности для худшего случая: она не может быть лучше, чем O(n*log2n). Худший случай для данного алгоритма прекрасно известен: если входной поток также отсортирован «воронкой» и не имеет одинаковых элементов, т.е. а) минимальный элемент б) максимальный в) минимальный из оставшихся г) максимальный из оставшихся (например при сортировке чисел: 1, 99, 2, 98, 3, 97, ...) и т.д. В этом случае в массив воронки поместится только два элемента, и алгоритм фактически сводится к классическому алгоритму сортировки слиянием, у которого первый шаг совмещён с процессом чтения элементов в ОЗУ. Как известно, этот алгоритм имеет именно такую сложность O(n*log2n) — как для худшего случая, так и для лучшего. Практика, однако, показывает, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы, а любая восходящая или нисходящая подпоследовательность будет гарантированно «поймана» воронкой размером даже в один список! А потому сортировка воронкой для лучшего случая (когда входные данные уже отсортированы) будет выполнена за линейное время O(n).

    Среднюю сложность при случайном распределении входных данных можно оценить лишь вероятностно. Очевидно, что чем больше в исходных данных монотонно возрастающих или убывающих подпоследовательностей, чем больше там повторяющихся элементов, тем «линейнее» будет время сортировки — особенно, если учитывать время загрузки исходных данных и записи результатов. Тем более, что при чтении и записи данных доступ к ним последовательный, то есть максимально быстрый. Эксперименты показали, что время сортировки соизмеримо со временем копирования файлов или любой другой линейной обработки данных. Тестирование на специально подготовленных массивах для лучшего и худшего случая объёмом от миллиона до ста миллионов строк показало: несмотря на то, что количество сравнений элементов отличается на порядки, общее время сортировки замедляется лишь на десятки процентов (во всех экспериментах менее, чем в два раза). Для сравнения: нехватка ОЗУ из-за резкого увеличения числа файловых операций замедляет время сортировки в десятки раз. Таким образом, если теоретическая сложность для худшего случая всё-таки логарифм, реальная сложность работы программы — линейная: время работы худшего случая лишь вдвое превышает время для лучшего, заведомо линейное.

    Достоинства и недостатки

    Достоинства:

    • один из самых быстродействующих (на практике) из алгоритмов внутренней и внешней сортировки общего назначения;
    • универсален. Сортирует практически любые типы данных — в частности, массивы с элементами постоянной или переменной длины;
    • поточная обработка входных данных: если для других алгоритмов требуется предварительно закачать весь массив данных в ОЗУ, после чего начинается собственно сортировка, то у «воронки» она к этому времени практически закончена;
    • естественность поведения: при обработке уже упорядоченных или частично упорядоченных данных время сортировки заметно уменьшается;
    • работает в условиях ограниченных ресурсов (нехватка ОЗУ);
    • работает на структурах данных последовательного доступа;
    • не имеет «трудных» входных данных;
    • прост в реализации;
    • требует лишь O(n) дополнительной памяти для своей работы.

    Недостатки:

    • неустойчив.

    Вообще говоря, устойчивость алгоритма не является проблемой, если все ключи разные (это зависит от входных данных) или когда одинаковые элементы неразличимы — например, когда весь элемент является ключом (именно так и устроен алгоритм сравнения элементов в данной реализации). В крайнем случае, алгоритм может быть легко доработан для обеспечения устойчивой сортировки путём расширения ключа исходным индексом элемента в массиве. В случае равенства основных ключей сравнение производится по индексу, исключая, таким образом, возможность изменения взаимного положения равных элементов. Эта модификация требует дополнительной памяти в размер индекса на каждый элемент, который инициализируется значением в момент чтения массива в ОЗУ.

    Реализация

    Самое очевидное улучшение алгоритма — разделить процессы заполнения списков воронки и их слияния, а также определиться с оптимальным размером самой воронки: при увеличении максимального количества списков в ней растёт (хотя и незначительно) время на поиск места для размещения очередного элемента, а при его уменьшении начинает тормозить процесс слияния списков — ведь в них может находиться от двух элементов до многих тысяч и даже миллионов! Эксперименты показали, что размер воронки почти никак не влияет на эффективность (тестировались воронки в 1, 2, 4, 8,… 64 списка): увеличение времени на пристройку элемента почти компенсируется уменьшением числа слияний более крупных списков. Поэтому был реализован самый простой вариант с размером воронки в один список, требующий не более двух сравнений для пристройки элемента. А вот размер буфера отсортированных списков до слияния, напротив, был выбран достаточно большим (1024 списка), при переполнении которого сливаются сразу три четверти самых маленьких списков этого буфера (до 256). Такая технология позволяет эффективно сортировать неудачные (близкие к худшему случаю) наборы исходных данных, объединяя крупные массивы лишь перед записью результатов в файл.

    Оптимизация процесса слияния временных файлов мало актуальна и заметна лишь при серьёзной нехватке ОЗУ, когда количество нарезок на файлы и последующих слияний достигает сотен и даже тысяч — например, при сортировке гигабайтных файлов утилитой, скомпилированной для MS-DOS с объёмом доступного ОЗУ в 300-400 килобайт. Но даже в этом случае сортировка происходит достаточно уверенно и не очень долго. Максимальное количество файлов определено в 36 (цифры и буквы латинского алфавита) со схлопыванием при переполнении сразу до 16.

    Развитие

    Алгоритм сортировки воронкой (как, впрочем, и другие алгоритмы, основанные на сравнениях) обладает неплохим потенциалом для повышения функциональности. В текущей реализации сортировка проводится по возрастанию значения байта данных в строке — наиболее универсальный механизм сравнения, позволяющий сортировать тексты на разных языках и структуры данных, содержащие нетекстовые символы. Но, в идеале, метод сравнения элементов должен быть настраиваемым пользователем (или вообще пользовательским). В частности, можно обеспечить возможность сортировки по возрастанию или убыванию, по алфавиту русского (в кодировках WIN-DOS-KOI-UTF et cetera), арабского, китайского и других языков, с игнорированием регистра символов или без него, сортировки данных разных типов (целочисленных, вещественных, даты, время), сортировки по полям таблиц и других структур, возможность переопределения значения терминатора (по умолчанию — символ перевода строки 0x0A) или длины массива (при сортировке структур данных постоянной длины) и т.д. В любом случае, настраивается лишь процедура сравнения элементов — весь остальной алгоритм сортировки «воронкой» остаётся неизменным.
    Поделиться публикацией

    Комментарии 426

      +1
      Таким образом, если теоретическая сложность для худшего случая всё-таки логарифм, реальная сложность работы программы — линейная: время работы худшего случая лишь вдвое превышает время для лучшего, заведомо линейное.

      Эту чушь лучше убрать. Если теоретическая сложность логарифм, реальная сложность не может быть линейной. То что худший случай вдвое превышает лучший не имеет к этому отношения.
        –13
        Это не чушь. В теории — да, что-то похожее на логарифм (хотя и входной поток должен быть отсортирован так, что последующее слияние списков будет разбавлено пришлёпыванием хвостов без каких-либо сравнений), а вот НА ПРАКТИКЕ — если учитывать время загрузки и выгрузки массивов в ОЗУ, время растёт именно линейно. Причём самая длинная часть — это ЗАПИСЬ отсортированного списка в файл. Чуть быстрее работает чтение, совмещённое с начальной сортировкой. И самая маленькая часть алгоритма — это как раз работа в ОЗУ. Я реально тестировал алгоритм для худшего и лучшего случая на массивах в миллион, 10 миллионов и 100 миллионов строк, я уже насортировал за это время десятки, если не сотни миллиардов элементов! Так что РЕАЛЬНАЯ скорость работы алгоритма именно ЛИНЕЙНАЯ!
          +8
          Причём самая длинная часть — это ЗАПИСЬ отсортированного списка в файл. Чуть быстрее работает чтение

          Которые не имеют никакого отношения к алгоритму сортировки.


          Чтобы говорить о производительности алгоритма сортировки, нужно измерять именно время сортировки, а не время ввода-вывода, время запуска jvm, время прогрева jit-компилятора и т.д.


          Иначе с таким же успехом можно говорить, что самая длинная часть — это включение компьютера, а потому "реальная сложность работы программы — константа" (с). Можно даже насортировать ради этого десятки и сотни миллиардов элементов (не забывая перезагружать компьютер перед каждой сортировкой)! Так что РЕАЛЬНАЯ скорость работы получится именно КОНСТАНТНАЯ!

            –9
            Совершенно верно. Для теоретиков! А я — практик, для меня имеют! Но ведь вроде как доказано, что алгоритмы, основанные на сравнениях, меньше логарифма быть не могут? Ну так пусть теоретики подавятся этим логарифмом! А вот средняя сложность — уж извините. стремится к O(n).
              +5

              Да нет, ввод и вывод все же не имеет никакого отношения к алгоритму. Что в теории, что на практике.


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


              Но вы же топите не за вашу реализацию, а за алгоритм. А меряете при этом не алгоритм, а непонятно что.
              Ну а оценивать асимптотику по соотношению времени работы с лучшим и худшим случаями — это вообще за гранью добра и зла.


              А я — практик

              Скажите мне, как практик практику, каким образом я могу на практике убедиться в эффективности вашего алгоритма или хотя бы реализации? Если так жалко кода — дайте хотя бы экзешник. Планируемый онлайн-сервис — задумка бредовая. Во-первых, хоть сколько-нибудь большой объем отсортировать не получится из-за банальных отвалов по таймауту (разве что вы заморочитесь и сделаете каким-то образом асинхронные задачи). Во-вторых, сортирующим и измеряющим по-прежнему будет недоступна информация о железе сервера и его загруженности в момент сортировки. И в-третьих, судя по вашим подходам, время сортировки ваш сервис будет измерять с учетом загрузки и выгрузки данных по сети, так что опять таки окажется, что время работы вообще КОНСТАНТА!1! А для плохого мобильного интернета — так и вообще иногда убывающая функция!

                –1
                Господи, да ловите! У меня на cайте давно валяется версия для DOS, с объёмом доступного ОЗУ в 300-400 кило. Входной файл должен располагаться в текущей папке и имет имя file.i, выходной будет file.o, символ окончания строки 0x0A, последний элемент должен оканчиваться этим же символом, сортирует по возрастанию байта данных, максимальный размер строки, насколько я помню, 16К, минимальный, соответственно, 1 байт (тот самый 0x0A).
                sint.wc.lt/sortir.exe

                Практически эта же статья, только с «весёлыми картинками» расположена по адресу sint.wc.lt/sortir.htm Наслаждайтесь!

                Да? А ПОЧЕМУ, собственно, «онлайн-сервис — задумка бредовая»? И что значит «сколько-нибудь большой объем»? ПОкопайтесь в Инете — ЧТО там предлагается. А мы планировали ограничить размер файлов для сортировки величиной 100 мегов (такие объёмы сортируются за секунды). Вам мало? Ну-ну… ;)
                  +6
                  sint.wc.lt/sortir.exe
                  Это у аглоритма такое название?
                    –1
                    У алгоритма тоже. И заметка так называлась, пока была в Песочнице. Тамошние модеры зарубили — «недостаточно информативно», говорят. :)
                    +6
                    Спасибо. Я потестировал.

                    Сравнивал с другой DOS-программой для внешней сортировки строк — с RPSORT.

                    На моих данных получились следующие результаты:
                    rpsort: 1.17 sec
                    sortir: 20.20 sec


                    Итого sortir получился примерно в 17 раз медленнее.

                    image
                      0
                      Почему автор на это не отвечает?
                        0
                        Автор в гостях и температура 38. И чьл за массив в пару сотен тысяч строк и в несчастные 4 миллиона сравнений? Даже ДОСовская версия сортирует такую хрень за доли секунды!
                          +1
                          4 миллиона сравнений это при сложности n*log2(n), а у вас линейная вы пишите должно быть меньше!
                            0
                            Должно, наверное — по крайней мере, если ВСЯ сортировка происходила в ОЗУ. Но не сам же я эти данные приписал! Да я их и в глаза не видел! Но методику проверки описал. АУ, valexey, провести проверку можете?
                              0
                              Дайте ссылочку на описание методики.

                              Я смогу что-то еще потестить примерно в понедельник.
                                0
                                Да уже не надо — я хотел file.o переименовать в file.i и посмотреть, как изменится количество сравнений. Но уже и без того ясно, что раз исходник размером 10М, там должно быть 2-3 десятка временных файлов.
                              0
                              Может у него линейная сложность с большой константой-множителем )))
                                0
                                У меня, что ли? При NT-шной сортировке количество считанных (читай, что уже почти и отсортированных) элементов меняются со скоростью примерно миллион в секунду (думаю, даже больше). Так что гадать по поводу «констант-множителей» предлагаю другим — лично меня ВСЁ устраивает.
                                  0
                                  К сожалению NT-шной сортировки нам не было дадено, поэтому я сравнивал вашу DOS-сортировку с другой DOS-сортировкой (1992 года) в одинаковом окружении и на одинаковых данных.
                                    0
                                    Правильно, так и надо! Только ПОВТОРИТЕ сортировку на уже отсортированном массиве! file.o переименуйте снова в file.i и запустите сортир. Сколько сравнений получилось? И, если заметили, были ли там промежуточные файлы и сколько именно?
                                      0
                                      Промежуточные файлы точно были (я их видел, да, они были и для sortir.exe и rpsort). Это же DOS-программа, в память все данные никак не влезут. Файл (FILE.I) был размером 10 Мб.
                                        0
                                        А, ну тогда понятно: если 10 мегов, то там было порядка 20 промежуточных файлов, и файловые операции сожрали всё время. Непонятно только, как rpsort умудрилась с ними за две секунды управиться. :)
                                          0
                                          Ну, поэтому я и просил дать возможность потестить версию не ограниченную 400..500 Кб ОЗУ.

                                          И поэтому я и нашел соперника для сравнения DOS-sortir.exe, чтобы было с чем сравнить — как другие справляются с большими (для ДОСа) файлами.
                                            +2
                                            Замечательно! Кстати, а какие объёмы временных файлов у сортира и соперника? И что будет, если попробовать сортировать мегов 500?
                                              0
                                              Какие объемы временных файлов я точно не помню, но помню, что у sortir.exe это было много мелких файлов, а у rpsort было немного больших (3 может 4 файла).

                                              Я пробовал еще сортировать 100 Мб файл, окончания работы sortir.exe я так и не дождался.

                                              Но могу попробовать ещё.
                                                0
                                                Уж попробуйте, если Вас не затруднит.
                                                  +2
                                                  Думаю где-то в понедельник будут результаты.

                                                  Но, безусловно, я бы с бОльшим удовольствием работал бы с чем-то более актуальным нежели DOS-версия проги :-)
                                                    +1
                                                    Файл этот 100-меговый не можете куда-нить забросить, чтобы я тоже посчитал?
                                                  +1
                                                  Ну так сортир, по крайней мере, говорит, как там у него идут дела. Я несколько раз сортировал им гигабайтные файлы (до 4Г включительно) — да, конечно, версия для NT куда веселее работает, но и этот тоже сортирует. А если «3, может 4», то это означает, что ОЗУ у rpsort исчислялось всё-таки мегабайтами. Размер файлов сортира — это и есть объём доступного ОЗУ, не считая, что там ещё 6 байт на элемент тратится на организацию списков.
                                                    0
                                                    Размер файлов сортира — это и есть объём доступного ОЗУ
                                                    Когда у вас DOS-версия сортирует 4-гиговый файл, на последнем шаге она сливает 2 файла по 2 гига в один на 4 гига? Размер файла = размер ОЗУ = 2 гига?
                                                      +1
                                                      А если попробовать подумать? ;) Слияние файлов вообще требует места в ОЗУ только для ДВУХ (текущих) элементов каждого файла.
                                                      0
                                                      Всё запускалось из под DOS, так что в плане доступа к памяти у всех были равные возможности. Я же не из Windows запускал :-)

                                                      Может оно конечно нашло extended/expanded memory и заюзало её. Я эту возможность тоже обрежу.

                                                      Файл тот сейчас на машине к которой до понедельника у меня нет доступа.
                                                    0
                                                    1 миллион строк, 64 Мб, средняя длина строки 64 байта, диск SSD.

                                                    RPSORT — 34.28 секунд
                                                    SORTIR — 145.27 секунд

                                                    RPSORT в 4.2 раза быстрее



                                                    ОС FreeDOS
                                                    Программа RUNTIME взята здесь в разделе Development
                                                    Программа RPSORT взята здесь, файл rpsrt102.zip
                                                      0
                                                      На всякий случай спрошу — проверялась ли корректность выполнения? То есть выхлоп от rpsort и sortir одинаковые?

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

                                                      Потом я это поправил.
                                                        0

                                                        Да, fc в DOS дальше 32765 строк не сравнивает, fc в Windows говорит, что различий нет. Концы строк в файле CRLF.

                                                        +1
                                                        Отлично! Спасибо! Это уже всё-таки миллион элементов и 64 мега весом. Почти то, что мы хотели разместить на веб-сервисе для сортировки.

                                                        А я тем временем скачал файл antarctica из OSM (http://download.geofabrik.de/index.html) 687 мегов, 10257561 строка. Сортир для NT отсортировал это дело за 1 минуту 55 секунд, 142.5 миллиона сравнений, без промежуточных файлов. Тачка здесь… ща… Pentium 4 CPU 2.6 GHc, Windows 7 «Домашняя базовая», 32-разрядная, ОЗУ 2 гига. rpsort… а, блин: ERROR 043: Line exeeds max length of 32750 bytes. Тогда и ДОСовский сортир должен бы был заткнуться… О пошёл файлы плодить! :) 46 мегов… 75 мегов… 103 мега… 131 мег… где-то на 140 метрах две минуты прошло… ладно, пошёл покурить — 202 метра, 30% файла считано, 4% записано… покурил — 442 метра, 66% файла считано, 8% записано, 10 минут прошло — полёт нормальный… а где же длинные строки? Насколько я помню, здесь у меня ограничение 16К на строку, а rpsort МГНОВЕННО отказался сортировать! ОППА! 17 минут — 100% считано! Так что, скорее всего, там НЕТ столь длинных строк, это какой-то глюк у rpsort. Да и я, насколько помню эту базу, никогда там ничего особо длинного не встречал. Так, пошло слияние файлов, самый мелкий из них на данные момент 55М. Нет, уже 57М и 8 осталось слить. 7… 6… 5… 20 минут прошло и файлы уже не менее 100М каждый… 4… 3… 2… готово! 25 минут всё удовольствие (чуть меньше). Не так уж и плохо, господа? ;)

                                                        Да, запустил fc/b для результатов двух сортиров — думаю, он будет добрых полчаса сравнивать. Но пока я это писал, различий не найдено. :)

                                                        Ах, да — у ДОСовского сортира 173.8 миллиона сравнений — это паразитный довесок от слияния файлов.

                                                        Нет, fc/b довольно быстро отработал. Как и ожидалось, «различия не найдены».

                                                        А у меня тем временем карму загнали в минус — теперь не могу комментировать чаще, чем раз в пять минут". Уроды закомплексованные…
                                                          +1
                                                          Для rpsort концы строк должны быть DOS/Windows, в вашем файле у вас концы строк юниксовые, поэтому rpsort считает что у вас там ровно одна строка.

                                                          Сконвертируйте файл с помощью unix2dos.
                                                            0
                                                            А я тем временем скачал файл antarctica из OSM (http://download.geofabrik.de/index.html) 687 мегов, 10257561 строка. Сортир для NT отсортировал это дело за 1 минуту 55 секунд
                                                            Обычный sort из Windows чуть быстрее. После сортировки файл становится больше из-за конвертации переводов строк в 0D 0A
                                                            Скрытый текст

                                                              0
                                                              Вы не знаете быстрее он или медленнее — вы же на разных машинах запускали.
                                                                +1
                                                                Это во-первых. А во-вторых, виндовый sort принципиально отказывается сортировать с учётом регистра символов. Я и пользовался им раньше, но он меня вконец достал, и я написал НОРМАЛЬНЫЙ сортир.

                                                                Здесь-то, может, результаты и близкие, но когда он сортирует UTF-8, да если там записи одновременно на разных языках… а от сортировки данных в формате base64 вообще повеситься можно. Мой же сортир сортирует по возрастанию байта данных. Вот отсортированная antarctica, если интересно
                                                                sint.wc.lt/antarctica.7z
                                                                  0
                                                                  Вы понимаете, что это только плюс к скорости виндового sort.

                                                                  Потому что он всегда сортирует без учёта регистра, имеет опции выбора локали, учитывает utf-8 и т.п. — это всё время и немалая сложность (например, ё одним знаком и е + две диакритических чёрточки = одно место в отсортированном списке).

                                                                  Не то что примитивно «сортир сортирует по возрастанию байта данных». Если из sort.exe удалить все извраты с локалями, представляете, как он залетает!!!
                                                                    –4
                                                                    Да конечно «плюс»! Только сортировать им невозможно! Эта придурь формат base64 без учёта регистра символов! Ну и хули с этим говном по кличке «результат» прикажете делать?
                                                                  0
                                                                  Так то на моем, далеко не самом новом ноуте не самой быстрой сортировкой этот файл сортируется за 10 секунд.

                                                                  На десктопе скорее всего будет сортировать секунды за 2-4.
                                                                    +1
                                                                    Кто? antarctica? У меня он копируется полминуты! А во время сортировки входит и время чтения данных, и время записи результатов, и время слияния временных файлов, если таковые имеются.
                                                                      +1
                                                                      Ну да, запускаем на разных машинах, поэтому цифры сравнивать нельзя.
                                                                        +1
                                                                        Ну, теперь-то Вы имеете возможность сравнивать? :)
                                                                +1
                                                                файл antarctica из OSM

                                                                Файл antarctica-latest.osm, 10257561 строк, размер 696.8 Мб, концы строк CRLF.
                                                                Диск HDD, на SSD столько места не было.
                                                                Прошу заметить, что код выполняется в виртуальной машине, а не на реальном железе.

                                                                rpsort
                                                                1496.81 секунд (24 минуты 56.81 секунд)

                                                                sortir
                                                                9363.62 секунд (2 часа 36 минут 3.62 секунды)

                                                                rpsort быстрее в 6.2 раза.

                                                                Размер раздела FAT 2 Гб, свободного места соответственно 1.3 Гб.
                                                                rpsort не хватило места для временных файлов, поэтому файл был скопирован на другой раздел.






                                                                  +1
                                                                  Да, впечатляет. Правда, «на реальном железе» как раз сортир отрабатывает за те самые неполные 25 минут, а rpsort вообще отказывается работать. :)
                                                                    +2
                                                                    rpsort не работает не из за железа а из за формата входных данных. Я же писал про это.
                                                                      +2

                                                                      Это не он отказывается работать, это вы для DOS программы подсовываете кривой файл с Unix переводами строк. Который она считает одной большой строкой, потому что последовательности "\r\n" в нем нет. Вам же уже сказали, как это исправить — поменяйте в файле любой программой "\n" на "\r\n", потом запускайте еще раз rpsort на своем железе. Если хватит смелости публично признать свою ошибку, напишете результаты сюда.

                                                                        +1
                                                                        Да без проблем, Господи! Моя программа тоже под DOS, но прекрасно работает как с \n, так и с \r\n. Откуда мне знать, что rpsort на этом хромает?

                                                                        Хренассе, DOS! Файл 57030401.BPB тут же запрыгнул на 191 Мб! А 57030601.BPB ваще на 627М! Правда, там какая-то хрень записана, ничего общего с исходными данными не имеющая… но отсортировала быстро, чуть более двух минут. Фактически со скоростью версии для NT. Но не надо мне сказки рассказывать, что она для DOS — память она явно отжирает гигабайтами!

                                                                        Ага, а сортировки разные — эта явно сортирует без учёта регистра символов, как и Виндовый сортир. Надеюсь, у неё это хотя бы настраивается?
                                                                          +2
                                                                          Моя программа тоже под DOS, но прекрасно работает как с \n, так и с \r\n.
                                                                          А этот алгоритм мне понадобился в самом конце декабря

                                                                          Вас не смущает, что ваша программа написана в 2018 году (когда Linux-системы на каждом углу), а rpsort в 1991 (когда Linux еще месяца не было)?


                                                                          Но не надо мне сказки рассказывать, что она для DOS — память она явно отжирает гигабайтами!

                                                                          В моем примере она работала в чистом DOS без всяких драйверов для расширенного доступа к памяти. Может перестанете приводить домыслы и будете ориентироваться на факты?


                                                                          Надеюсь, у неё это хотя бы настраивается?

                                                                          Напишите rpsort.com /? и узнаете.

                                                                            0
                                                                            Нисколько! Ибо в 1991 году на планете Земля ещё водились программисты!

                                                                            Дело не в драйверах — дело в количестве файлов. Их было ТРИ ШТУКИ. Причём два служебных. Так что сортировать она могла ТОЛЬКО в ОЗУ!

                                                                            Да зачем? У неё и доки какие-то валяются…
                                                                            Switches Which Set Defaults For Sort Keys /A — Sort all Text Keys in ASCII (Case Sensitive) Sequence

                                                                            Что-то непохоже на «Set Defaults»… а, ну да — там же не ASCII!
                                                                              +2
                                                                              Нисколько! Ибо в 1991 году на планете Земля ещё водились программисты!

                                                                              И откуда они должны были знать, что через 28 лет в будущем кто-то запустит их программу с другими символами перевода строк? Программа для DOS, ориентирована на производительность компьютеров 1991 года, делать там поддержку другого перевода строк нафиг никому не надо было.


                                                                              Так что сортировать она могла ТОЛЬКО в ОЗУ!

                                                                              Я вам еще раз предлагаю перестать использовать домыслы. Не использует эта программа больше одного стандартного мегабайта DOS. Ну вот так вот она написана. Независимо от того, что вы об этом думаете.


                                                                              Что-то непохоже на «Set Defaults»

                                                                              Может надо весь раздел прочитать, а не вырывать фразы из контекста?

                                                                                0
                                                                                Я ни чего и не говорю — эту программу писали настоящие программисты! В отличие от этого «сообщества разработчиков», которые только рот затыкают этими мудацкими «кармами». Ну и чего мне делать? Сюда писать коммент или внизу соблаговолили-таки привести код слияния пары списков? А сортировать она могла ТОЛЬКО в ОЗУ — больше тупо негде. Если она «не использует больше одного стандартного мегабайта DOS» (кстати, кто Вам это сказал?), то ГДЕ ИМЕННО она сортирует файл в сотни мегабайт? Мой сортир лепит туеву хучу файлов огрызками в размер доступного ОЗУ — это понятно. Команда sort образца Win-95 лепила промежуточные файлы СОТНЯМИ (да ещё, сволочь, втихаря разбивала длинные строки — типа «отсортировала»), sort образца Win-NT, насколько я заметил, создаёт лишь один временный файл (и сортирует на несколько порядков быстрее, чем «предшественник»), в разбиении длинных строк не замечен, но сортирует, падла, без учёта регистра символов.

                                                                                Ладно, почитаем описание… RPSORT can sort very large files… RPSORT is very fast and can sort files containing hundreds of kilobytes and thousands of records in just a few seconds (I am assuming a 286 CPU and a hard disk). However, if you are sorting a really large file (say 20 megabytes) then the execution time could be a some number of minutes.
                                                                                Ну, всё логично. Но «hundreds of kilobytes and thousands of records» меня не интересуют — версия реально оперирует сотнями мегабайт и миллионами строк!

                                                                                RPSORT compares two records/lines, at a time, to determine which comes first and swaps them, if necessary, to put them in the right sequence. The comparisons continue until the entire input has been sequenced.
                                                                                Чаво?! Это чуть ли не пузырёк описывается. :)

                                                                                RPSORT uses the quicksort algorithm (invented by C. A. R. Hoare in 1962) to determine which records/lines to compare.
                                                                                Оба-на! Так это классический квик? Ну, и как же опорный элемент выбирается? Ах, да — он же «сильно деградирует по скорости (до O(n^2) в худшем или близком к нему случае), что может случиться при неудачных входных данных». То есть, если сортировать уже отсортированный массив… да ничего подобного! Отсортировал за те же две минуты! То есть либо Вики врёт, либо никакой это не квик, а куда более умелая реализация. Браво! Кто там… Bob Pirko — БРАВО!

                                                                                If the input file(s) are small enough to fit in the available memory space the sort is done in one pass in memory. If the input is too big to fit into memory, it is read in chunks and each chunk is sorted and written to a temp file. Then RPSORT uses one or more merge phases to combine the chunks into the sorted output file.
                                                                                Блин, ну один в один мой сортир! Только у меня МНОГО файлов, а у него ОДИН временный файл. И что, это важно? Хм… а может быть и важно! Там же списками можно хранить, а не перечитывать и пересравнивать заново!

                                                                                If the last record in an input file does not terminate with CRLF or LFCR, RPSORT will append these two characters and display a message informing you of its action.
                                                                                Блин, ну чуть ли не дословно, что я Димке писал, когда он мне подсунул файл без финального терминатора строки и сортир его, соответственно, послал на. Ну какой же кайф читать профессионала, а не бредни этого «сообщества разработчиков»! Снимаю шляпу! RPSORT — изумительная программа! Но воронка всё равно лучше! :)
                                                                                  +1
                                                                                  Но воронка всё равно лучше!
                                                                                  — Чем лучше?
                                                                                  — Чем грузины! :D
                                                                                    +1
                                                                                    В отличие от этого «сообщества разработчиков», которые только рот затыкают этими мудацкими «кармами»

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


                                                                                    Сюда писать коммент или внизу соблаговолили-таки привести код слияния пары списков?

                                                                                    Вам внизу уже приведена полностью работающая программа. Код слияния двух списков находится в функции performMerge(). Если вам другие функции мешают, скопируйте ее отдельно.


                                                                                    Если она «не использует больше одного стандартного мегабайта DOS» (кстати, кто Вам это сказал?), то ГДЕ ИМЕННО она сортирует файл в сотни мегабайт?

                                                                                    Я прочитал описание в документации, посмотрел код на ассемблере, запустил программу в виртуальной машине с соответствующим ограничением по памяти. Если хотите узнать, где именно, рекомендую вам сделать так же.


                                                                                    Так это классический квик?
                                                                                    Только у меня МНОГО файлов, а у него ОДИН временный файл. И что, это важно?

                                                                                    Важно то, что она работает быстрее вашей программы. Мы же это проверяли, а не что-то другое.


                                                                                    Блин, ну чуть ли не дословно, что я Димке писал, когда он мне подсунул файл без финального терминатора строки и сортир его, соответственно, послал на.

                                                                                    В этой части говрится, что rpsort сама добавляет эти символы. Ваша программа так не делает. Вы всем рассказываете, какой вы крутой настоящий программист, а такой банальный случай не предусмотрели. Обратите внимание на себя, прежде чем обвинять в некомпетентности других.


                                                                                    Но воронка всё равно лучше!

                                                                                    Про субъективные неизмеримые характеристики мы не говорили. По конкретным цифрам она хуже.


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


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

                                                                                      –1
                                                                                      Да я не про себя говорю — я про всех говорю! Это именно затыкание рта. Оскорбить вообще невозможно — можно лишь оскорбитьСЯ. Я тоже мог бы оскорбляться на всякие грязные домыслы, что я «украл чужую программу и что-то там поправил в hex-редакторе», но я же не полный дебил, чтобы оскорбляться! Это просто повод для затыкания рта неугодным, не более.

                                                                                      Приведённый код слияния списков (что у Вас, что у второго автора) есть полное дерьмо — он именно КОПИРУЕТ два сливаемых списка в третий, а исходные уничтожает. При этом BugM ещё и утверждает, что он «привел код самого оптимального метода слияния очередей, лучше сделать невозможно»! Заказать новый массив, скопировать туда два старых, освободить память двух исходников — и это называется «невозможно лучше»? Господа программисты, мне стыдно за вас! Кстати, я и под исходный массив (у вас обоих, как я понимаю, ВООБЩЕ НЕТ ни ввода данных из файла, ни вывода в него результатов?) заказываю ОЗУ блоками (кажется, по четверть мегабайта), а не дёргаю операционку на каждый чих.

                                                                                      Да, rpsort действительно работает великолепно! Тем более удивительно, что Гугл её даже найти толком не может (подсовывает «Что такое RPSORT.COM и как его исправить?»), а Яндекс и вообще подсовывает ссылку… на эту самую ветку! Программа написана чёрте когда, но в Виндах встроено полное дерьмо sort для Win95 и почти бесполезная sort для WinNT! Однако, сам автор говорит, что это разновидность QuickSort и, следовательно, имеет квадратичную сложность для худшего случая (правда, указанный в Вики вариант для худшего случая автор виртуозно обошёл). Кроме того, воронка намного проще в реализации, легко и весело ловит все частично упорядоченные подпоследовательности (между прочим, Timsort как раз и «основан на том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы») и прекрасно себя чувствует даже в худшем случае, причём вероятность этого худшего случая исчезающе мала.

                                                                                      Да, моя программа «так не делает», потому как это неряшливость представления данных, и делать я это собирался только для веб-сервиса, причём финальный терминатор всё равно бы обрезал, чтобы сортируемый и отсортированный массивы совпадали байт в байт. Я работаю с базами данных много лет, и с подобной неряшливостью не сталкивался ни разу. А как продукт ВОВНЕ — можно и обработать (в настоящий момент программа на это вылетает с диагностикой invalid data).

                                                                                      Нет, Вы поняли неправильно: под O(N) я подразумеваю именно число сравнений, и потому (и только потому оценка для худшего случая всё-таки логарифм), при этом фактическое время работы растёт фактически линейно даже для худшего случая — ну, «подрочит» она немного в ОЗУ мелкие массивы — какая разница? Это почти незаметно по времени (всего лишь десятки процентов замедление) И это У ВАС при слиянии списков происходит «перемещения элементов (даже если это указатели)» — у меня и указатели стоят на месте — только их значения иногда меняются.

                                                                                      Неправда Ваша: ЕСЛИ БЫ я «обращал внимание только на число сравнений элементов в 2 штуки при добавлении в воронку, а число сравнений при слиянии списков вообще не учитывал», ТО число сравнений было бы ВСЕГДА менее удвоенного числа этих элементов. Сравнения я учитываю даже при слиянии файлов при нехватке ОЗУ, в результате чего их количество при сортировке ДОС-версией было на 30 миллионов больше, чем при сортировке версией для NT (без образования промежуточных файлов). А вот Вас бы я попросил «правильно посчитать» число сравнений при сортировке УЖЕ ОТСОРТИРОВАННОГО массива данных — просто для того, чтобы убедиться, что у Вас действительно запрограммирована воронка, а не что-либо иное.
                                                                                        +2
                                                                                        Оскорбить вообще невозможно — можно лишь оскорбитьСЯ.

                                                                                        Мне пофиг, что вы об этом думаете. Я на этот сайт пришел читать информацию по программированию, а не оскорбительные слова и нецензурную брань. Об этом явно написано в правилах, с которыми вы соглашались при регистрации.


                                                                                        "Вот список того, чего на ресурсе делать не следует:

                                                                                        Оскорблять других пользователей, не следить за эмоциями
                                                                                        Мат, оскорбления, переходы на личности, эвфемизмы, троллинг — хорошие способы быстро и надежно сменить текущий статус аккаунта на ReadOnly."


                                                                                        Вы их нарушаете, и о последствиях вам говорили заранее.


                                                                                        он именно КОПИРУЕТ два сливаемых списка в третий, а исходные уничтожает

                                                                                        Как у вас статье написано, так и сделано.
                                                                                        "Алгоритм слияния упорядоченных массивов хорошо известен: на каждом шаге берётся меньший из текущих элементов подмассивов и отправляется в результирующий массив."


                                                                                        И это У ВАС при слиянии списков происходит «перемещения элементов (даже если это указатели)» — у меня и указатели стоят на месте — только их значения иногда меняются.

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


                                                                                        Нет, Вы поняли неправильно: под O(N) я подразумеваю именно число сравнений
                                                                                        А вот Вас бы я попросил «правильно посчитать» число сравнений при сортировке УЖЕ ОТСОРТИРОВАННОГО массива данных

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


                                                                                        Давайте так. Если не хотите выкладывать алгоритм публично, скидывайте мне и нескольким другим заинтересованным исходники в личку. Лично я обещаю никуда его не выкладывать, и после выяснения всех спорных моментов удалить. Вы ведь считаете, что надо друг другу на слово верить, так что это не должно быть проблемой. Мы их проверяем и говорим вам, где и как вы считаете неправильно. Другие заинтересованнные не дадут соврать одному. Также я хочу попробовать заменить ваш алгоритм на быструю сортировку, оставив всё остальное без изменений. Это даст возможность посчитать число сравнений в одинаковых условиях.


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

                                                                                          +1
                                                                                          Мои эмоции существуют только в Вашем воображении. Я уже приводил цитату из описания моего «идеального стиля общения» Вот она:
                                                                                          Я заранее предполагаю, что оппонент адекватен, что он меня уважает, что он предполагает, что и я его уважаю, что все тезисы (мои или его) есть соответствующее IMHO, что это не нужно проговаривать на каждый чих. У меня нет ни времени, ни желания долго «обнюхиваться» при знакомстве, делать реверансы и т.п. И собеседнику моему, я полагаю, тоже время дорого. Так зачем же нам фигнёй заниматься, приплясывать друг перед другом — в тыщу раз эффективнее сразу поверить, что перед тобой нормальный, хороший человек, что с ним можно обмениваться эмоциональными, то бишь максимально информативными сообщениями. Господа, ну ведь это же так просто!
                                                                                          А закомплексованные «оскорбляющиеся» меня вообще не интересуют.

                                                                                          Это не «подгонять к моему значению цифры» — это продемонстрировать, что Ваш код ДЕЙСТВИТЕЛЬНО имеет что-то общее с воронкой!

                                                                                          Господи, «отправляется в результирующий массив» вовсе не означает «копируется»! И я достаточно профессионален как программист, чтобы бежать, как от огня, от таких «исправляльщиков». Я просто НЕ СЧИТАЮ Вас достаточно компетентным, чтобы править мой код. А уж комбинация фраз «надо друг другу на слово верить» и тут же «другие заинтересованные не дадут соврать одному» и вообще смешна. Мне НЕ НУЖНО «уменьшать количество сравнений» — алгоритм работает ИДЕАЛЬНО! Кстати, я уже отправил в личку программу для тестирования одному из вас. Тому, кто не пальцы гнёт, а грамотно работает.

                                                                                          Вот Вам фрагмент МОЕГО кода на тему пристройки элемента. Как тут код выводится-то?.. Так, что ли?
                                                                                          if (CompareElements (Addr, _PAF.ATail) >= 0)
                                                                                          { // текущий элемент не меньше хвоста
                                                                                          (*(TPEl TPD *)_PAF.ATail).ANext = Addr;
                                                                                          _PAF.ATail = Addr; // новый хвост
                                                                                          _PAF.Len += l; // массив стал больше на длину элемента
                                                                                          continue; // идём на чтение очередного элемента
                                                                                          } // конец условия "текущий элемент больше"


                                                                                          А вот на тему слияния:
                                                                                          if (CompareElements (Addr1, Addr2) <= 0)
                                                                                          { // элемент первого массива не больше второго
                                                                                          (*(TPEl TPD *)Addr).ANext = Addr1;
                                                                                          Addr = Addr1; // адрес текущего элемента нового массива
                                                                                          Addr1 = (*(TPEl TPD *)Addr1).ANext;
                                                                                          continue; // отправляем его в сливаемый поток
                                                                                          } // конец условия "первый элемент не больше"

                                                                                          Как видите, никаких add, new или remove — есть один лишь тупой MOV! А в комментариях написано " отправляем его в сливаемый поток".
                                                                                            +2
                                                                                            Мои эмоции существуют только в Вашем воображении. Я уже приводил цитату из описания моего «идеального стиля общения»

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


                                                                                            Это не «подгонять к моему значению цифры» — это продемонстрировать, что Ваш код ДЕЙСТВИТЕЛЬНО имеет что-то общее с воронкой!

                                                                                            Это все верно только при условии, что вы подсчитываете правильно. А это как раз и вызывает вопросы.


                                                                                            Господи, «отправляется в результирующий массив» вовсе не означает «копируется»!

                                                                                            Я и не говорил, что это означает "копируется", это вы начали говорить про копирование. Работа со вспомогательными массивами у меня в счетчиках не учитывается.


                                                                                            А уж комбинация фраз «надо друг другу на слово верить» и тут же «другие заинтересованные не дадут соврать одному» и вообще смешна.

                                                                                            А другие и не считают, что друг другу надо на слово верить. Это только вы так считаете. Это доказательство для других, а не для вас.


                                                                                            Мне НЕ НУЖНО «уменьшать количество сравнений» — алгоритм работает ИДЕАЛЬНО!

                                                                                            Вы читаете вообще, что я пишу? Или просто фразы из контекста вырываете?


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


                                                                                            Тому, кто не пальцы гнёт, а грамотно работает.

                                                                                            Простите, вы называете "гнуть пальцы" объективные результаты работы rpsort, которая использует другой алгоритм сортировки? Про свою крутость здесь говорите только вы.


                                                                                            Вот Вам фрагмент МОЕГО кода на тему пристройки элемента.

                                                                                            У меня для добавления в конец используется вот такой код:


                                                                                            if (str >= voronka[ voronka.length-1 ]) {
                                                                                                // add to end
                                                                                                voronka.push(str);
                                                                                            }

                                                                                            Они логически эквивалентны. И у вас и у меня одно сравнение и одно добавление.


                                                                                            А вот на тему слияния:

                                                                                            У меня для добавления в список при слиянии используется вот такой код:


                                                                                            if (e1 <= e2) {
                                                                                                newList.push(e1);
                                                                                            }

                                                                                            Они тоже логически эквивалентны. И у вас и у меня одно сравнение и одно добавление. Причем у вас там 3 записи значений указателей, в отличие от QuickSort, в которой для помещения указателя на элемент в нужную позицию требуется одна запись.


                                                                                            И так как код эквивалентен, то сравнений (вызовов CompareElements) у вас столько же, сколько у меня. А значит в 10 раз больше, чем в QuickSort.


                                                                                            Как видите, никаких add, new или remove — есть один лишь тупой MOV!

                                                                                            Вот то, что у вас между фигурными скобками, в других языках вынесено в отдельные функции, названия которых часто начинаются с add. Потому что эта операция называется "добавление элемента в структуру данных Linked List".

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

                                                                                              Я?! По копирование?! Где!?! Когда?! В Вашем коде и коде Вашего «напарника» данные именно копируются. Да ещё и всякая возня с new-add-delete. А счётчики Ваши меня не интересуют вообще — уже говорил. Разве чтобы Вы подтвердили, что у Вас действительно воронка запрограммирована, а не какая-нить левая хрень.

                                                                                              Я читаю, читаю, что Вы пишете. Более того: я очень редко читаю невнимательно. ;)

                                                                                              Нет, я называю «гнуть пальцы» — это нести всякую полуграмотную ахинею про «разновидность сортировки вставками» и тому подобную белиберду.

                                                                                              Нет, Ваш код и мой код НЕ «эквивалентны». Ах, «логически»… Логически — да, пожалуй. :) Совершенно верно: у Вас идёт КОПИРОВАНИЕ двух списков в третий, то есть огромные накладные расходы, особенно заметные при слиянии как раз сверхмалых списков, то есть для ситуации, близкой к худшему случаю.

                                                                                              Сударь, НЕ МОЖЕТ «для помещения указателя на элемент в нужную позицию требоваться одна запись»! Нужно поправить адрес следующего элемента в сливаемом списке и перещёлкнуть указатели текущего элемента у него и у того массива, из которого был взят элемент.

                                                                                              Вот именно, что «то у меня между фигурными скобками, в других языках вынесено в отдельные функции», так что один несчастный mov заменяется на call, внутри этого call сидит туева хуча других mov, не говоря уже про более затратные конструкции. Потому что у меня НЕТ никакого «добавления элемента в структуру данных». Всё проще гораздо! ;)
                                                                                                +2
                                                                                                если готов отвечать за свои действия

                                                                                                Вот и отвечайте. Написали мат — получили минус. Что вы жалуетесь-то тогда.


                                                                                                Я?! По копирование?! Где!?! Когда?!

                                                                                                Вот здесь.
                                                                                                "он именно КОПИРУЕТ два сливаемых списка в третий, а исходные уничтожает."


                                                                                                В Вашем коде и коде Вашего «напарника» данные именно копируются. Да ещё и всякая возня с new-add-delete

                                                                                                Это все никак не влияет на вычислительную сложность алгоритма. Ту, про которую вы говорите, что в вашем алгоритме она O(N). new-add-delete на эту N или NlogN или что там будет в скобках никак не влияют. Кокнретно для сортировок обозначение в скобках показывает число сравнений. Это вам понятно или нет? Причем здесь new-add-delete, если они в подсчетах не участвуют?


                                                                                                А счётчики Ваши меня не интересуют вообще — уже говорил.

                                                                                                Счетчики это и есть вычислительная сложность конкретного запуска. Вас сложность вашего алгоритма не интересует? Что ж вы тогда тут спорите. Сойдемся на том, что она хуже, чем у быстрой сортировки, и всё.


                                                                                                Я просто НЕ СЧИТАЮ Вас достаточно компетентным
                                                                                                Тому, кто не пальцы гнёт, а грамотно работает.
                                                                                                это нести всякую полуграмотную ахинею про «разновидность сортировки вставками»

                                                                                                Я ничего не говорил вам про сортировку вставками.


                                                                                                Нет, Ваш код и мой код НЕ «эквивалентны». Ах, «логически»… Логически — да, пожалуй. :) Совершенно верно: у Вас идёт КОПИРОВАНИЕ двух списков в третий, то есть огромные накладные расходы

                                                                                                Ни в quickSort, ни в voronkaSort накладные расходы не учитываются. Накладные расходы влияют на конкретное абсолютное время в миллисекундах одного алгоритма. А мы сравниваем относительное число операций сравнения в двух алгоритмах. Даже если накладные расходы сделать ноль в обоих алгоритмах, QuickSort будет работать быстрее. Что вам здесь непонятно?


                                                                                                Сударь, НЕ МОЖЕТ «для помещения указателя на элемент в нужную позицию требоваться одна запись»! Нужно поправить адрес следующего элемента в сливаемом списке и перещёлкнуть указатели текущего элемента у него и у того массива, из которого был взят элемент.

                                                                                                Это в вашей структуре данных "связный список" надо все это перещелкивать. А QuickSort меняет исходный плоский непрерывный массив. Я же вам приводил код на Си с qsort, нету там никаких перещелкиваний.


                                                                                                mov заменяется на call, внутри этого call сидит туева хуча других mov, не говоря уже про более затратные конструкции

                                                                                                Да, только на число сравнений элементов это все равно не влияет. А в QuickSort никаких связных списков нет, и то что у вас между фигурными скобками там вообще не используется.

                                                                                                  0
                                                                                                  :lol: Ну Вы прелесть! Да, я написал «он именно КОПИРУЕТ два сливаемых списка в третий, а исходные уничтожает.» Но непосредственно перед этим я написал: «Приведённый код слияния списков (что у Вас, что у второго автора) есть полное дерьмо» — и далее по тексту. Так это я ПРО ВАШ код писал! ;)

                                                                                                  Не-а, не сойдёмся! Сложность лучшего случая для воронки, очевидно, O(n). Для худшего, очевидно, O(n log n), среднего, очевидно, что-то между ними. Сложность Квика подробно расписана в Википедии и она составляет, соответственно, O(n log n), O(n^2) и O(n log n). Какие именно цифири Вы намерены поправить своими счётчиками?

                                                                                                  Да, Вы ничего не говорили мне про сортировку вставками. Я просто НЕ СЧИТАЮ Вас достаточно компетентным.

                                                                                                  Я же вам приводил код на Си с qsort, нету там никаких перещелкиваний.
                                                                                                  Там и слияний никаких нет! И вообще один голый вызов: qsort(input, stringLen, sizeof(char *), myCompare);

                                                                                                  Кстати, а что она вообще делает? Элементы переставляет? В QuickSort никаких связных списков нет? А есть-то что? Что там Вики говорит про «перемещение элементов»? А что за swap там на каждом углу? Что вообще может быть ЛУЧШЕ списка? Тем более, при работе с элементами переменной длины? 60 лет на свете живу, но ничего лучшего не знаю! :)
                                                                                                    0
                                                                                                    Сложность лучшего случая для воронки, очевидно, O(n)

                                                                                                    И всё, слово "очевидно" это все ваши доказательства? Я так тоже могу: "сложность лучшего случая для воронки, очевидно, O(n^2)". Раз вы считаете это достаточным доказательством, значит там и есть O(n^2).


                                                                                                    Ну где там O(N), покажите. Вот у меня есть код, полностью соответствующий вашему описанию, потому что несоответствие описанию вы так и не показали. Сравнений там очевидно больше, чем O(N), всё посчитано. И программа ваша медленнее работает, чем другие. Это факты. Поэтому это не очевидно.


                                                                                                    В QuickSort никаких связных списков нет?

                                                                                                    А, так вы вообще не знаете, как она работает. Пфф, о чем тогда можно говорить. Так вот, сообщаю вам как тот кто прочитал оба описания, что там алгоритм эффективнее вашего. Если у вас сравнений получается меньше, значит вы подсчитываете неправильно.

                                                                                                      0
                                                                                                      А какие могут быть доказательства? При отсортированном входном потоке очередной элемент пристраивается в первый (и единственный) массив воронки за одно сравнение. Первый элемент — вообще без сравнений. Список один, сливать ничего не требуется, сортировка завершена. Вы вообще заметку-то читали? А вот если у Вас число сравнений НЕ равно n-1, значит, это никакая не «воронка».

                                                                                                      Понятия не имею! Там написано, что она работает за квадрат в худшем случае — мне этого достаточно, чтобы не читать. Там написано про перемещения элементов — мне этого тоже достаточно. Но Вы так и не ответили на вопрос: что может быть быстрее и удобнее списка? И переставляет ли Квик элементы?
                                                                                                        +1
                                                                                                        Сложность лучшего случая для воронки, очевидно, O(n)
                                                                                                        При отсортированном входном потоке

                                                                                                        А, ну так для QuickSort проверка "отсортирован ли массив" тоже делается за O(N), как и для любой другой сортировки.


                                                                                                        А вот если у Вас число сравнений НЕ равно n-1, значит, это никакая не «воронка»

                                                                                                        Вот взяли бы и проверили, код вам предоставлен. Нажать F12 в браузере это так сложно? Проверить можно было бы быстрее, чем вы этот коммент писали.


                                                                                                        Именно в этом коде на 1000 элементов получается 1996 — 1998 сравнений, потому что сначала сравнивается с головой воронки, а не с хвостом, в полном соответствии с вашим описанием в статье. Если исправить, получается 999.


                                                                                                        voronkaSort
                                                                                                        208 ms / 1000 elements
                                                                                                        Object { read: 2996, add: 1000, compare: 1996 }

                                                                                                        Так что, идем дальше, или опять будете искать поводы увильнуть?


                                                                                                        Но Вы так и не ответили на вопрос: что может быть быстрее и удобнее списка? И переставляет ли Квик элементы?

                                                                                                        Читайте описание, смотрите код реализаций. Вы же программист.

                                                                                                          –1
                                                                                                          Да накойхер мне ВАШ код проверять? Тем более, что JS В ПРИНЦИПЕ непригоден для создания продукта! Мой код проверен и прекрасно протестирован два месяца назад — для того я и завёл вообще счётчик сравнений, и он тут же на массиве из 1000 значений показал свои 999. Но линейность лучшего случая и без кода должна быть очевидна любому дебилу. И никаких «тоже»! Не знаю, может «для QuickSort проверка „отсортирован ли массив“ и делается за O(N)», но моему сортиру ПО БАРАБАНУ, что там на входе! Он просто читает и сортирует, читает м сортирует. Когда все данные считаны — массив отсортирован. Ну или, в крайнем случае, нужно слить ещё не более 1024 списков буфера.

                                                                                                          Ну, слава те, Господи! У меня всегда сравнивался сначала с хвостом, но это не имеет значения — значит, массив, отсортированный В ОБРАТНОМ ПОРЯДКЕ отсортируется за те самые 999. В любом случае, сложность линейная, что и написано в самых первых строчках описания алгоритма.

                                                                                                          Да я-то программист, в отличие от Вас. Но за слова свои отвечаем или «как всегда»?
                                                                                                            +2

                                                                                                            Ладно, хотели на C++, вот вам на C++.


                                                                                                            Код


                                                                                                            Результаты:


                                                                                                            voronkaSort
                                                                                                            correct sorting
                                                                                                            207 ms / 10000 elements
                                                                                                            CompareElements() calls: 5961724
                                                                                                            
                                                                                                            quickSort
                                                                                                            correct sorting
                                                                                                            8 ms / 10000 elements
                                                                                                            CompareElements() calls: 194037

                                                                                                            Разговор окончен.


                                                                                                            Код на C++
                                                                                                            #include <stdio.h>
                                                                                                            #include <time.h>
                                                                                                            #include <stdlib.h>
                                                                                                            #include <string.h>
                                                                                                            #include <sys/time.h>
                                                                                                            
                                                                                                            struct DataWrapper
                                                                                                            {
                                                                                                                char* pRawData;
                                                                                                                int len;
                                                                                                            
                                                                                                                DataWrapper(char* pRawData, int len)
                                                                                                                {
                                                                                                                    this->pRawData = pRawData;
                                                                                                                    this->len = len;
                                                                                                                }
                                                                                                            };
                                                                                                            
                                                                                                            struct Element
                                                                                                            {
                                                                                                                DataWrapper* data;
                                                                                                                Element* next;
                                                                                                            
                                                                                                                Element()
                                                                                                                {
                                                                                                                    this->data = NULL;
                                                                                                                    this->next = NULL;
                                                                                                                }
                                                                                                            };
                                                                                                            
                                                                                                            struct LinkedList
                                                                                                            {
                                                                                                                Element* head;
                                                                                                                Element* tail;
                                                                                                                int len;
                                                                                                            
                                                                                                                LinkedList()
                                                                                                                {
                                                                                                                    this->head = NULL;
                                                                                                                    this->tail = NULL;
                                                                                                                    this->len = 0;
                                                                                                                }
                                                                                                            
                                                                                                                void addToHead(Element* element)
                                                                                                                {
                                                                                                                    if (this->len == 0) {
                                                                                                                        element->next = NULL;
                                                                                                                        this->head = element;
                                                                                                                        this->tail = element;
                                                                                                                        this->len++;
                                                                                                                        return;
                                                                                                                    }
                                                                                                            
                                                                                                                    element->next = this->head;
                                                                                                                    this->head = element;
                                                                                                                    this->len++;
                                                                                                                }
                                                                                                            
                                                                                                                void addToTail(Element* element)
                                                                                                                {
                                                                                                                    element->next = NULL;
                                                                                                            
                                                                                                                    if (this->len == 0) {
                                                                                                                        this->head = element;
                                                                                                                        this->tail = element;
                                                                                                                        this->len++;
                                                                                                                        return;
                                                                                                                    }
                                                                                                            
                                                                                                                    this->tail->next = element;
                                                                                                                    this->tail = element;
                                                                                                                    this->len++;
                                                                                                                }
                                                                                                            };
                                                                                                            
                                                                                                            int COMPARE_ELEMENTS_COUNT = 0;
                                                                                                            
                                                                                                            int CompareElements(Element* e1, Element* e2)
                                                                                                            {
                                                                                                                COMPARE_ELEMENTS_COUNT++;
                                                                                                            
                                                                                                                int res = memcmp(e1->data->pRawData, e2->data->pRawData, (e1->data->len < e2->data->len ? e1->data->len : e2->data->len));
                                                                                                                if (res == 0) {
                                                                                                                    return (e1->data->len - e2->data->len);
                                                                                                                }
                                                                                                                return res;
                                                                                                            }
                                                                                                            
                                                                                                            void performMerge(LinkedList** buffer, int toIndex, int fromIndex)
                                                                                                            {
                                                                                                                Element* e1 = buffer[toIndex]->head;
                                                                                                                Element* e2 = buffer[fromIndex]->head;
                                                                                                                Element* prev = NULL;
                                                                                                                Element* tmp = NULL;
                                                                                                            
                                                                                                                // [3, 4], [2, 9]
                                                                                                                if (e1 != NULL && e2 != NULL) {
                                                                                                                    if (CompareElements(e1, e2) > 0) {
                                                                                                                        buffer[toIndex]->head = e2;
                                                                                                            
                                                                                                                        tmp = e2->next;
                                                                                                            
                                                                                                                        e2->next = e1;
                                                                                                                        buffer[toIndex]->len++;
                                                                                                            
                                                                                                                        prev = e2;
                                                                                                                        e2 = tmp;
                                                                                                                    } else {
                                                                                                                        prev = e1;
                                                                                                                        e1 = e1->next;
                                                                                                                    }
                                                                                                                }
                                                                                                            
                                                                                                                while (e1 != NULL && e2 != NULL) {
                                                                                                                    if (CompareElements(e1, e2) >= 0) {
                                                                                                                        tmp = e2->next;
                                                                                                            
                                                                                                                        prev->next = e2;
                                                                                                                        e2->next = e1;
                                                                                                                        buffer[toIndex]->len++;
                                                                                                            
                                                                                                                        prev = e2;
                                                                                                                        e2 = tmp;
                                                                                                                    } else {
                                                                                                                        prev = e1;
                                                                                                                        e1 = e1->next;
                                                                                                                    }
                                                                                                                }
                                                                                                            
                                                                                                                while (e2 != NULL) {
                                                                                                                    tmp = e2->next;
                                                                                                                    buffer[toIndex]->addToTail(e2);
                                                                                                                    e2 = tmp;
                                                                                                                }
                                                                                                            }
                                                                                                            
                                                                                                            static int compareBySizeAsc(const void* a, const void* b)
                                                                                                            {
                                                                                                                return ((*(LinkedList**)a)->len - (*(LinkedList**)b)->len);
                                                                                                            }
                                                                                                            
                                                                                                            void mergeLists(LinkedList** buffer, int &bufferLength)
                                                                                                            {
                                                                                                                int count = bufferLength * 3 / 4;
                                                                                                            
                                                                                                                qsort(buffer, bufferLength, sizeof(LinkedList*), compareBySizeAsc);
                                                                                                            
                                                                                                                int i, j;
                                                                                                                for (i = 1; i <= count; i++) {
                                                                                                                    performMerge(buffer, 0, i);
                                                                                                                }
                                                                                                            
                                                                                                                // i == count + 1
                                                                                                                for (j = i; j < bufferLength; j++) {
                                                                                                                    buffer[j - i + 1] = buffer[j];
                                                                                                                }
                                                                                                            
                                                                                                                bufferLength = bufferLength - i + 1;
                                                                                                            }
                                                                                                            
                                                                                                            LinkedList* voronkaSort(LinkedList* &list)
                                                                                                            {
                                                                                                                const int maxBufferSize = 1024;
                                                                                                            
                                                                                                                LinkedList** buffer = new LinkedList*[maxBufferSize];
                                                                                                                int bufferLength = 0;
                                                                                                            
                                                                                                                LinkedList* voronka = new LinkedList();
                                                                                                                Element* next = NULL;
                                                                                                            
                                                                                                                for (Element* cur = list->head; cur != NULL; cur = next) {
                                                                                                            
                                                                                                                    next = cur->next;
                                                                                                            
                                                                                                                    if (voronka->len == 0) {
                                                                                                                        voronka->addToTail(cur);
                                                                                                                        continue;
                                                                                                                    } else {
                                                                                                                        if (CompareElements(cur, voronka->tail) >= 0) {
                                                                                                                            voronka->addToTail(cur);
                                                                                                                            continue;
                                                                                                                        } else if (CompareElements(cur, voronka->head) <= 0) {
                                                                                                                            voronka->addToHead(cur);
                                                                                                                            continue;
                                                                                                                        }
                                                                                                                    }
                                                                                                            
                                                                                                                    if (bufferLength == maxBufferSize) {
                                                                                                                        mergeLists(buffer, bufferLength);
                                                                                                                    }
                                                                                                            
                                                                                                                    buffer[bufferLength] = voronka;
                                                                                                                    bufferLength++;
                                                                                                            
                                                                                                                    voronka = new LinkedList();
                                                                                                                    voronka->addToTail(cur);
                                                                                                                }
                                                                                                            
                                                                                                                if (bufferLength == maxBufferSize) {
                                                                                                                    mergeLists(buffer, bufferLength);
                                                                                                                }
                                                                                                            
                                                                                                                if (voronka->len > 0) {
                                                                                                                    buffer[bufferLength] = voronka;
                                                                                                                    bufferLength++;
                                                                                                                }
                                                                                                            
                                                                                                                for (int i = 1; i < bufferLength; i++) {
                                                                                                                    performMerge(buffer, 0, i);
                                                                                                                }
                                                                                                            
                                                                                                                list = buffer[0];
                                                                                                                delete []buffer;
                                                                                                            }
                                                                                                            
                                                                                                            void quickSort(char** arr, int start, int end)
                                                                                                            {
                                                                                                                int mid = (start + end) / 2;
                                                                                                            
                                                                                                                char* midValue = arr[mid];
                                                                                                            
                                                                                                                DataWrapper data(midValue, strlen(midValue));
                                                                                                                Element midValueElement;
                                                                                                                midValueElement.data = &data;
                                                                                                                midValueElement.next = NULL;
                                                                                                            
                                                                                                                Element arrElement;
                                                                                                                DataWrapper arrData(NULL, 0);
                                                                                                                arrElement.data = &arrData;
                                                                                                                arrElement.next = NULL;
                                                                                                            
                                                                                                                int i = start, j = end;
                                                                                                                int p;
                                                                                                            
                                                                                                                while (i <= j) {
                                                                                                            
                                                                                                                    arrData.pRawData = arr[i];
                                                                                                                    arrData.len = strlen(arr[i]);
                                                                                                            
                                                                                                                    while (CompareElements(&arrElement, &midValueElement) < 0) {
                                                                                                                        i++;
                                                                                                            
                                                                                                                        arrData.pRawData = arr[i];
                                                                                                                        arrData.len = strlen(arr[i]);
                                                                                                                    }
                                                                                                            
                                                                                                                    arrData.pRawData = arr[j];
                                                                                                                    arrData.len = strlen(arr[j]);
                                                                                                            
                                                                                                                    while (CompareElements(&arrElement, &midValueElement) > 0) {
                                                                                                                        j--;
                                                                                                            
                                                                                                                        arrData.pRawData = arr[j];
                                                                                                                        arrData.len = strlen(arr[j]);
                                                                                                                    }
                                                                                                            
                                                                                                                    if (i <= j) {
                                                                                                                        char* tmp = arr[i];
                                                                                                                        arr[i] = arr[j];
                                                                                                                        arr[j] = tmp;
                                                                                                            
                                                                                                                        i++;
                                                                                                                        j--;
                                                                                                                    }
                                                                                                                }
                                                                                                                p = i;
                                                                                                            
                                                                                                                if (start < p - 1) {
                                                                                                                    quickSort(arr, start, p - 1);
                                                                                                                }
                                                                                                                if (p < end) {
                                                                                                                    quickSort(arr, p, end);
                                                                                                                }
                                                                                                            }
                                                                                                            
                                                                                                            static int compareStrings(const void* a, const void* b)
                                                                                                            {
                                                                                                                return strcmp(*(const char**)a, *(const char**)b);
                                                                                                            }
                                                                                                            
                                                                                                            int getTime()
                                                                                                            {
                                                                                                                struct timeval tp;
                                                                                                                gettimeofday(&tp, NULL);
                                                                                                                long int ms = tp.tv_sec * 1000 + tp.tv_usec / 1000;
                                                                                                            
                                                                                                                return ms;
                                                                                                            }
                                                                                                            
                                                                                                            int main()
                                                                                                            {
                                                                                                                const int N = 10000;
                                                                                                            
                                                                                                                char** strings = new char*[N];
                                                                                                                const char* symbols = "0123456789abcdefghijklmnopqrstuvwxyz";
                                                                                                            
                                                                                                                srand(time(NULL));
                                                                                                            
                                                                                                                int i, j;
                                                                                                                const int maxStringLen = 20;
                                                                                                                for (i = 0; i < N; i++) {
                                                                                                                    int sLen = (rand() % maxStringLen) + 1;
                                                                                                            
                                                                                                                    strings[i] = new char[sLen + 1];
                                                                                                                    strings[i][sLen] = '\0';
                                                                                                            
                                                                                                                    for (j = 0; j < sLen; j++) {
                                                                                                                        strings[i][j] = symbols[rand() % 36];
                                                                                                                    }
                                                                                                                }
                                                                                                            
                                                                                                                char** systemSortedStrings = new char*[N];
                                                                                                                for (i = 0; i < N; i++) {
                                                                                                                    systemSortedStrings[i] = strings[i];
                                                                                                                }
                                                                                                                qsort(systemSortedStrings, N, sizeof(const char*), compareStrings);
                                                                                                            
                                                                                                                int t1, t2;
                                                                                                            
                                                                                                                // voronkaSort
                                                                                                            
                                                                                                                LinkedList* list = new LinkedList();
                                                                                                                for (i = 0; i < N; i++) {
                                                                                                                    DataWrapper* data = new DataWrapper(strings[i], strlen(strings[i]));
                                                                                                            
                                                                                                                    Element* element = new Element();
                                                                                                                    element->data = data;
                                                                                                            
                                                                                                                    list->addToTail(element);
                                                                                                                }
                                                                                                            
                                                                                                                COMPARE_ELEMENTS_COUNT = 0;
                                                                                                                t1 = getTime();
                                                                                                                voronkaSort(list);
                                                                                                                t2 = getTime();
                                                                                                            
                                                                                                                char** voronkaSortedStrings = new char*[N];
                                                                                                                int n = 0;
                                                                                                                for (Element* cur = list->head; cur != NULL; cur = cur->next) {
                                                                                                                    voronkaSortedStrings[n] = cur->data->pRawData;
                                                                                                                    n++;
                                                                                                                }
                                                                                                            
                                                                                                                printf("voronkaSort\n");
                                                                                                                for (i = 0; i < N; i++) {
                                                                                                                    if (strcmp(voronkaSortedStrings[i], systemSortedStrings[i]) != 0) {
                                                                                                                        printf("ERROR: incorrect sorting\n");
                                                                                                                        break;
                                                                                                                    }
                                                                                                                }
                                                                                                                if (i == N) {
                                                                                                                    printf("correct sorting\n");
                                                                                                                }
                                                                                                                printf("%d ms / %d elements\n", t2 - t1, N);
                                                                                                                printf("CompareElements() calls: %d\n", COMPARE_ELEMENTS_COUNT);
                                                                                                            
                                                                                                                // quickSort
                                                                                                            
                                                                                                                char** quickSortSortedStrings = new char*[N];
                                                                                                                for (i = 0; i < N; i++) {
                                                                                                                    quickSortSortedStrings[i] = strings[i];
                                                                                                                }
                                                                                                            
                                                                                                                COMPARE_ELEMENTS_COUNT = 0;
                                                                                                                t1 = getTime();
                                                                                                                quickSort(quickSortSortedStrings, 0, N - 1);
                                                                                                                t2 = getTime();
                                                                                                            
                                                                                                                printf("\n");
                                                                                                            
                                                                                                                printf("quickSort\n");
                                                                                                                for (i = 0; i < N; i++) {
                                                                                                                    if (strcmp(quickSortSortedStrings[i], systemSortedStrings[i]) != 0) {
                                                                                                                        printf("ERROR: incorrect sorting\n");
                                                                                                                        break;
                                                                                                                    }
                                                                                                                }
                                                                                                                if (i == N) {
                                                                                                                    printf("correct sorting\n");
                                                                                                                }
                                                                                                                printf("%d ms / %d elements\n", t2 - t1, N);
                                                                                                                printf("CompareElements() calls: %d\n", COMPARE_ELEMENTS_COUNT);
                                                                                                            
                                                                                                                return 0;
                                                                                                            }
                                                                                                              –4
                                                                                                              Я?! Хотел?! Код?! От Вас?! Я хотел, чтобы Вы отвечали за свои слова, и привели, как там Квик управляется одним указателем без перестановки элементов. Мне вот кажется, что это есть Бред Сивой КОбылы.

                                                                                                              Разговор окончен.
                                                                                                              Вот за это спасибо! :)
                                                                                                                +1
                                                                                                                и привели, как там Квик управляется одним указателем без перестановки элементов

                                                                                                                Не очень хорошо нарушать свои озвученные намерения, но вы такие перлы выдаете, что их сложно оставить без ответа. В каком, простите, виде вам надо привести? В виде кода на языке, которые вы понимаете? Так я и привел уже, в приведенном коде на C++ есть функция quickSort, никаких танцев с бубном наподобие "поправить адрес следующего элемента в сливаемом списке и перещёлкнуть указатели текущего элемента у него и у того массива, из которого был взят элемент" там нет. Сортируются обычные указатели на строки. C++ для вас достаточно понятен, или может на ассемблере написать?

                                                                                                                  0
                                                                                                                  Ну и как, долго Вы «разговор оканчивать будете»? :)

                                                                                                                  Что?! В Вашем коде?! Первое же, что я сделал — это вышвырнул оттуда нафиг qsort! Впрочем, вот Вам полный «отчёт о проделанной работе»:

                                                                                                                  Ладно, глянем на код — так уж и быть. Не зря же человек трудился! :)

                                                                                                                  Строки, разумеется, не читаются, а инициализируются. Массив, разумеется, в сраных 10 000 строк. Максимальная длина строки, разумеется, сраных 20 символов. Строки, разумеется, оканчиваются нулевым байтом.

                                                                                                                  Так, все эти quickSort, да printf — поганой метлой, чтоб не путались под ногами.

                                                                                                                  И чо у нас за LinkedList?.. ну, чо-то там обнуляется — допустим. Похоже на мой ArrayPSP. А DataWrapper что за зверь? А здесь какая-то ссылка на какую-то pRawData. Насколько я понимаю, у меня такого вообще нет. Равно как и Element. В любом случае, идёт какая-то инициализация чего-то там. ЧАВО?! addToTail?! А это-то с какого бодуна? Ладно, автору виднее… :) О! Добрались до voronkaSort, наконец!

                                                                                                                  Блин, опять чего-то там заказывается, да инициализируется… О! Element* cur появился! То есть СНАЧАЛА мы организовали данные в виде списка, и лишь ПОТОМ стали чего-то сортировать. Нормальная воронка к этому времени сортировку уже практически закончила. :)

                                                                                                                  Господи, опять addToTail! При чём тут ваще Tail? Ха-ха-ха! А там втихаря, оказывается, if (this->len == 0) this->head = element! Ну ладно, пущай будет Tail… :)

                                                                                                                  Не понял! Как это if (bufferLength == maxBufferSize) mergeLists(buffer, bufferLength)?! А остальные списки кто сливать будет? Пушкин? Ладно, в цикле сойдёт — вдруг правильно? ОЙ! Опять voronka = new LinkedList()?! Да скоко ж можно?

                                                                                                                  Во, блин! Одного mergeLists мало? Ещё и performMerge? Ну. и чем же они отличаются? ЧАВО???!!! В mergeLists сидит qsort?! А в глаз? :) И потом: а накойхер нужен это compareBySizeAsc? Размеры же списков меняются ДИНАМИЧЕСКИ!

                                                                                                                  Ага, и performMerge отседова вызывается. Ну, тогда ещё ладно… ОЙ, МАМА!!! ЭТО ВОТ ЭТО ВОТ называется «слияние списков»?!
                                                                                                                  for (i = 1; i <= count; i++) performMerge(buffer, 0, i);

                                                                                                                  ВОТ ЭТО ВОТ?! ПЦ! Браво, господин «программист»! ТАКОГО я даже от Вас не ожидал! Так с какого хрена Вы говорите, что это МОЯ воронка даёт больше сравнений? Это ВОТ ЭТА ВОТ ВАША БРЕДЯТИНА их даёт! Здесь действительно КВАДРАТ получается!

                                                                                                                  Всё, я издох — на performMerge у меня уже сил нет. Там наверняка копирование, но это уже не имеет никакого значение. Кто там предлагал мне код-то отдать «на проверку»? Не автор ли сего произведения? Программисты, бля!(с)
                                                                                                                    +4

                                                                                                                    То есть вы не можете сказать, чем отличается код на C++ от описания в статье. Ну, этого следовало ожидать. Хотя я предполагал, что вы все-таки ответите за свои слова, раз от других требуете.


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


                                                                                                                    Что?! В Вашем коде?! Первое же, что я сделал — это вышвырнул оттуда нафиг qsort!

                                                                                                                    Зачем вы тогда просите, чтобы вам что-то привели, если потом выкидываете?


                                                                                                                    В mergeLists сидит qsort?!

                                                                                                                    У вас вообще пузырек:
                                                                                                                    "Только у воронки пузырёк включается на последних 256 элементах (ну или на всех файлах) и сортирует готовые списки по их суммарному размеру."


                                                                                                                    То есть СНАЧАЛА мы организовали данные в виде списка, и лишь ПОТОМ стали чего-то сортировать.
                                                                                                                    Опять voronka = new LinkedList()?!
                                                                                                                    ...

                                                                                                                    Это всё на количество сравнений никак не влияет. А оно в вашем алгоритме больше, чем в том, который вы выкинули. У вас какая-то странная манера прятать голову в песок "не буду запускать quickSort, вдруг там правда меньше сравнений". Либо предлагаете изменение в коде voronkaSort, которое его уменьшит, либо считаем, что никакого "Минимальная трудоемкость худшего случая… блин, ДА, ЛИНЕЙНАЯ!" и "средняя сложность уж извините стремится к O(n)" у вас нет.

                                                                                                                      –2
                                                                                                                      Сударь, попрощались ведь уже! И сказал я Вамс всё — Вы АБСОЛЮТНО НИЧЕГО не понимаете в алгоритме! И не в воронке, а в слиянии — алгоритме, написанном чуть ли не сто лет назад. Воронка всего лишь готовит отсортированные массивы для слияния. А Ваш опус
                                                                                                                      for (i = 1; i <= count; i++) performMerge(buffer, 0, i);
                                                                                                                      это просто КЛИНИЧЕСКИЙ бред!
                                                                                                                        +1

                                                                                                                        Попрощались. Но я по наивности считал, что уж в коде на C++-то вы сможете разобраться, и либо скажете, где несоответствие описанию, и я признаю что я не прав, либо признаете что неправы вы, и быстрая сортировка работает быстрее.


                                                                                                                        Этот бред написан у вас в статье.
                                                                                                                        "Алгоритм слияния упорядоченных массивов хорошо известен… Когда один из подмассивов закончился, оставшиеся элементы второго подмассива добавляются в результирующий массив."
                                                                                                                        "при переполнении которого сливаются сразу три четверти самых маленьких списков этого буфера (до 256)"


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

                                                                                                                          –2
                                                                                                                          Этого бреда у меня НЕ МОЖЕТ быть написано в статье! У меня сливаются САМЫЕ МЕЛКИЕ массивы, а Вы херачите все в нулевой! Ещё на Фейсбуке я писал, что это квадрат. И здесь пару раз упоминал, что при большом умении можно доиграться до квадрата. Поздравляю, господин «программист»: Вы именно до него и доигрались!
                                                                                                                            0
                                                                                                                            Этого бреда у меня НЕ МОЖЕТ быть написано в статье!

                                                                                                                            Вы отрицаете, что то что в кавычках это цитаты вашего текста? Ну поиском по странице поищите.


                                                                                                                            У меня сливаются САМЫЕ МЕЛКИЕ массивы, а Вы херачите все в нулевой!

                                                                                                                            Вот тот самый "В mergeLists сидит qsort" и сортирует массивы по размеру, после сортировки нулевой всегда самый маленький, первые три четверти это и есть самые мелкие массивы.


                                                                                                                            Исправьте voronkaSort в этом онлайн-редакторе как вам надо, запустите и проверьте. Можете даже код сюда не показывать. Просто quickSort верните обратно и сравните значения "CompareElements() calls" для набора случайных строк в обоих алгоритмах.

                                                                                                                              +1
                                                                                                                              А после ПЕРВОГО ЖЕ СЛИЯНИЯ он тоже «самый маленький»? ;) Я же говор: Вы АБСОЛЮТНО НИЧЕГО не понимаете в процедуре слияния!
                                                                                                                                0
                                                                                                                                После ПЕРВОГО ЖЕ СЛИЯНИЯ при следующем вызове mergeLists массив buffer снова сортируется по возрастанию длин. И снова первые три четверти становятся самыми маленькими массивами. И нулевой элемент этого массива снова получается «самый маленький». Прочитайте код уже. И нет, на количество вызовов CompareElements() это не влияет, потому что при этой сортировке она не вызывается.
                                                                                                                                  0
                                                                                                                                  Сударь, Вы ХОТЯ БЫ В ПРОГРАММИРОВАНИИ ХОТЬ ЧТО-НИБУДЬ — понимаете? Какой, в жопу, «следующий вызов mergeLists», когда Вы В ЭТОМ САМОМ ВЫЗОВЕ сливаете в нулевой массив туеву хучу других? Прочитайте код уже! СВОЙ код, блин! Не «следующий вызов mergeLists», а следующий вызов этого… как его… performMerge!
                                                                                                                                    0
                                                                                                                                    Не «следующий вызов mergeLists», а следующий вызов этого… как его… performMerge!

                                                                                                                                    Давайте вы не будете мне приписывать ваши фантазии. Если я сказал "следующий вызов mergeLists", значит это "следующий вызов mergeLists".


                                                                                                                                    Вот цитата из вашего описания:
                                                                                                                                    "А вот размер буфера отсортированных списков до слияния, напротив, был выбран достаточно большим (1024 списка), при переполнении которого сливаются сразу три четверти самых маленьких списков этого буфера (до 256).


                                                                                                                                    Вот из выделенных слов и составлено название функции. Вы утверждаете, что переполнение и необходимость слияния происходит всегда один раз при любом количестве строк? Нет? Значит их больше одного, и там есть "следующий вызов mergeLists".

                                                                                                                                      +1
                                                                                                                                      Именно! САМЫХ МАЛЕНЬКИХ! А кто Вам сказал, что нулевой массив УЖЕ ПОСЛЕ ПЕРВОГО СЛИЯНИЯ будет самым маленьким? Я уже утомился повторять: Вы АБСОЛЮТНО НИЧЕГО не понимаете в механизме слияния списков!
                                                                                                                                        0
                                                                                                                                        Иллюстрация для особо одарённых: предположим, мы имеем по ДВА элемента в каждом списке (худший случай из всех возможных). При ПЕРВОМ вызове Вы действительно сливаете два самых маленьких (2 + 2), но уже при втором Вы сливаете САМЫЙ БОЛЬШОЙ с оставшимся самым маленьким (4+2). Далее идёт 6+2, 8+2 и т.д… То есть Вы ОДИН раз сливаете два самых маленьких списка, а остальные 767 раз Вы сливаете САМЫЙ БОЛЬШОЙ с ними! Господи, Вы программист или где?
                                                                                                                                          +1
                                                                                                                                          Я проверил изменения, которые предложил автор. Действительно, порядок слияния маленьких массивов имеет значение. Я считал, что это неважно. Конечно, никакого O(N) для среднего и худшего случая там нет, но результаты действительно чуть лучше быстрой сортировки.

                                                                                                                                          voronkaSort
                                                                                                                                          correct sorting
                                                                                                                                          12 ms / 10000 elements
                                                                                                                                          CompareElements() calls: 176652
                                                                                                                                          
                                                                                                                                          quickSort
                                                                                                                                          correct sorting
                                                                                                                                          6 ms / 10000 elements
                                                                                                                                          CompareElements() calls: 178747
                                                                                                                                          


                                                                                                                                          Для 10000 элементов иногда у быстрой сортировки меньше сравнений. При увеличении количества практически всегда на 10-30% больше.

                                                                                                                                          Я согласен, что изначально я неоптимально реализовал сортировку воронкой. Можно считать, что в данном случае я был не прав. Тем не менее, O(N) остается недоказанным, пока автор не предоставит соответствующий код. Естественно, кроме случая отсортированного массива, проверка которого занимает O(N) в любых сортировках. Насколько я могу судить, в алгоритме автора сложность чуть ближе к O(Nlog2N), чем у быстрой сортировки, а также требуется дополнительная память для организации связного списка.

                                                                                                                                          Код онлайн

                                                                                                                                          Код на C++
                                                                                                                                          #include <stdio.h>
                                                                                                                                          #include <time.h>
                                                                                                                                          #include <stdlib.h>
                                                                                                                                          #include <string.h>
                                                                                                                                          #include <sys/time.h>
                                                                                                                                          
                                                                                                                                          struct DataWrapper
                                                                                                                                          {
                                                                                                                                              char* pRawData;
                                                                                                                                              int len;
                                                                                                                                          
                                                                                                                                              DataWrapper(char* pRawData, int len)
                                                                                                                                              {
                                                                                                                                                  this->pRawData = pRawData;
                                                                                                                                                  this->len = len;
                                                                                                                                              }
                                                                                                                                          };
                                                                                                                                          
                                                                                                                                          struct Element
                                                                                                                                          {
                                                                                                                                              DataWrapper* data;
                                                                                                                                              Element* next;
                                                                                                                                          
                                                                                                                                              Element()
                                                                                                                                              {
                                                                                                                                                  this->data = NULL;
                                                                                                                                                  this->next = NULL;
                                                                                                                                              }
                                                                                                                                          };
                                                                                                                                          
                                                                                                                                          struct LinkedList
                                                                                                                                          {
                                                                                                                                              Element* head;
                                                                                                                                              Element* tail;
                                                                                                                                              int len;
                                                                                                                                          
                                                                                                                                              LinkedList()
                                                                                                                                              {
                                                                                                                                                  this->head = NULL;
                                                                                                                                                  this->tail = NULL;
                                                                                                                                                  this->len = 0;
                                                                                                                                              }
                                                                                                                                          
                                                                                                                                              void addToHead(Element* element)
                                                                                                                                              {
                                                                                                                                                  if (this->len == 0) {
                                                                                                                                                      element->next = NULL;
                                                                                                                                                      this->head = element;
                                                                                                                                                      this->tail = element;
                                                                                                                                                      this->len++;
                                                                                                                                                      return;
                                                                                                                                                  }
                                                                                                                                          
                                                                                                                                                  element->next = this->head;
                                                                                                                                                  this->head = element;
                                                                                                                                                  this->len++;
                                                                                                                                              }
                                                                                                                                          
                                                                                                                                              void addToTail(Element* element)
                                                                                                                                              {
                                                                                                                                                  element->next = NULL;
                                                                                                                                          
                                                                                                                                                  if (this->len == 0) {
                                                                                                                                                      this->head = element;
                                                                                                                                                      this->tail = element;
                                                                                                                                                      this->len++;
                                                                                                                                                      return;
                                                                                                                                                  }
                                                                                                                                          
                                                                                                                                                  this->tail->next = element;
                                                                                                                                                  this->tail = element;
                                                                                                                                                  this->len++;
                                                                                                                                              }
                                                                                                                                          };
                                                                                                                                          
                                                                                                                                          
                                                                                                                                          
                                                                                                                                          
                                                                                                                                          int COMPARE_ELEMENTS_COUNT = 0;
                                                                                                                                          
                                                                                                                                          int CompareElements(Element* e1, Element* e2)
                                                                                                                                          {
                                                                                                                                              COMPARE_ELEMENTS_COUNT++;
                                                                                                                                          
                                                                                                                                              int res = memcmp(e1->data->pRawData, e2->data->pRawData, (e1->data->len < e2->data->len ? e1->data->len : e2->data->len));
                                                                                                                                              if (res == 0) {
                                                                                                                                                  return (e1->data->len - e2->data->len);
                                                                                                                                              }
                                                                                                                                              return res;
                                                                                                                                          }
                                                                                                                                          
                                                                                                                                          void performMerge(LinkedList** buffer, int toIndex, int fromIndex)
                                                                                                                                          {
                                                                                                                                              Element* e1 = buffer[toIndex]->head;
                                                                                                                                              Element* e2 = buffer[fromIndex]->head;
                                                                                                                                              Element* tmp = NULL;
                                                                                                                                          
                                                                                                                                              int firstAdd = 1;
                                                                                                                                              while (e1 != NULL && e2 != NULL) {
                                                                                                                                                  if (CompareElements(e1, e2) <= 0) {
                                                                                                                                                      tmp = e1;
                                                                                                                                                      e1 = e1->next;
                                                                                                                                                  } else {
                                                                                                                                                      tmp = e2;
                                                                                                                                                      e2 = e2->next;
                                                                                                                                                  }
                                                                                                                                          
                                                                                                                                                  if (firstAdd) {
                                                                                                                                                      buffer[toIndex]->head = tmp;
                                                                                                                                                      buffer[toIndex]->tail = tmp;
                                                                                                                                                      buffer[toIndex]->len = 1;
                                                                                                                                          
                                                                                                                                                      firstAdd = 0;
                                                                                                                                                  } else {
                                                                                                                                                      buffer[toIndex]->tail->next = tmp;
                                                                                                                                                      buffer[toIndex]->tail = tmp;
                                                                                                                                                      buffer[toIndex]->len++;
                                                                                                                                                  }
                                                                                                                                              }
                                                                                                                                          
                                                                                                                                              while (e1 != NULL) {
                                                                                                                                                  tmp = e1->next;
                                                                                                                                                  buffer[toIndex]->addToTail(e1);
                                                                                                                                                  e1 = tmp;
                                                                                                                                              }
                                                                                                                                          
                                                                                                                                              while (e2 != NULL) {
                                                                                                                                                  tmp = e2->next;
                                                                                                                                                  buffer[toIndex]->addToTail(e2);
                                                                                                                                                  e2 = tmp;
                                                                                                                                              }
                                                                                                                                          
                                                                                                                                              buffer[toIndex]->tail->next = NULL;
                                                                                                                                          }
                                                                                                                                          
                                                                                                                                          static int compareBySizeAsc(const void* a, const void* b)
                                                                                                                                          {
                                                                                                                                              return ((*(LinkedList**)a)->len - (*(LinkedList**)b)->len);
                                                                                                                                          }
                                                                                                                                          
                                                                                                                                          void mergeLists(LinkedList** buffer, int &bufferLength)
                                                                                                                                          {
                                                                                                                                              int count = bufferLength * 3 / 4;
                                                                                                                                          
                                                                                                                                              qsort(buffer, bufferLength, sizeof(LinkedList*), compareBySizeAsc);
                                                                                                                                          
                                                                                                                                              int i, j;
                                                                                                                                          
                                                                                                                                              int count2 = count / 2;
                                                                                                                                              while (count2 >= 3)  {
                                                                                                                                                  for (int n = 0; n < count2; n++) {
                                                                                                                                                      performMerge(buffer, n, n + count2);
                                                                                                                                                  }
                                                                                                                                          
                                                                                                                                                  count2 /= 2;
                                                                                                                                              }
                                                                                                                                          
                                                                                                                                              performMerge(buffer, 0, 1);
                                                                                                                                              performMerge(buffer, 2, count);
                                                                                                                                              performMerge(buffer, 0, 2);
                                                                                                                                          
                                                                                                                                              i = count + 1;
                                                                                                                                              for (j = i; j < bufferLength; j++) {
                                                                                                                                                  buffer[j - i + 1] = buffer[j];
                                                                                                                                              }
                                                                                                                                          
                                                                                                                                              bufferLength = bufferLength - i + 1;
                                                                                                                                          }
                                                                                                                                          
                                                                                                                                          
                                                                                                                                          LinkedList* voronkaSort(LinkedList* &list)
                                                                                                                                          {
                                                                                                                                              const int maxBufferSize = 1024;
                                                                                                                                          
                                                                                                                                              LinkedList** buffer = new LinkedList*[maxBufferSize];
                                                                                                                                              int bufferLength = 0;
                                                                                                                                          
                                                                                                                                              LinkedList* voronka = new LinkedList();
                                                                                                                                              Element* next = NULL;
                                                                                                                                          
                                                                                                                                              for (Element* cur = list->head; cur != NULL; cur = next) {
                                                                                                                                          
                                                                                                                                                  next = cur->next;
                                                                                                                                          
                                                                                                                                                  if (voronka->len == 0) {
                                                                                                                                                      voronka->addToTail(cur);
                                                                                                                                                      continue;
                                                                                                                                                  } else {
                                                                                                                                                      if (CompareElements(cur, voronka->tail) >= 0) {
                                                                                                                                                          voronka->addToTail(cur);
                                                                                                                                                          continue;
                                                                                                                                                      } else if (CompareElements(cur, voronka->head) <= 0) {
                                                                                                                                                          voronka->addToHead(cur);
                                                                                                                                                          continue;
                                                                                                                                                      }
                                                                                                                                                  }
                                                                                                                                          
                                                                                                                                          
                                                                                                                                                  if (bufferLength == maxBufferSize) {
                                                                                                                                                      mergeLists(buffer, bufferLength);
                                                                                                                                                  }
                                                                                                                                          
                                                                                                                                                  buffer[bufferLength] = voronka;
                                                                                                                                                  bufferLength++;
                                                                                                                                          
                                                                                                                                                  voronka = new LinkedList();
                                                                                                                                                  voronka->addToTail(cur);
                                                                                                                                              }
                                                                                                                                          
                                                                                                                                              if (bufferLength == maxBufferSize) {
                                                                                                                                                  mergeLists(buffer, bufferLength);
                                                                                                                                              }
                                                                                                                                          
                                                                                                                                              if (voronka->len > 0) {
                                                                                                                                                  buffer[bufferLength] = voronka;
                                                                                                                                                  bufferLength++;
                                                                                                                                              }
                                                                                                                                          
                                                                                                                                          
                                                                                                                                          
                                                                                                                                              qsort(buffer, bufferLength, sizeof(LinkedList*), compareBySizeAsc);
                                                                                                                                          
                                                                                                                                              int count2 = bufferLength / 2;
                                                                                                                                              while (count2 >= 1)  {
                                                                                                                                                  for (int n = 0; n < count2; n++) {
                                                                                                                                                      performMerge(buffer, n, n + count2);
                                                                                                                                                  }
                                                                                                                                          
                                                                                                                                                  if (bufferLength % 2 == 1 && bufferLength >= 2) {
                                                                                                                                                      performMerge(buffer, count2 - 1, bufferLength - 1);
                                                                                                                                                  }
                                                                                                                                          
                                                                                                                                                  bufferLength = count2;
                                                                                                                                                  count2 /= 2;
                                                                                                                                              }
                                                                                                                                          
                                                                                                                                              list = buffer[0];
                                                                                                                                              delete []buffer;
                                                                                                                                          }
                                                                                                                                          
                                                                                                                                          
                                                                                                                                          void quickSort(char** arr, int start, int end)
                                                                                                                                          {
                                                                                                                                              int mid = (start + end) / 2;
                                                                                                                                              char* midValue = arr[mid];
                                                                                                                                              char* tmp = NULL;
                                                                                                                                          
                                                                                                                                              DataWrapper data(midValue, strlen(midValue));
                                                                                                                                              Element midValueElement;
                                                                                                                                              midValueElement.data = &data;
                                                                                                                                              midValueElement.next = NULL;
                                                                                                                                          
                                                                                                                                              Element arrElement;
                                                                                                                                              DataWrapper arrData(NULL, 0);
                                                                                                                                              arrElement.data = &arrData;
                                                                                                                                              arrElement.next = NULL;
                                                                                                                                          
                                                                                                                                          
                                                                                                                                              int i = start, j = end;
                                                                                                                                          
                                                                                                                                              while (i <= j) {
                                                                                                                                          
                                                                                                                                                  arrData.pRawData = arr[i];
                                                                                                                                                  arrData.len = strlen(arr[i]);
                                                                                                                                          
                                                                                                                                                  while (CompareElements(&arrElement, &midValueElement) < 0) {
                                                                                                                                                      i++;
                                                                                                                                          
                                                                                                                                                      arrData.pRawData = arr[i];
                                                                                                                                                      arrData.len = strlen(arr[i]);
                                                                                                                                                  }
                                                                                                                                          
                                                                                                                                                  arrData.pRawData = arr[j];
                                                                                                                                                  arrData.len = strlen(arr[j]);
                                                                                                                                          
                                                                                                                                                  while (CompareElements(&arrElement, &midValueElement) > 0) {
                                                                                                                                                      j--;
                                                                                                                                          
                                                                                                                                                      arrData.pRawData = arr[j];
                                                                                                                                                      arrData.len = strlen(arr[j]);
                                                                                                                                                  }
                                                                                                                                          
                                                                                                                                                  if (i <= j) {
                                                                                                                                                      tmp = arr[i];
                                                                                                                                                      arr[i] = arr[j];
                                                                                                                                                      arr[j] = tmp;
                                                                                                                                          
                                                                                                                                                      i++;
                                                                                                                                                      j--;
                                                                                                                                                  }
                                                                                                                                              }
                                                                                                                                          
                                                                                                                                              if (start < j) {
                                                                                                                                                  quickSort(arr, start, j);
                                                                                                                                              }
                                                                                                                                              if (i < end) {
                                                                                                                                                  quickSort(arr, i, end);
                                                                                                                                              }
                                                                                                                                          }
                                                                                                                                          
                                                                                                                                          
                                                                                                                                          static int compareStrings(const void* a, const void* b)
                                                                                                                                          {
                                                                                                                                              return strcmp(*(const char**)a, *(const char**)b);
                                                                                                                                          }
                                                                                                                                          
                                                                                                                                          int getTime()
                                                                                                                                          {
                                                                                                                                              struct timeval tp;
                                                                                                                                              gettimeofday(&tp, NULL);
                                                                                                                                              long int ms = tp.tv_sec * 1000 + tp.tv_usec / 1000;
                                                                                                                                          
                                                                                                                                              return ms;
                                                                                                                                          }
                                                                                                                                          
                                                                                                                                          int main()
                                                                                                                                          {
                                                                                                                                              const int N = 10000;
                                                                                                                                          
                                                                                                                                              char** strings = new char*[N];
                                                                                                                                              const char* symbols = "0123456789abcdefghijklmnopqrstuvwxyz";
                                                                                                                                          
                                                                                                                                              srand(time(NULL));
                                                                                                                                          
                                                                                                                                              int i, j;
                                                                                                                                              const int maxStringLen = 20;
                                                                                                                                              for (i = 0; i < N; i++) {
                                                                                                                                                  int sLen = (rand() % maxStringLen) + 1;
                                                                                                                                          
                                                                                                                                                  strings[i] = new char[sLen + 1];
                                                                                                                                                  strings[i][sLen] = '\0';
                                                                                                                                          
                                                                                                                                                  for (j = 0; j < sLen; j++) {
                                                                                                                                                      strings[i][j] = symbols[rand() % 36];
                                                                                                                                                  }
                                                                                                                                              }
                                                                                                                                          
                                                                                                                                              char** systemSortedStrings = new char*[N];
                                                                                                                                              for (i = 0; i < N; i++) {
                                                                                                                                                  systemSortedStrings[i] = strings[i];
                                                                                                                                              }
                                                                                                                                              qsort(systemSortedStrings, N, sizeof(const char*), compareStrings);
                                                                                                                                          
                                                                                                                                              int t1, t2;
                                                                                                                                          
                                                                                                                                          
                                                                                                                                          
                                                                                                                                              // voronkaSort
                                                                                                                                          
                                                                                                                                              LinkedList* list = new LinkedList();
                                                                                                                                              for (i = 0; i < N; i++) {
                                                                                                                                                  DataWrapper* data = new DataWrapper(strings[i], strlen(strings[i]));
                                                                                                                                          
                                                                                                                                                  Element* element = new Element();
                                                                                                                                                  element->data = data;
                                                                                                                                          
                                                                                                                                                  list->addToTail(element);
                                                                                                                                              }
                                                                                                                                          
                                                                                                                                          
                                                                                                                                              COMPARE_ELEMENTS_COUNT = 0;
                                                                                                                                              t1 = getTime();
                                                                                                                                              voronkaSort(list);
                                                                                                                                              t2 = getTime();
                                                                                                                                          
                                                                                                                                              char** voronkaSortedStrings = new char*[N];
                                                                                                                                              int n = 0;
                                                                                                                                              for (Element* cur = list->head; cur != NULL; cur = cur->next) {
                                                                                                                                                  voronkaSortedStrings[n] = cur->data->pRawData;
                                                                                                                                                  n++;
                                                                                                                                              }
                                                                                                                                          
                                                                                                                                          
                                                                                                                                              printf("voronkaSort\n");
                                                                                                                                              for (i = 0; i < N; i++) {
                                                                                                                                                  if (strcmp(voronkaSortedStrings[i], systemSortedStrings[i]) != 0) {
                                                                                                                                                      printf("ERROR: incorrect sorting\n");
                                                                                                                                                      break;
                                                                                                                                                  }
                                                                                                                                              }
                                                                                                                                              if (i == N) {
                                                                                                                                                  printf("correct sorting\n");
                                                                                                                                              }
                                                                                                                                              printf("%d ms / %d elements\n", t2 - t1, N);
                                                                                                                                              printf("CompareElements() calls: %d\n", COMPARE_ELEMENTS_COUNT);
                                                                                                                                          
                                                                                                                                          
                                                                                                                                          
                                                                                                                                          
                                                                                                                                              // quickSort
                                                                                                                                          
                                                                                                                                              char** quickSortSortedStrings = new char*[N];
                                                                                                                                              for (i = 0; i < N; i++) {
                                                                                                                                                  quickSortSortedStrings[i] = strings[i];
                                                                                                                                              }
                                                                                                                                          
                                                                                                                                              COMPARE_ELEMENTS_COUNT = 0;
                                                                                                                                              t1 = getTime();
                                                                                                                                              quickSort(quickSortSortedStrings, 0, N - 1);
                                                                                                                                              t2 = getTime();
                                                                                                                                          
                                                                                                                                          
                                                                                                                                              printf("\n");
                                                                                                                                          
                                                                                                                                              printf("quickSort\n");
                                                                                                                                              for (i = 0; i < N; i++) {
                                                                                                                                                  if (strcmp(quickSortSortedStrings[i], systemSortedStrings[i]) != 0) {
                                                                                                                                                      printf("ERROR: incorrect sorting\n");
                                                                                                                                                      break;
                                                                                                                                                  }
                                                                                                                                              }
                                                                                                                                              if (i == N) {
                                                                                                                                                  printf("correct sorting\n");
                                                                                                                                              }
                                                                                                                                              printf("%d ms / %d elements\n", t2 - t1, N);
                                                                                                                                              printf("CompareElements() calls: %d\n", COMPARE_ELEMENTS_COUNT);
                                                                                                                                          
                                                                                                                                          
                                                                                                                                              return 0;
                                                                                                                                          }
                                                                                                                                          


                                                                                                                                            –2
                                                                                                                                            Ну это уже что-то! Ладно, Вам жирный плюс за мужской ответ. Но как программист — уж извините — Вы меня не интересуете. От слова «совсем».
                                                                                                                                              0
                                                                                                                                              Бегло посмотрел на код. Замечания:

                                                                                                                                              1. Сортировка в mergeLists (хоть qsort, хоть чем-то ещё) не имеет смысла, поскольку размеры списков меняются динамически, и обычный пузырёк (который даже не сортирует, а находит два наименьших) сработает быстрее и эффективнее.

                                                                                                                                              2. Да, двойной цикл по спискам выглядит куда разумнее. У меня нечто похожее, только сделано с точностью до наоборот:
                                                                                                                                              а) более «тяжёлые» списки подтягиваются как раз к началу буфера, а не к его концу
                                                                                                                                              б) цикл по индексам списков, К КОТОРЫМ подливаются другие, идёт вверх, а по тем, КОТОРЫЕ подливаются — вниз, с конца. Тогда убирается всегда последний элемент буфера «лёгким движением руки».
                                                                                                                                              в) вместо сортировки списков производится ранжирование (большие, малые и сверхмалые) — при этом ориентируемся на размер исходного файла
                                                                                                                                              г) сверхмалые списки сливаются «безоговорочно», вообще без анализа, кто там из них больше, а кто меньше — кого интересует эта «мышиная возня»? По этой же причине процесс может не остановиться на 3/4, а схлопнуть буквально все списки буфера в один. Ну или сколько там получится сверхмалых после всех слияний.
                                                                                                                                              д) малые списки сливаются «иногда» — например, когда их число превышает половину буфера. И они уже анализируются на размер, поскольку могут содержать уже многие тысячи элементов.
                                                                                                                                              е) большие списки сливаются только в самом конце, перед выдачей результатов.

                                                                                                                                              3. Посмотрел и на performMerge. К моему удивлению, копирования не увидел. Правда, увидел нечто другое: ЕСЛИ список toIndex является одновременно и результирующим списком, ТО что произойдёт, когда не только головной элемент fromIndex, но и второй, третий, четвёртый окажутся всё равно меньше головы toIndex? Где тогда будем брать исходные значения следующих элементов toIndex? Они не затрутся, часом?
                                                                                                                                                0
                                                                                                                                                Они не затрутся, часом?

                                                                                                                                                Для проверки там сделана сортировка системной функцией и сравнение результатов, сортировалось всегда правильно. Указатели перед изменением сохраняются в e1/e2, так что даже когда мы затерем голову списка, мы продолжим с тех элементов, которые были следующими.


                                                                                                                                                По техническим моментам согласен, я не ставил себе цель за час-другой написать супероптимальную программу. Меня интересовала алгоритмическая сложность. Но O(N) сравнений в среднем случае там все равно нет, там обычный доказанный O(NlogN), о чем вам писали в этом комменте. Если бы вы изначально написали так в статье, никто бы с вами спорить не стал.


                                                                                                                                                Пример: перед слиянием длины минимальных списков были такие [2,2,2,2,2,2,2,2], после слияния стали такие [4,4,4,4]. При следующем слиянии те же элементы снова будут участвовать в сравнениях, то есть на каждый элемент приходится больше одного сравнения, и это число не константное, а зависит от количества элементов.

                                                                                                                                                  0
                                                                                                                                                  А при чём тут «сортировка системной функцией»? Сливаемые списки отсортированы по определению, а вот в какой последовательности их элементы пойдут в выходной поток — это вопрос. Указатели-то сохраняются, но если мы отправим десяток элементов из второго списка, а из первого при этом будут считаны лишь пара-тройка, то это, как я понимаю, не поможет. В моей реализации нет никакого массива списков — их паспорта размазаны по всему ОЗУ и хранятся вместе с элементами данных, поэтому не могут быть затёрты при любом порядке формирования результирующего списка.

                                                                                                                                                  А меня всегда интересовала оптимальность работы программы как продукта, поэтому я пытался минимизировать, в первую очередь, число файловых операций и сохранить поточность чтения/записи данных. Общее время работы программы слабо зависит от числа сравнений, даже если их количество отличается на порядки: просто счётчик списков в буфере либо стоит на месте (относительно медленно растёт), либо прыгает как сумасшедший от пары сотен до десяти, да так, что глазом не уследишь, сколько там было операций даже очистки буфера. Так что теоретически (по числу сравнений) там действительно логарифм (для худшего случая или близкого к нему), но практически время растёт почти линейно. Я так и написал в статье: «Эксперименты показали, что время сортировки соизмеримо со временем копирования файлов или любой другой линейной обработки данных. Тестирование на специально подготовленных массивах для лучшего и худшего случая объёмом от миллиона до ста миллионов строк показало: несмотря на то, что количество сравнений элементов отличается на порядки, общее время сортировки замедляется лишь на десятки процентов (во всех экспериментах менее, чем в два раза)».

                                                                                                                                                  Да, да, «при следующем слиянии те же элементы снова будут участвовать в сравнениях, то есть на каждый элемент приходится больше одного сравнения» — отсюда и логарифм. Но если в классическом алгоритме сортировки слиянием так приходится делать ВСЕГДА, то воронка отлавливает из общего потока все монотонно возрастающие или убывающие подпоследовательности, делая их «уже слитыми». И чем их больше и чем они длиннее, тем меньше приходится сравнений на каждый элемент, тем «линейнее» будет время сортировки даже если смотреть именно на количество сравнений.
                                                                                                                                                    0
                                                                                                                                                    А при чём тут «сортировка системной функцией»?

                                                                                                                                                    Я же сказал — для проверки, что я нигде не ошибся, и мой код сортирует правильно.


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

                                                                                                                                                    Я проверял этот вариант, это работает нормально. Иначе оно бы через раз падало, строки же случайные,


                                                                                                                                                    А меня всегда интересовала оптимальность работы программы как продукта, поэтому я пытался минимизировать, в первую очередь, число файловых операций и сохранить поточность чтения/записи данных. Общее время работы программы слабо зависит от числа сравнений.

                                                                                                                                                    Число промежуточных файловых операций в случае когда данные не помещаются в ОЗУ определяется в первую очередь числом сравнений.


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


                                                                                                                                                    Я так и написал в статье: Эксперименты показали, что время сортировки соизмеримо со временем копирования файлов или любой другой линейной обработки данных.

                                                                                                                                                    Дело в том, что вы сравниваете свой алгоритм с другими сортировками, для которых при оценке сложности никакие файловые операции не рассматриваются. В таком ключе время любой сортировки соизмеримо со временем копирования файлов, ваша ничем не лучше.


                                                                                                                                                    общее время сортировки замедляется лишь на десятки процентов

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


                                                                                                                                                    И чем их больше и чем они длиннее, тем меньше приходится сравнений на каждый элемент, тем «линейнее» будет время сортировки даже если смотреть именно на количество сравнений.

                                                                                                                                                    В такой формулировке соглашусь, только вы слишком преувеличиваете линейность.


                                                                                                                                                    Если вот такую линейную последовательность
                                                                                                                                                    "11", "12", "13", "14",
                                                                                                                                                    повторять до заданного N, то число сравнений выглядит так:


                                                                                                                                                    N = 256, O(X) = 1725, O(X)/N = 6.73
                                                                                                                                                    N = 512, O(X) = 3901, O(X)/N = 7.61
                                                                                                                                                    N = 1024, O(X) = 8701, O(X)/N = 8.49
                                                                                                                                                    N = 2048, O(X) = 19197, O(X)/N = 9.37
                                                                                                                                                    N = 4096, O(X) = 41981, O(X)/N = 10.24
                                                                                                                                                    N = 8192, O(X) = 91086, O(X)/N = 11.11
                                                                                                                                                    N = 16384, O(X) = 196511, O(X)/N = 11.99
                                                                                                                                                    N = 32768, O(X) = 421776, O(X)/N = 12.87


                                                                                                                                                    Для быстрой сортировки так:


                                                                                                                                                    N = 256, O(X) = 2111, O(X)/N = 8.24
                                                                                                                                                    N = 512, O(X) = 4800, O(X)/N = 9.37
                                                                                                                                                    N = 1024, O(X) = 10474, O(X)/N = 10.22
                                                                                                                                                    N = 2048, O(X) = 24130, O(X)/N = 11.78
                                                                                                                                                    N = 4096, O(X) = 49145, O(X)/N = 11.99
                                                                                                                                                    N = 8192, O(X) = 107742, O(X)/N = 13.15
                                                                                                                                                    N = 16384, O(X) = 228535, O(X)/N = 13.94
                                                                                                                                                    N = 32768, O(X) = 535148, O(X)/N = 16.33


                                                                                                                                                    Динамика схожая, а для быстрой сортировки зависимость от числа элементов в среднем случае O(X) = O(NlogN). Длинные линейные последовательности в несортированных данных на практике не так уж часто встречаются.

                                                                                                                                                      0
                                                                                                                                                      Просто потому что основное преимущество сортировок это число сравнений.

                                                                                                                                                      Немного не так. Это для неустойчивых сортировок. Для них перемещений меньше, но на большие расстояния.
                                                                                                                                                      Для устойчивых больше коротких перемещений.

                                                                                                                                                      Например, при сортировке массива вставками с двоичным поиском, число сравнений O(N*log(N)). Но число вставок (перемещений) O(N^2).

                                                                                                                                                      Так что, определяется худшим из этих двух показателей.
                                                                                                                                                        0
                                                                                                                                                        Ну, у меня сортировка неустойчивая, но, поскольку вся строка является ключом, можно сказать, что устойчивая.
                                                                                                                                                        0
                                                                                                                                                        Нет, число промежуточных файловых операций в случае когда данные не помещаются в ОЗУ определяется в первую очередь размером доступного ОЗУ. Да, я согласен — любая сортировка настолько же оптимальная, как моя, если идёт режим внешней сортировки и размер доступного ОЗУ НАМНОГО меньше сортируемого массива — недаром про неё написано лишь несколько общих фраз, а все алгоритмы описаны для случая сортировки внутренней. И я в полном восхищении от программы rpsort — я просто не понимаю, КАК можно получить такую скорость! Да, допустим — я со своим слиянием сотен или тысяч файлов проигрываю версии, если все буферы ОЗУ сбрасывать в один файл, но ведь это всё равно ФАЙЛОВЫЕ операции! Всё равно приходится устраивать болтанку головками по дорожкам, а это ВРЕМЯ! Остаётся предположить, что либо программа всё-таки отхватывает больше ОЗУ, чем сортир для ДОС, либо сама операционка кеширует обращение к диску и основной объём операций происходит всё-таки в ОЗУ. Но в наше время ОЗУ проблемой не является, так что внешняя сортировка действительно стала экзотикой.

                                                                                                                                                        Ну, нет! Квадрат — он и в Африке квадрат! Я реально сортирую массивы в десятки и сотни миллионов элементов, и если ЗДЕСЬ нарваться на квадрат — это будет ПОЛНАЯ жопа! Никакой учёт или неучёт файловых операций не спасёт!

                                                                                                                                                        Я как-то читал здесь, на Хабре (ещё до того, как зарегистрировался) какой-то отчёт о сравнении различных алгоритмов сортировки, так там массивы были от 10^6 (или даже от 10^5 — не помню) до 10^8, причём на этих объёмах тестировались лишь малая часть алгоритмов, и данные были тоже определённым образом подготовлены. Впрочем, не помню, но уверен, что воронка спокойно пройдёт все эти тесты и любые другие. Я и хотел сделать онлайн-сервис, чтобы не на словах, а на деле продемонстрировать, что воронка лучше ЛЮБОГО из них!

                                                                                                                                                        А какие проблемы в построении связного списка? Текущий элемент просто пристраивается в текущий список воронки — в последней реализации за одно или два сравнения — И ВСЁ! Ну, размер элемента в ОЗУ увеличивается на 6 байт — размер его паспорта. На скорость это не влияет вообще никак!

                                                                                                                                                        Если вот такую линейную последовательность
                                                                                                                                                        «11», «12», «13», «14»,
                                                                                                                                                        повторять до заданного N, то число сравнений выглядит так:
                                                                                                                                                        Ну, мне лень переопределять число сравнений в миллионах на точные цифры, и сравнения лень проводить, но я эту последовательность, насколько я понимаю, поймает воронка размером в два списка, независимо от числа повторов. Плюс одно слияние. :)

                                                                                                                                                        Длинные линейные последовательности в несортированных данных на практике не так уж часто встречаются.
                                                                                                                                                        Честно? Мне сейчас действительно ВСЁ РАВНО, какие там данные. Бывает, что я просто копирую в общую кучу 2-3 десятка уже отсортированных файлов и сортирую — в этом случае размер буфера составит те самые 2-3 десятка, а бывает (это обычно происходит при сортировке данных в формате base64), что число сравнений зашкаливает за 5-6 миллиардов — время сортировки практически одинаковое. Или различия настолько малы, что на это вообще не стоит обращать внимание.

                                                                                                                                                        А, вот у меня какая-то старая реализация воронки, где число сравнений считается точно, а не в миллиардах. Вот я накопировал -ти 11-12-13-14 до размера 768М и… блин, всё равно два временных файла получилось! Ведь в данном случае адрес паспорта вдвое больше размера самой строки! Ладно, накопировал поменьше: до 384М. Имеем: 134217728 элементов, 436207607 сравнений. Блин, что-то мало… может, счётчик 32-разрядный переполнился? Ещё разок, повнимательнее… нет, всё верно. Каждый элемент встречается 33554432 раза. Правда, я не знаю, сколько списков в этой воронке может, все 64? А последняя версия… УПС! Что за хрень?! А почему она еле-еле читает? За 20 секунд еле-еле миллион осилила (0.6%)… 1% осилила… похоже на какой-то глюк… ладно — эту уже когда-нибудь, как до дома доберусь, посмотрю. То есть через неделю-другую.
                                                                                                                                                          0
                                                                                                                                                          Никакой учёт или неучёт файловых операций не спасёт!

                                                                                                                                                          Ну rpsort использует быструю сортировку, и нормально работает, не зависает.


                                                                                                                                                          Я и хотел сделать онлайн-сервис, чтобы не на словах, а на деле продемонстрировать, что воронка лучше ЛЮБОГО из них!

                                                                                                                                                          В онлайн-сервисе все время съест загрузка/выгрузка файлов. Кроме того, будет сильно влиять мощность процессора и скорость жесткого диска на сервере. Поэтому так никто и не сравнивает.


                                                                                                                                                          А какие проблемы в построении связного списка?

                                                                                                                                                          Такие что готовый плоский массив указателей на данные надо в него преобразовать.


                                                                                                                                                          Ну, размер элемента в ОЗУ увеличивается на 6 байт — размер его паспорта.

                                                                                                                                                          Это все фрагментированные данные, которые выделяются через new. Хотя не знаю, может вы всё на стеке храните.


                                                                                                                                                          эту последовательность, насколько я понимаю, поймает воронка размером в два списка, независимо от числа повторов

                                                                                                                                                          Тогда для нее не будет верно "требующий не более двух сравнений для пристройки элемента".
                                                                                                                                                          С размером воронки в 1 список в буфере будет [11, 11, 12, 13, 14], [11, 12, 13, 14], [11, 12, 13, 14],… [12, 13, 14]. Возможно с этим и связано "А последняя версия… УПС! Что за хрень?! А почему она еле-еле читает?".


                                                                                                                                                          Бывает, что я просто копирую в общую кучу 2-3 десятка уже отсортированных файлов
                                                                                                                                                          а бывает, что число сравнений зашкаливает за 5-6 миллиардов — время сортировки практически одинаковое.

                                                                                                                                                          Сортировка именно файлов вручную это вообще редкий случай. Обычно сортировка требуется в приложении в автоматическом режиме для данных в оперативной памяти. На сервисах с высокими нагрузками вообще избегают лишний раз обращаться к файлам или к сети, потому что это значительные задержки.

                                                                                                                                                            0
                                                                                                                                                            rpsort использует НЕ ПРОСТО быструю сортировку, а совершенно потрясающую её реализацию. Ни в каком Квике нет ни слова про временные файлы, не говоря уже о весьма специфическом их формате. Эту сортировку делал Мастер! А вот юзерам от всяких там Биллов Гейтсов досталось почему-то дерьмо — как раз примерно в то время вышла Win-95 с позорнейшим встроенным сортиром.

                                                                                                                                                            В онлайн-сервисах ДО ХРЕНИЩА операций «загрузка/выгрузка файлов», иногда куда более объёмных, чем те, которые я хотел бы обрабатывать. Никаких проблем с этим не вижу вообще. И я сильно сомневаюсь, что мощность процессора и скорость жесткого диска на сервере хуже, чем на моём компе или, тем более, на том, с которого я сейчас это пишу. И я ничего не собираюсь «сравнивать» — я просто хочу дать конечным пользователям НОРМАЛЬНЫЙ сервис сортировки — насколько я знаю, ни один из аналогичных алгоритмов такого сервиса не предложил (не считая того позорища, которое я видел).

                                                                                                                                                            Какой ещё, блин, «готовый плоский массив указателей на данные»?! КОМУ «надо в него преобразовать»? Нет у меня никакого «плоского массива» — мне он нафиг не нужен!

                                                                                                                                                            Это все фрагментированные данные, которые выделяются через new. Хотя не знаю, может вы всё на стеке храните.
                                                                                                                                                            Какие, блин, «фрагментированные данные»?! Какой «new», какой «стек»?! Я же писал: паспорта хранятся ВМЕСТЕ С ДАННЫМИ! Сначала идёт 6 байт паспорта, а сразу за ними сама строка.

                                                                                                                                                            Ну и чего? В худшем случае там вообще по два элемента в список помещаются, а тут всё-таки четыре. Нет, С ЭТИМ ничего не может быть связано. Тем более, что сортир потом вдруг неожиданно ускорился и тоже всё отсортировал.

                                                                                                                                                            При чём тут «сортировка именно файлов вручную»? Я говорил про работу с базой данных OSM, которая в нарезках имеет 300 с чем-то файлов исходников. Да, «это редкий случай», а вот просто сортировка нужна почти постоянно. Например, при формировании очередного комплекта карт более грубого масштаба исходные данные сортируются трижды (с разными настройками). А про структуризацию данных описаний я и просто молчу — там она используется много-много раз!

                                                                                                                                                            P.S. Любопытная закономерность: эта ветка набрала почти 4 сотни комментов — в основном тех, где размахивали руками и топали ногами. А сейчас ветка как будто вымерла, и разговор поддерживает тот единственный, с кем мы уже попрощались. :)
                                                                                                                                                              0
                                                                                                                                                              Дополнил каждую строчку этих 11-12-13-14 символами _12345# каждую (размер вырос до 1280М) — прекрасно сортирует! Хотя размеры списков воронки, очевидно, не изменились ни на йоту. Хм, а на записи после 55 миллионов строк сновав резко затормозила, хотя здесь вообще ни одного сравнения нет… то ли операционка какой-то вредительской деятельностью занимается, то ли какой-нить Касперский. Промежуточных файлов, конечно, снова стало два (899М и 381М), а число сравнений, включая слияние этих двух, составило 228.4 миллиона. Что, ДАЖЕ МЕНЬШЕ?! И отсортировала всё правильно… а ну, если опять отрезать эти _12345#? Одуреть! Опять жуткие тормоза! Кстати, а ДОСовский сортир как? А ДОСовский плодит со страшной силой промежуточные файлы размером 185640 байт, но работает всё равно быстрее версии для NT! Очевидно, какой-то глюк — скорее всего, связанный с моим «умением» работать с компилятором WATCOM.
                                                                                                                                                                0
                                                                                                                                                                rpsort использует НЕ ПРОСТО быструю сортировку, а совершенно потрясающую её реализацию. Ни в каком Квике нет ни слова про временные файлы

                                                                                                                                                                Вы никак не хотите понять то что вам все тут повторяли. Сортировки ВООБЩЕ не связаны ни с какими файлами. Это алгоритмы, их можно применять и к строкам и к числам и к файлам, и вообще к любым сравнимым сущностям. В rpsort не какая-то особая реализация quicksort, а просто ее применение к сортировке в файлах. Если бы она в памяти сортировала, там был бы точно такой же алгоритм сортировки с тем же самым числом сравнений и перестановок.


                                                                                                                                                                как раз примерно в то время вышла Win-95 с позорнейшим встроенным сортиром

                                                                                                                                                                В Linux есть нормальная команда sort, для Windows есть портированные версии. Например такая версия входит в состав пакета Git For Windows. Сейчас проверил, файл antarctica-latest.osm сортирует за 20 секунд. Можете скачать и сравнить со своей программой на своем железе.


                                                                                                                                                                В онлайн-сервисах ДО ХРЕНИЩА операций «загрузка/выгрузка файлов», иногда куда более объёмных, чем те, которые я хотел бы обрабатывать. Никаких проблем с этим не вижу вообще.

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


                                                                                                                                                                И я сильно сомневаюсь, что мощность процессора и скорость жесткого диска на сервере хуже, чем на моём компе

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


                                                                                                                                                                Какой ещё, блин, «готовый плоский массив указателей на данные»?! КОМУ «надо в него преобразовать»? Нет у меня никакого «плоского массива» — мне он нафиг не нужен!

                                                                                                                                                                Я в этой части разве про вас говорил? Я говорил про преимущество quicksort.
                                                                                                                                                                Плоский массив — этот тот который создается просто через new или через указание константного размера в исходниках.


                                                                                                                                                                Какие, блин, «фрагментированные данные»?! Какой «new», какой «стек»?! Я же писал: паспорта хранятся ВМЕСТЕ С ДАННЫМИ! Сначала идёт 6 байт паспорта, а сразу за ними сама строка.

                                                                                                                                                                6 байт паспорта — это тоже данные. В компьютерах любые значения называются "данные".
                                                                                                                                                                Эти 6 байт паспорта для каждого элемента вы через new выделяете или в локальных переменных на стеке храните?


                                                                                                                                                                При чём тут «сортировка именно файлов вручную»?

                                                                                                                                                                Это вы про нее говорили, приводили в качестве примера для случаев отсортированых последовательностей. "я просто копирую в общую кучу 2-3 десятка уже отсортированных файлов". Я вам и говорю, что она ни при чем, это практически никогда не требуется, а значит длинные последовательности редко встречаются.


                                                                                                                                                                а вот просто сортировка нужна почти постоянно

                                                                                                                                                                А вот просто сортировка в большинстве случаев делается в памяти без всяких файлов. Либо для этого используется база данных, в которой методы сортировки встроенные и просто так их не поменять.


                                                                                                                                                                P.S. А о чем разговаривать. Какие-то сведения об алгоритме мы наконец-то от вас добились. O(N) в среднем случае у вас нет, значит сенсации никакой нет. Обсуждать нечего. Немного лучше quicksort это конечно плюс, возможно где-то это будет полезно. Лично я продолжаю разговор надеясь развеять некоторые ваши заблуждения, которые может разделять и кто-то из читателей.

                                                                                                                                                                  –2
                                                                                                                                                                  Господи, да мне какой только ерунды здесь ни повторяли! И я тыщу раз говорил — я — ПРАКТИК! Мне АБСОЛЮТНО по барабану все эти дурацкие теоретические изыски с дурацкими подсчётами дурацких сравнений. Нормальным людям сортировка требуется ДЛЯ РАБОТЫ, а не для обсуждения сферических коней в вакууме. А потому у них сортировки СВЯЗАНЫ с файлами! А в файлах уже могут быть и строки, и числа, и структуры, и все остальные «любые сравнимые сущности». Меня АБСОЛЮТНО не интересуют, что там «было бы если бы» — я просто ВИЖУ, что работа с файлами в rpsort организована ВИРТУОЗНО, а никакое не «просто ее применение к сортировке в файлах». Потому как я — программист, а Вы — просто кодировать умеете.

                                                                                                                                                                  Не знаю — может, в Linux и есть нормальная команда sort — никогда не работал, но в Виндах времён rpsort было АБСОЛЮТНОЕ дерьмо! Да и сейчас тоже немногим лучше. И я не хочу ничего скачивать и не хочу нигде рыскать — ЕСЛИ И В САМОМ ДЕЛЕ где-то есть НОРМАЛЬНАЯ утилита сортировки, то какого ж хрена она где-то там зарыта, а всплывает всегда полное дерьмо? ЧЕМ ИМЕННО эта Линуксовая сортировка лучше? А если лучше, какого хрена она не вытеснит всю эту мерзость с наших компьютеров? Куда, например, подевалась эта rpsort? Почему о ней не знает даже Гугл?

                                                                                                                                                                  У меня файл antarctica-latest.osm КОПИРУЕТСЯ за 30 секунд. И ничего ни с чем сравнивать я не собираюсь — мой алгоритм меня ПОЛНОСТЬЮ устраивает как продукт! И я его ни на какой Квик или что-либо другое менять не собираюсь. И сравнивать ни с чем не собираюсь, на очередной помойке найденным! Сервис есть? Нет? Пошли на!

                                                                                                                                                                  Кстати, а Вы-то что так опять разговорились? Разговор опять перешёл от программирования в область «бла-бла»? Ну и как, долго Вы ещё «прощаться» будете? А Ваш долбаный «плоский массив» засуньте в… в общем, Вы знаете куда.

                                                                                                                                                                  — Эти 6 байт паспорта для каждого элемента вы через new выделяете или в локальных переменных на стеке храните?
                                                                                                                                                                  ПЦ! Сударь, я УЖЕ НАПИСАЛ, где и как хранятся паспорта элементов! Я это ещё В САМОЙ ЗАМЕТКЕ написал! Потрудитесь прочесть! Читать нужно слева направо. А Ваш долбаный «new» вместе с Вашим долбаным «стеком» засуньте туда же, куда и «плоский массив». И НЕ ВАМ «развеивать некоторые мои заблуждения», ибо я Вас НЕ ВОСПРИНИМАЮ как программиста, как специалиста, и несколько раз уже говорил это открытым текстом. Потрудитесь прочесть, наконец!
                                                                                                                                                                    0
                                                                                                                                                                    И я тыщу раз говорил — я — ПРАКТИК!

                                                                                                                                                                    Да хоть сколько повторите. Сортировки все равно не связаны ни с какими файлами. И в rpsort все равно обычный всем известный алгоритм. Это факты.


                                                                                                                                                                    Нормальным людям сортировка требуется ДЛЯ РАБОТЫ, а не для обсуждения сферических коней в вакууме. А потому у них сортировки СВЯЗАНЫ с файлами!

                                                                                                                                                                    Этот вывод неверный. Сортировать гигабайтные файлы, тем более запуская вручную консольную программу, это ну может 1 процент от всего использования сортировок. А может и меньше. А остальные 99% это автоматическая сортировка в памяти в заранее написанной программе. Это факты.


                                                                                                                                                                    я УЖЕ НАПИСАЛ, где и как хранятся паспорта элементов! Я это ещё В САМОЙ ЗАМЕТКЕ написал!

                                                                                                                                                                    Там написано "в ОЗУ". И new и стек это ОЗУ. Я не знаю, что вы подразумеваете под "в ОЗУ, которое также заказывается динамически" с учетом вашего отношения к new. Использование new или malloc это и есть динамическое выделение. Это тоже факты.


                                                                                                                                                                    Разговор опять перешёл от программирования в область «бла-бла»?

                                                                                                                                                                    Вы не заметили, что я только отвечаю на цитаты из вашего текста? Так что это вы перешли в область «бла-бла».


                                                                                                                                                                    И ничего ни с чем сравнивать я не собираюсь — мой алгоритм меня ПОЛНОСТЬЮ устраивает как продукт!

                                                                                                                                                                    А разве кто-то утверждал, что он вас не устраивает? Почему вы приписываете другим свои домыслы?
                                                                                                                                                                    Был разговор про эффективность, я привел примеры и доказательства. Я не спрашивал, что вы собираетесь делать с этой информацией.


                                                                                                                                                                    Кстати, а Вы-то что так опять разговорились?

                                                                                                                                                                    Хочу и говорю. Вы мне запрещаете или что?


                                                                                                                                                                    И НЕ ВАМ «развеивать некоторые мои заблуждения», ибо я Вас НЕ ВОСПРИНИМАЮ как программиста, как специалиста, и несколько раз уже говорил это открытым текстом.

                                                                                                                                                                    А я несколько раз открыто это проигнорировал.
                                                                                                                                                                    Мне без разницы, что вы об этом думаете и сколько раз что-то говорили. Я вашим мнением не интересовался.

                                                                                                                                                                      –2
                                                                                                                                                                      ВАМ, сударь, этот алгоритм НЕ известный! И мне ТОЖЕ не известный. И я утверждаю категорически, что ни одна собака из этих «всех» не осмелится поднять лапку, что ей, дескать, известен этот алгоритм. Это даже не считая того, что я убью эту собаку наповал первым же вопросом о структуре одного из временных файлов. Так что не надо ВРАТЬ, сударь!

                                                                                                                                                                      Факты?! ГДЕ эти «факты»? Назовите НОРМАЛЬНЫЕ программы сортировки! Назовите НОРМАЛЬНЫЕ алгоритмы сортировки! ЧЕМ ИМЕННО нужно сортировать из всего обилия этих алгоритмов, в который затесался даже клинически маразматический «bogosort»? А какой именно РЕАЛИЗАЦИЕЙ этого наилучшего алгоритма следует пользоваться, не говоря уже про вопрос ПОЧЕМУ? Ну, где там «все»? Хоть один осмелится что-нибудь вякнуть? Может быть, Вы сами рискнёте, сударь? Нет? ;)

                                                                                                                                                                      А факты состоят совершенно в другом: ВЫ, ЛИЧНО ВЫ сначала продемонстрировали свою АБСОЛЮТНОЮ безграмотность как программист, а потом стали дрочить ВАМИ же придуманный идиотский «тест», хотя любому идиоту понятно, что ТАКОЕ говно отловит «воронка» размером в сраных два списка, так что сложность там ЛИНЕЙНАЯ! А практика показала, что воронка размером в один список, формально имеющая логарифмическую сложность, потребовала ДАЖЕ МЕНЬШЕ этих дурацких сравнений, которые абсолютно ни о чём не говорят, и нужны разве что полуграмотному стаду баранов, корчащему из себя специалистов. Вот это — ФАКТЫ! А ещё факты в том, что Вы даже свой дурацкий пример додрочили лишь до сраных 32К элементов, а «воронка» отсортировала 128М! Вот Вам РЕАЛЬНЫЕ факты! И если Вы ХОТЬ ЧТО-ТО собираетесь показать этими дурацкими цифирями, так доведите, по крайней мере, этот Ваш «тест» до конца! Ладно, какой Вы «реализатор» воронки — я в курсе — хотя бы Квиком, который «всем известный».
                                                                                                                                                                      N = 16384, O(X) = 196511, O(X)/N = 11.99
                                                                                                                                                                      N = 32768, O(X) = 421776, O(X)/N = 12.87
                                                                                                                                                                      N = 65536, O(X) = ?, O(X)/N =?
                                                                                                                                                                      N = 131072, O(X) = ?, O(X)/N =?
                                                                                                                                                                      N = 262144, O(X) = ?, O(X)/N =?
                                                                                                                                                                      N = 524288, O(X) = ?, O(X)/N =?
                                                                                                                                                                      N = 1048576, O(X) = ?, O(X)/N =?
                                                                                                                                                                      N = 2097152, O(X) = ?, O(X)/N =?
                                                                                                                                                                      N = 4194304, O(X) = ?, O(X)/N =?
                                                                                                                                                                      N = 8388608, O(X) = ?, O(X)/N =?
                                                                                                                                                                      N = 16777216, O(X) = ?, O(X)/N =?
                                                                                                                                                                      N = 33554432, O(X) = ?, O(X)/N =?
                                                                                                                                                                      N = 67108864, O(X) = ?, O(X)/N =?
                                                                                                                                                                      N = 134217728, O(X) = ?, O(X)/N =?
                                                                                                                                                                      Я уже писал, что в последнем случае воронка (НОРМАЛЬНАЯ воронка) даёт 228.4 миллиона ваших дурацких сравнений. Вот это ФАКТЫ! Так доведите таблицу ДО КОНЦА, раз уж что-то вякаете про «факты», господин «программист»! ;)

                                                                                                                                                                      Блин, там написано ГДЕ ИМЕННО «в ОЗУ»! Я знаю, что Вы ничего не знаете, но читать хотя бы умеете? ВОт Вам прямо под нос цитата из заметки. Читать, как я уже говорил, следует слева направо:
                                                                                                                                                                      Элементы входного потока размещаются в ОЗУ, которое также заказывается динамически, блоками не менее максимального размера элемента (как правило намного большими), по исчерпанию уже заказанного ОЗУ. Каждый элемент предваряется паспортом вида «размер элемента в байтах» (определяется при чтении элемента) и «адрес следующего элемента» (изначально обнулён), то есть входной поток данных преобразуется в список. Такая организация данных позволяет проводить сортировку без перемещения самих элементов и обеспечивает экономное расходование памяти для хранения неоднородных данных (обычно это строки, которые могут отличаться по длине в тысячи раз), и под каждый из них выделяется лишь тот объём, который требуется данному конкретному элементу
                                                                                                                                                                      Доступно, господин «программист»?

                                                                                                                                                                      Вы не заметили, что я только отвечаю на цитаты из вашего текста?
                                                                                                                                                                      Нет, я заметил, что Вы уже попрощались тыщу лет назад, но никак не уйдёте. И заметил я это в самом начале «нулевых». И даже писал примерно в те же времена: «Время от времени какая-нить сопля имитирует демарш — дескать, не может она больше этого идиот[изм]а выносить. Не верьте — никуда она, нафиг, не денется».

                                                                                                                                                                      Нет, сударь — я никогда никогда никому ничего не запрещаю. Это мне частенько рот затыкают, а я белый и пушистый. Правда, распальцованных идиотов с детства не перевариваю, и даже недостатком это не считаю. ;)
                                                                                                                                                              0
                                                                                                                                                              И я в полном восхищении от программы rpsort — я просто не понимаю, КАК можно получить такую скорость! Да, допустим — я со своим слиянием сотен или тысяч файлов проигрываю версии, если все буферы ОЗУ сбрасывать в один файл, но ведь это всё равно ФАЙЛОВЫЕ операции! Всё равно приходится устраивать болтанку головками по дорожкам, а это ВРЕМЯ! Остаётся предположить, что либо программа всё-таки отхватывает больше ОЗУ, чем сортир для ДОС, либо сама операционка кеширует обращение к диску и основной объём операций происходит всё-таки в ОЗУ.

                                                                                                                                                              Вот вам великая тайна, как сортировать файлы произвольного размера, имея в наличии всего 2 килобайта памяти для строк. Как это оптимизировать для использования чуть большего количества памяти, думайте сами. На этом разговор действительно окончен.


                                                                                                                                                              Код онлайн


                                                                                                                                                              180 строк на C++
                                                                                                                                                              // quicksort for files
                                                                                                                                                              
                                                                                                                                                              #include <stdio.h>
                                                                                                                                                              #include <time.h>
                                                                                                                                                              #include <stdlib.h>
                                                                                                                                                              #include <string.h>
                                                                                                                                                              #include <sys/time.h>
                                                                                                                                                              
                                                                                                                                                              const int maxStringSize = 1024;
                                                                                                                                                              
                                                                                                                                                              int compareElements(char* a, char* b)
                                                                                                                                                              {
                                                                                                                                                                  return strcmp (a, b);
                                                                                                                                                              }
                                                                                                                                                              
                                                                                                                                                              int getValue(FILE* tmp, int n)
                                                                                                                                                              {
                                                                                                                                                                  int pos = 0;
                                                                                                                                                                  fseek(tmp, n * sizeof(int), SEEK_SET);
                                                                                                                                                                  fread(&pos, sizeof(int), 1, tmp);
                                                                                                                                                              
                                                                                                                                                                  return pos;
                                                                                                                                                              }
                                                                                                                                                              
                                                                                                                                                              void setValue(FILE* tmp, int n, int pos)
                                                                                                                                                              {
                                                                                                                                                                  fseek(tmp, n * sizeof(int), SEEK_SET);
                                                                                                                                                                  fwrite(&pos, sizeof(int), 1, tmp);
                                                                                                                                                              }
                                                                                                                                                              
                                                                                                                                                              char* loadString(FILE* input, int pos, char* str)
                                                                                                                                                              {
                                                                                                                                                                  fseek(input, pos, SEEK_SET);
                                                                                                                                                                  fgets(str, maxStringSize, input);
                                                                                                                                                              
                                                                                                                                                                  return str;
                                                                                                                                                              }
                                                                                                                                                              
                                                                                                                                                              // 2 KB
                                                                                                                                                              char midValue[maxStringSize];
                                                                                                                                                              char tmpValue[maxStringSize];
                                                                                                                                                              
                                                                                                                                                              void quickSort(FILE* tmp, FILE* input, int start, int end)
                                                                                                                                                              {
                                                                                                                                                                  int mid = (start + end) / 2;
                                                                                                                                                                  loadString(input, getValue(tmp, mid), midValue);
                                                                                                                                                              
                                                                                                                                                                  int tmpPos = 0;
                                                                                                                                                                  int i = start, j = end;
                                                                                                                                                              
                                                                                                                                                                  while (i <= j) {
                                                                                                                                                              
                                                                                                                                                                      while (compareElements(  loadString(input, getValue(tmp, i), tmpValue), midValue  ) < 0) {
                                                                                                                                                                          i++;
                                                                                                                                                                      }
                                                                                                                                                              
                                                                                                                                                                      while (compareElements(  loadString(input, getValue(tmp, j), tmpValue), midValue  ) > 0) {
                                                                                                                                                                          j--;
                                                                                                                                                                      }
                                                                                                                                                              
                                                                                                                                                                      if (i <= j) {
                                                                                                                                                                          tmpPos = getValue(tmp, i);
                                                                                                                                                                          setValue(tmp, i, getValue(tmp, j));
                                                                                                                                                                          setValue(tmp, j, tmpPos);
                                                                                                                                                              
                                                                                                                                                                          i++;
                                                                                                                                                                          j--;
                                                                                                                                                                      }
                                                                                                                                                                  }
                                                                                                                                                              
                                                                                                                                                                  if (start < j) {
                                                                                                                                                                      quickSort(tmp, input, start, j);
                                                                                                                                                                  }
                                                                                                                                                                  if (i < end) {
                                                                                                                                                                      quickSort(tmp, input, i, end);
                                                                                                                                                                  }
                                                                                                                                                              }
                                                                                                                                                              
                                                                                                                                                              const char *inputFileName = "input.txt";
                                                                                                                                                              const char *outputFileName = "output.txt";
                                                                                                                                                              const char *tmpFileName = "tmp.bin";
                                                                                                                                                              
                                                                                                                                                              int prepareSort(FILE* tmp, FILE* input)
                                                                                                                                                              {
                                                                                                                                                                  char s[maxStringSize];
                                                                                                                                                              
                                                                                                                                                                  int pos = 0;
                                                                                                                                                                  int N = 0;
                                                                                                                                                                  fseek(tmp, 0, SEEK_SET);
                                                                                                                                                                  fseek(input, 0, SEEK_SET);
                                                                                                                                                                  while (!feof(input)) {
                                                                                                                                                                      fgets(s, maxStringSize, input);
                                                                                                                                                                      if (feof(input)) break;
                                                                                                                                                              
                                                                                                                                                                      fwrite(&pos, sizeof(int), 1, tmp);
                                                                                                                                                                      pos = ftell(input);
                                                                                                                                                                      N++;
                                                                                                                                                                  }
                                                                                                                                                              
                                                                                                                                                                  fseek(tmp, 0, SEEK_SET);
                                                                                                                                                                  fseek(input, 0, SEEK_SET);
                                                                                                                                                              
                                                                                                                                                                  return N;
                                                                                                                                                              }
                                                                                                                                                              
                                                                                                                                                              void saveStringsAfterSort(FILE* input, FILE* output, FILE* tmp)
                                                                                                                                                              {
                                                                                                                                                                  fseek(input, 0, SEEK_SET);
                                                                                                                                                                  fseek(tmp, 0, SEEK_SET);
                                                                                                                                                              
                                                                                                                                                                  char str[maxStringSize];
                                                                                                                                                                  int pos = 0;
                                                                                                                                                                  while (!feof(tmp)) {
                                                                                                                                                                      fread(&pos, sizeof (int), 1, tmp);
                                                                                                                                                                      if (feof(tmp)) break;
                                                                                                                                                              
                                                                                                                                                                      loadString(input, pos, str);
                                                                                                                                                                      fputs(str, output);
                                                                                                                                                                  }
                                                                                                                                                              }
                                                                                                                                                              
                                                                                                                                                              void runFileSort()
                                                                                                                                                              {
                                                                                                                                                                  FILE* input = fopen(inputFileName, "r");
                                                                                                                                                                  FILE* output = fopen(outputFileName, "w");
                                                                                                                                                                  FILE* tmp = fopen(tmpFileName, "wb+");
                                                                                                                                                              
                                                                                                                                                                  int N = prepareSort(tmp, input);
                                                                                                                                                              
                                                                                                                                                                  quickSort(tmp, input, 0, N - 1);
                                                                                                                                                              
                                                                                                                                                                  saveStringsAfterSort(input, output, tmp);
                                                                                                                                                              
                                                                                                                                                                  fclose(tmp);
                                                                                                                                                                  fclose(output);
                                                                                                                                                                  fclose(input);
                                                                                                                                                              }
                                                                                                                                                              
                                                                                                                                                              void prepareTestFiles(int N)
                                                                                                                                                              {
                                                                                                                                                                  const char* symbols = "0123456789abcdefghijklmnopqrstuvwxyz";
                                                                                                                                                              
                                                                                                                                                                  srand(time(NULL));
                                                                                                                                                              
                                                                                                                                                                  int i, j;
                                                                                                                                                              
                                                                                                                                                                  const int maxStringLen = 20;
                                                                                                                                                                  char str[maxStringLen + 1];
                                                                                                                                                              
                                                                                                                                                                  FILE* input = fopen(inputFileName, "w");
                                                                                                                                                                  for (i = 0; i < N; i++)
                                                                                                                                                                  {
                                                                                                                                                                      int sLen = (rand() % maxStringLen) + 1;
                                                                                                                                                              
                                                                                                                                                                      str[sLen] = '\0';
                                                                                                                                                                      for (j = 0; j < sLen; j++) {
                                                                                                                                                                          str[j] = symbols[rand() % 36];
                                                                                                                                                                      }
                                                                                                                                                              
                                                                                                                                                                      fputs(str, input);
                                                                                                                                                                      fputs("\n", input);
                                                                                                                                                                  }
                                                                                                                                                              
                                                                                                                                                                  fclose(input);
                                                                                                                                                              }
                                                                                                                                                              
                                                                                                                                                              int main ()
                                                                                                                                                              {
                                                                                                                                                                  const int N = 1000;
                                                                                                                                                              
                                                                                                                                                                  prepareTestFiles(N);
                                                                                                                                                              
                                                                                                                                                                  runFileSort();
                                                                                                                                                              
                                                                                                                                                                  return 0;
                                                                                                                                                              }
                                                                                                                                                                –1
                                                                                                                                                                Сударь, Вашу «великую тайну» засуньте туда же, куда и свои поганые «new», «стек» и «плоский массив». Это даже не считая того, что первой же строчкой в «великой тайне» стоит:
                                                                                                                                                                const int maxStringSize = 1024;
                                                                                                                                                                И Вашу клинику на тему «остальные 99% это автоматическая сортировка в памяти в заранее написанной программе» туда же. Это никакие не «факты» — это Бред Сивой Кобылы! Воронка работает с файлами, rpsort работает с файлами, все виды дерьма, встроенного во все версии DOS-Win работают с файлами, выкопанная Вами сортировка от Линукса работает с файлами, базы данных, к Вашему сведению, это ТОЖЕ файлы. Так что Ваша «автоматическая сортировка в памяти в заранее написанной программе» годится разве что для онанизма с Вашими же бредовыми «тестами», да и то лишь потому, что результаты этого позора в этом случае можно не показывать.

                                                                                                                                                                Вот как проводят тесты НОРМАЛЬНЫЕ люди (даже на столь маразматическом материале, как Ваш). Извиняюсь, последняя версия сортира на этом тесте почему-то жутко тормозит, а посмотреть, что происходит, я здесь не могу (я в гостях в другом городе), так что воспользуюсь старой версией, которая была написана ещё 13 февраля, которая число перестановок считает точно, а не в миллионах, и у которой 32-разрядный счётчик этих идиотских сравнений переполняется. Итак:

                                                                                                                                                                N = 4, O(X) = 3, O(X)/N = 0.75
                                                                                                                                                                N = 8, O(X) = 17, O(X)/N = 2,125
                                                                                                                                                                N = 16, O(X) = 43, O(X)/N = 2,6875
                                                                                                                                                                N = 32, O(X) = 95, O(X)/N = 2,96875
                                                                                                                                                                N = 64, O(X) = 199, O(X)/N = 3,109375
                                                                                                                                                                N = 128, O(X) = 407, O(X)/N = 3,1796875
                                                                                                                                                                N = 256, O(X) = 823, O(X)/N = 3,21484375
                                                                                                                                                                N = 512, O(X) = 1655, O(X)/N = 3,232421875
                                                                                                                                                                N = 1024, O(X) = 3319, O(X)/N = 3,2412109375
                                                                                                                                                                N = 2048, O(X) = 6647, O(X)/N = 3,24560546875
                                                                                                                                                                N = 4096, O(X) = 13303, O(X)/N = 3,247802734375
                                                                                                                                                                N = 8192, O(X) = 26615, O(X)/N = 3,2489013671875
                                                                                                                                                                N = 16384, O(X) = 53239, O(X)/N = 3,24945068359375
                                                                                                                                                                N = 32768, O(X) = 106487, O(X)/N = 3,249725341796875
                                                                                                                                                                N = 65536, O(X) = 212983, O(X)/N = 3,2498626708984375
                                                                                                                                                                N = 131072, O(X) = 425975, O(X)/N = 3,24993133544921875
                                                                                                                                                                N = 262144, O(X) = 851959, O(X)/N = 3,249965667724609375
                                                                                                                                                                N = 524288, O(X) = 1703927, O(X)/N = 3,2499828338623046875
                                                                                                                                                                N = 1048576, O(X) = 3407863, O(X)/N = 3,24999141693115234375
                                                                                                                                                                N = 2097152, O(X) = 6815735, O(X)/N = 3,249995708465576171875
                                                                                                                                                                N = 4194304, O(X) = 13631479, O(X)/N = 3,2499978542327880859375
                                                                                                                                                                N = 8388608, O(X) = 27262967, O(X)/N = 3,24999892711639404296875
                                                                                                                                                                N = 16777216, O(X) = 54525943, O(X)/N = 3,249999463558197021484375
                                                                                                                                                                N = 33554432, O(X) = 109051895, O(X)/N = 3,2499997317790985107421875
                                                                                                                                                                N = 67108864, O(X) = 218103799, O(X)/N = 3,24999986588954925537109375
                                                                                                                                                                N = 134217728, O(X) = 436207607, O(X)/N = 3,249999932944774627685546875
                                                                                                                                                                N = 268435456, O(X) = 1112288452, O(X)/N = 4,14359737932682037353515625 (2 tmp-файла)
                                                                                                                                                                N = 536870912, O(X) = 2684354535, O(X)/N = 4,99999995343387126922607421875 (4 tmp-файла)
                                                                                                                                                                N = 1073741824, O(X) = 6172582694, O(X)/N = 5,74866560660302639007568359375 (7 tmp-файлов)

                                                                                                                                                                В последнем запуске моя воронка отсортировала МИЛЛИАРД строк Вашего идиотского теста! Даже не миллиард, а 1Г! Вот это ДЕЙСТВИТЕЛЬНО МОЯ воронка! Мною придуманная, мною запрограммированная, мною отлаженная. А те «компилирующиеся» бредни, которые криворукие «проверяльщики» нагло выдавали за «реализацию моего алгоритма» — это всего лишь бредни, никакого отношения в воронке не имеющие. Ну, и где там Великий и Ужасный Квик? Правильно: в зопе! ;)
                                                                                                                        0
                                                                                                                        Но линейность лучшего случая и без кода должна быть очевидна любому дебилу
                                                                                                                        Только не в случае внешей сортировки. Допустим, у вас вход 100 млн. отсортированных строк. А в память влезает только 1 млн. Это значит, нужно разбивать вход на блоки по 1 и потом многократно их сливать, что добавит log-множитель.
                                                                                                                          0
                                                                                                                          Увы… внешность сортировки здесь не существенна.

                                                                                                                          Тут даже не на блоки надо смотреть при слиянии, а на подсписки воронки. И на тот факт, что сливаются они на каждом шагу два самых коротких.

                                                                                                                          Допустим у нас имеется N=2^n-1 элементов (например, 31). И в результате некоторого разделения длина списков оказалась такой: 16, 8, 4, 2, 1.

                                                                                                                          Тогда за 3 перемещения в промежуточный список два самых коротких подсписка сольются в список длиной 3.
                                                                                                                          Затем понадобится максимум 7 перемещений, чтобы слить списки длиной 3 и 4 в один список длиной 7.

                                                                                                                          Итого 10 перемещений.

                                                                                                                          Затем потребуется еще 15 и 31 перемещение (максимум). Т.е. всего из воронки в результирующий список сольем за 56 перемещений.

                                                                                                                          Если взять не 31 элемент, а больше (но все так же разбить по степеням двойки), то получим что число перемещений, действительно, стремится к 2*N. Т.е. имеет временную сложность O(N).

                                                                                                                          Но при этом возникают другие моменты:

                                                                                                                          1. Как на самом деле распределяются длины подсписков?

                                                                                                                          2. Как растет алгоритмическая временная сложность слияния при другом (не обратно геометрическом) распределении длин подсписков?

                                                                                                                          3. Как растет алгоритмическая сложность поиска двух самых коротких подсписков? Возможно (т.к. число подсписков растет медленнее O(N)), она тоже тоже имеет сложность O(N).

                                                                                                                          Так что, слияние, в некоторых идеальных случаях, и в самом деле может выполняться за O(N). Но какие временные затраты потребуются для построения такого оптимального (с точки зрения слияния) распределения подсписков — отдельный вопрос.
                                                                                                                            0
                                                                                                                            1. Как на самом деле распределяются длины подсписков?
                                                                                                                            Как повезёт. Зависит от входного потока.

                                                                                                                            2. Как растет алгоритмическая временная сложность слияния при другом (не обратно геометрическом) распределении длин подсписков?
                                                                                                                            Да никак! Логарифм в худшем случае.

                                                                                                                            3. Как растет алгоритмическая сложность поиска двух самых коротких подсписков? Возможно (т.к. число подсписков растет медленнее O(N)), она тоже тоже имеет сложность O(N).
                                                                                                                            Это вообще копейки. Хотя в финальном вылизывании кода я даже от этого ушёл — в подавляющем большинстве случаев самые короткие подсписки не ищутся вообще. Только когда НАДО. :)
                                                                                                                            +1
                                                                                                                            Да ни один из других алгоритмов про внешнюю сортировку даже не заикается! Посмотрите, какой бред написан по этому поводу в Вики. Про сортировку строк, кстати, тоже.
                                                                                                0
                                                                                                со /A она генерирует полностью идентичный результат результату вашей программы (при условии досовых концов строк).
                                                                                        0
                                                                                        Файл antarctica-latest.osm

                                                                                        Оп-па. А размеры файлов-то различаются.



                                                                                        2 раза проверил. Программа никаких ошибок не выдает, VirtualBox тоже. Если у кого-то есть возможность, проверьте независимо пожалуйста, с учетом размера раздела в 2 Гб. Вдруг это VirtualBox глючит.
                                                                                          0
                                                                                          У сортира размер исходника и отсортированного файла совпадают байт в байт!
                                                                                            0
                                                                                            А размеры файлов-то различаются. 2 раза проверил. Если у кого-то есть возможность, проверьте независимо пожалуйста.

                                                                                            Отвечу сам себе.
                                                                                            Проверил еще раз в DOSBox. Подтверждаю — при нехватке места программа просто генерирует неправильный файл, не выдавая никаких ошибок.


                                                                                            Проверка в Windows 7 и выше: В программе "Управление дисками" создать виртуальный жесткий диск размером 2 Гб, подмонтировать в DOSBox, скопировать файл antarctica-latest.osm с переводами строк "\r\n" как file.i, запустить sortir.exe. Выходной файл file.o будет меньше на столько, сколько не хватило места.


                                                                                            Скриншот

                                                                                              –1
                                                                                              Сударь, Вы сколько раз собираетесь «разговор действительно оканчивать»? ;) И какой ещё хернёй намерены мучать мо воронку? Про свой долбаный Квик больше не заикаетесь? Объясняю: я эту программу написал ДЛЯ СЕБЯ. Я НЕ РАССЧИТЫВАЛ на её использование мудаками, которые запускают её в условиях заведомой нехватки места — это в наши-то годы, когда памяти ХОТЬ ЖОПОЙ ЖУЙ! Я не рассчитывал на такое использование даже при работе на своём первом компьютере, который имел винт размером 5 мегабайт. И дети мои, которые компьютер видели с рождения, ни разу в жизни подобной хернёй не маялись. Вы свалите, наконец, отседова или так и будете зудеть точнёхонько по моему описанию, что «никуда она, нафиг, не денется»? ;)
                                                                –4
                                                                И что за массив в пару сотен тысяч строк и в несчастные 4 миллиона сравнений? Даже ДОСовская версия сортирует такую хрень за доли секунды!

                                                                Ха-ха-ха! Хотел лайк поставить под Вашим комментом — «недостаточно кармы для голосования»! Вечером карма была 12 (хотя уже начали сбивать), сейчас — 1. Детский сад… а я-то сюда пришёл как в сообщество разработчиков!

                                                                Так что за данные? И откуда данные по времени?
                                                                  +3
                                                                  Так вам разработчики и поставили минусы.
                                                                    0
                                                                    Разработчики?! Разработчики обычно аргументируют свои действия, а не несут всякую полуграмотную ахинею вроде «это будет аналог сортировки вставками». :)
                                                                      +1

                                                                      Отлично, где ваши аргументы? У вас нет ни кода, ни конкретных замеров времени в сравнении с аналогами, ни даже замеров только вашей программы на разном количестве элементов. Есть только ваши заверения вида "она быстро работает, правда-правда, я проверял", к которым нет доверия, потому что вы заинтересованное лицо. И какая-то обфусцированная DOS-программа, в которой возможно обычный quicksort.

                                                                        +1
                                                                        У меня есть код, у меня есть программа, у меня есть описание алгоритма, даже с иллюстрациями, у меня есть несколько месяцев его эксплуатации, за которые я уже реально отсортировал десятки, если не сотни миллиардов строк — это как раз У ОСТАЛЬНЫХ нет нихрена! Кстати, вот тот скрин, который приведён выше, допускает лёгкую проверку: достаточно только переименовать получившийся file.o снова в file.i и запустить сортировку ещё раз. Для полностью отсортированного массива число сравнений должно быть на единицу меньше, чем число элементов (то есть последняя цифирь в диагностике должна быть N=0.2 — это число сравнений в миллионах). Если же она будет больше, значит, программа работала в режиме внешней сортировки, с образованием временных файлов при нехватке ОЗУ и их последующим слиянием. Тогда, возможно, время работы действительно будет таким, как указано — но это ведь далеко не равные условия! Я просто ЗНАЮ, что несчастные 231997 строк программа НЕ МОЖЕТ сортировать так долго!
                                                                          0
                                                                          У меня есть код
                                                                          А не факт, может у вас только и есть екзечничек, в котором вы подправили фамилию через hex-редактор. И впариваете нам тут чужую революционную разработку!
                                                                          у меня есть описание алгоритма
                                                                          Где, покажите? А… [разочарованно] вы про статью.
                                                                          даже с иллюстрациями
                                                                          Так покажите!

                                                                          Нет, тут явно что-то нечисто… Поповщиной попахивает!
                                                                            +1
                                                                            Да мне ПЛЕВАТЬ, чем там у Вас что «попахивает». Я пришёл на форум разработчиков — в первую очередь, программистов. Вернее, я думал, что пришёл именно туда. А попал на какую-то банду закомплексованных идиотов, которые строят разные мудацкие домыслы по поводу hex-редактора. Ссылку на иллюстрации я давал — там пошаговая картинка приведена, для особо одарённых. И я абсолютно уверен, что мой алгоритм выдерет, как котов любые другие на любых данных. Повторяю: я уже отсортировал МИЛЛИАРДЫ строк! Даже моя версия для DOS сортирует гигабайтные файлы! Да, довольно долго, ибо ОЗУ у неё с гулькин нос, и число временных файлов исчисляется тысячами. Но она, по крайней мере, РАБОТАЕТ — даже в таких условиях! А какой-либо аналог, работающий в режиме внешней сортировки, лично мне не известен вообще. А Вам, сударь? ;)
                                                                              +3
                                                                              Ничего Вы не давали. Это только Ваши голословные ничем не подкрепленные утверждения.

                                                                              Исходники в студию! Либо подробное пошаговое описание алгоритма в псевдокоде.

                                                                              И что-то я не видел, что кто-то из «банды», как Вы, сударь, имели выразиться, обозвал Вас нехорошим словом. А вот от Вас в адрес местного сообщества было и «бараны» и «идиоты».

                                                                              Может быть, Вы все же что-то попутали и Вам не сюда хотелось попасть?
                                                                                0
                                                                                ЩАЗ! А подробное пошаговое описание приведено! Кто там в параллельной ветке бахвалился, что у людей интеллект имеется? Ну так сохранилась ли хоть одна извилина, чтобы хотя бы описание алгоритма понять? ИМХО, любой школьник разберётся! По крайней мере, школьник из моих времён.

                                                                                Да, мне НЕ СЮДА хотелось попасть — мне хотелось попасть на разговор с профессиональными программистами. И не надо ВРАТЬ, сударь! Я никого не обзывал баранами и идиотами — я говорил про людей в целом. К которым, если Вы заметили, я и сам отношусь.
                                                                                  +3
                                                                                  Описание понятно. Непонятно на каком основании, на каких аналитических выкладках и статистических данных сделаны выводы о производительности. Насколько репрезантативны эти тестовые наборы, какие получились доверительные интервалы в каждой серии испытаний и т.д.
                                                                                    0
                                                                                    Я же русским языком говорил: я моделировал именно ХУДШИЙ случай (он очевиден любому идиоту) на массивах данных до ста миллионов строк, и он отличался от лучшего (заведомо линейного) не более, чем в два раза во всех экспериментах! А с «доверительными интервалами» или там «репрезентативностью»! пусть занимаются те, кому не лень — у меня на порядки более важные дела есть! Я же сказал: дайте хостинг под NT, мы сделаем там онлайн-сервис, и тестируйте хоть до посинения!
                                                                            0
                                                                            Ну, раз это все у вас есть, то Вам не составит никаких сложностей привести среднее (по результатам, допустим 10 или 100 испытаний) количество сравнений и перемещений/копирований элементов для наборов из 1000, 10000, 100000 и 1000000 случайных строк.

                                                                            Пока что я вижу грубейшую ошибку:

                                                                            Только одно последнее слияние (merge) выполняется за O(N) сравнений/перемещений. Если есть дополнительная память. Если надо слиять «на месте», то это сложно, но тоже возможно.

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

                                                                            Т.к. глубина деления на части имеет порядок O(log(N)), то общие затраты на сравнение/перемещение имеют порядок O(N*log(N)).

                                                                            Это что касается этапа слияний. Что касается этапа разделений, то ранее уже писали, что для нахождения места вставки каждого элемента следует произвести сравнение со всеми уже сформированными ранее диапазонами. Как растет среднее число диапазонов при увеличении N сказать пока что не могу. Но подозреваю сильно, что число диапазонов не остается равным одному. А раз так, то число сравнений на первом этапе (разделения) тоже никак не может иметь порядок O(N). Возможно, он будет тоже O(N*log(N)). А может быть и хуже.

                                                                            А еще после каждого слияния потребуется нахождение двух самых узких диапазонов. Для этого достаточно найти место для последнего результирующего диапазона, полученного слиянием, и переместить его на это место. Перемещение, в случае использования указателей памяти и динамических списков, может осуществляться быстро за O(1), но тогда поиск будет почти линейным (пробежать по цепочке динамического списка). Если же использовать упорядоченный массив, то поиск можно осуществить за O(log(M)) (M — число оставшихся поддиапазонов), зато перемещение будет иметь порядок O(M).

                                                                            Т.е. в любом случае эта операция по переупорядочиванию поддиапазона или по поиску двух самых узких поддиапазонов потребует затрат порядка O(M*log(M)). Правда, M увеличивается не линейно от N, но все равно это настораживает.
                                                                              +1
                                                                              Нет, не составит. Но если местная публика не верит даже приведёному описанию алгоритма, то чем тут помогу какие-то «испытания» — тем более, в моём же исполнении? А если Вы прочли хотя бы заметку, Вы должны были бы понять, что количество перемещений/копирований элементов для наборов из 1000, 10000, 100000 и 1000000 случайных строк РАВНО нулю! Насколько я помню, там об этом сказано открытым текстом.

                                                                              Ну, еслли ВЫ «пока что видите грубейшую ошибку», то это ещё не значит, что она там есть. Ежу понятно, что ЛЮБОЕ слияние (merge) выполняется за O(N) сравнений. И никакой дополнительной памяти" на это не требуется. Сливаемые элементы как раз и «стоят на месте», и это не просто «возможно» — это очень просто. Откуда Вам там мерещатся сложности — мне неведомо. Вы вообще программист? Ну хоть немножко?

                                                                              Да не надо, блин, сливать никакие «четвертушки и т.д.»! Всё определяется массчивом исходных данных. Это в классическом алгоритме слияния такое требуется — именно оттуда и логароифм! У «воронки» же такая ситуация встречается крайне редко. Блин, неу не пересказывать же мне здесь опять всю заметку!
                                                                              Какая, в задницу, «глубина деления на части»? Кто там чего «делит»? Какие, в задницу, «вставки»? Прочтите же заметку, наконец!
                                                                                +2
                                                                                Вот поэтому и не должно быть никакого «вашего исполнения». Критерий истинности результатов эксперимента — его повторяемость, независимая от личности экспериментатора.

                                                                                Чтобы алгоритм прошел независимую проверку. Иначе — это просто слова.

                                                                                P.S.: Кстати, на анимированной иллюстрации прекрасно видно, что при слиянии элементы не стоят на месте, а перемещаются. Поэтому, либо Вы лукавите, либо картинка не полностью соответствует описанию.
                                                                                А если наблюдаются противоречия даже на таком уровне, то как уж тут разобраться?
                                                                                  +2
                                                                                  Блин, да задолбали! В статье написано, что сортируются СПИСКИ, а что сортировка списков не требует перемещения элементов, должно быть понятно любому дебилоиду! По крайней мере, если он имеет хоть какое-то отношение к программированию.
                                                                                    +1
                                                                                    Это с какого такого перепугу такая ересь, любезный?

                                                                                    Да… сортировка списков не требует физического перемещения данных в памяти. Т.е. по большей степени не надо переписывать сами данные из одного элемента списка в другой. Вернее, можно, если размер этих данных меньше или сопоставим с размерами указателей списков, либо если программа не борется за звание чуда программистской мысли.

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

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

                                                                                    Так что, все не так просто, как на самом деле. И любое изменение порядка или расположения элементов в списке, независимо от того, переносятся ли сами данные (физическое перемещение) или просто изменяются связи между ними (логическое перемещение) — это всё суть операции перемещения. И при исследовании производительности алгоритмов считаются все эти операции перемещения без различия — физические они или логические.

                                                                                    Я же чувствовал, что здесь какой-то подвох. А оказалось — элементарное непонимание принципов работы сортировки списков.
                                                                                      –2
                                                                                      Господи, какая же бредятина! Вам, сударь, я тоже проставил битик: Вы НЕ программист. Комментировать же КЛИНИЧЕСКУЮ ахинею вроде «выделения/освобождения памяти, сборкой мусора и т.д.» не имею ни малейшего желания. Отойдите в сторонку, плиз!
                                                                                        +1
                                                                                        Неужели слова незнакомые попались? :D

                                                                                        Но это не должно было бы помешать Вам понять, что перемещение элементов при сортировке списков происходит. Или всё таки помешало?

                                                                                        Хотите, я вышлю вам Д. Кнута в формате DjVu? Пять томов?

                                                                                        Впрочем, это для Вас слишком сложно…

                                                                                        Начнем ликвидацию Вашей безграмотности с беллетристики. Н. Вирт — «Алгоритмы + структуры данных = программы», наверное, будет как раз. Там есть и про производительность и про выделение памяти и про сортировку списков. Для новичков и желающих научиться программированию будет как раз.

                                                                                        Не стесняйтесь — пишите свою почту в личку. Я скину — мне не жалко.
                                                                                          –4
                                                                                          Лапуль, если я заказываю память у ОС, и она мне эту память даёт, то это МОЯ память! А раз моя — НИ ОДНА БЛ&ДЬ не имеет права проводить там свою вонючую «уборку мусора» или заниматься какой-либо иной хернёй! Вам ХОЯ БЫ ЭТО — доступно, господин «программист»?
                                                                                            0
                                                                                            Ну я, конечно понимаю, что первое слово Вы писали своей жене (или мужу), но случайно адресовали мне.

                                                                                            Но, тем не менее, по поводу сборщика мусора:

                                                                                            https://ru.wikipedia.org/wiki/Сборка_мусора

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

                                                                                            Разумеется, Вы об этом знали?
                                                                                              +2
                                                                                              Так включите бестолковку-то, наконец! ЧТо там ОС делает со своей памятью ДО того или ПОСЛЕ того — мне глубоко НАСРАТЬ! Пока память МОЯ, ни одна сволочь не имеет права там ковыряться. А я не настолько дебил, чтобы там копировать.перемещать элементы. Доступно, господин «программист»?
                                                                                                0
                                                                                                А насколько Вы дебил, разрешите поинтересоваться? :D
                                                                                                  0
                                                                                                  Разрешаю. Настолько, что я ввязываюсь в полемику с полуграмотными идиотами.
                                                                                                    +1
                                                                                                    Ой, ну что ж Вы так, в самом деле? К чему эти экивоки, недосказанности… Какие-то «полуграмотные идиоты» откуда-то вылезли.

                                                                                                    Говорите уж прямо, как есть: «Тупым быдлом, недостойным целовать пыль в тени ног меня Великого Программиста» :)

                                                                                                    Так разобрались, наконец, почему в сортировке списков есть операции обменов?
                                                                                                      –2
                                                                                                      Сударь, Вы не программист — Вы обычный тролль. У меня на сайте есть «методика вытравливания» таких, как Вы, которую я с неизменным успехом применяю вот уже 20 лет. Ушли бы Вы отсюда по-хорошему, а? ;)

                                                                                                      Повторяю для особо одарённых: в МОЕЙ сортировке НЕТ никаких «операций обменов». Нет, не было и не будет.
                                                                                                        +1
                                                                                                        И куда ж Вы ее дели? :D

                                                                                                        Повторяю для ни разу не одаренных: любая операция по изменению порядка следования элементов (будь то в списке, будь то в массиве) хоть путем переписывания самих данных, хоть путем изменения связующих указателей — это и есть «операция перемещения» (или «операция обмена», если сортировка обменная).

                                                                                                        Читаем на Вашем сайте в описании алгоритма сортировки (этап слияния):
                                                                                                        на каждом шаге берётся меньший из текущих элементов подмассивов и отправляется в результирующий массив

                                                                                                        Каждое такое «оправляется» и есть операция перемещения. Пусть даже она не сопровождается физическим переписыванием самих данных в памяти, а, например, производится путем исключения элемента из цепочки одного списка и включением в цепочку результирующего списка.

                                                                                                        Кстати, путаница в терминологии (массив/список) тоже показательна. Все же это — совершенно разные структуры данных.

                                                                                                        Так что, книгу Н. Вирта выслать? Там про структуры данных весьма интересно написано. С чУдными картинками. Поможет Вам разобраться в разнице между сорторовками массивов и списков.

                                                                                                        P.S.: И, таки, да. Я совсем не программист. Ибо уже лет 25 не занимаюсь программированием профессионально — по заказу или по профессиональной необходимости. Так — по мелочам для души иногда…
                                                                                                        А по молодости лет бывало. И прикладные программы (пакеты статистической обработки, СУБД) и системные утилиты для DOS (в т.ч. всякие резидентные перехватчики/обработчики — для печати, для вывода дампа памяти, для замедления игр… программы-шутки, даже вирус один как-то написал). Но и тогда я себя программистом не считал. А всякие программы сортировки (от Пузырька до Хоара) писал на FORTRAN-IV и на PL-1 более 30 лет назад. По мере необходимости.
                                                                                                          –1
                                                                                                          Сударь, перестаньте корчить из себя программиста! Операция по изменению порядка следования элементов в списке — это сраный оператор присвоения! Грубо говоря, mov И НИЧЕГО БОЛЕЕ! Если какому-то идиоту вдарило в голову называть это «операция перемещения», то мой сортир-то здесь при чём? И «путаница в терминологии» тоже в Вашей голове — я рассматриваю массив исходных данных — да, организованный в ОЗУ в виде списка, Но никаких «совершенно разных структур данных» не вижу В УПОР! Массив данных, у которых каждый элемент тупо предваряется паспортом, всё равно массив! Когда элементы пишутся в блоки заказанного ОЗУ, они пишутся именно как массивы, последовательно. А когда идёт сортировка, те же самые данные (ФИЗИЧЕСКИ, блин, те же самые!) просто РАССМАТРИВАЮТСЯ как список! А книгу Вирта можете смело засунуть себе в задницу. Тем более, что то именно я писал лет 20 назад: «Вирт ничего не понимал в программировании — по крайней мере, в момент разработки языка. И Керниган писал в заметке „Почему Паскаль не является моим самым любимым языком программирования“: три из четырёх известных мне компиляторов с Паскаля написаны на С.

                                                                                                          Господи, да мне ПЛЕВАТЬ на Ваши справки и регалии! Тыщу раз повторял: „Можете обвешаться ими хоть в три слоя, хоть до пупа — всё равно я буду смотреть не на КТО сказал, а на ЧТО сказано! Здесь и сейчас Вы никакой не программист — Вы здесь просто полуграмотный тролль.
                                                                                                            +2
                                                                                                            Такая организация данных позволяет проводить сортировку без перемещения самих элементов и обеспечивает экономное расходование памяти для хранения неоднородных данных

                                                                                                            количество перемещений/копирований элементов для наборов из 1000, 10000, 100000 и 1000000 случайных строк РАВНО нулю!

                                                                                                            А когда идёт сортировка, те же самые данные (ФИЗИЧЕСКИ, блин, те же самые!) просто РАССМАТРИВАЮТСЯ как список

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


                                                                                                            код на c++ с qsort()
                                                                                                            #include <string.h>
                                                                                                            #include <stdio.h>
                                                                                                            #include <stdlib.h>
                                                                                                            
                                                                                                            int myCompare (const void * a, const void * b) {
                                                                                                                const char *pa = *(const char **)a;
                                                                                                                const char *pb = *(const char **)b;
                                                                                                            
                                                                                                                return strcmp(pa, pb);
                                                                                                            }
                                                                                                            
                                                                                                            int main() {
                                                                                                                const char *input[] = {"a", "orange", "apple", "mobile"};
                                                                                                                int stringLen = sizeof(input) / sizeof(char *);
                                                                                                            
                                                                                                                int i;
                                                                                                            
                                                                                                                for (i = 0; i < stringLen; ++i) {
                                                                                                                    printf("%p: %d: %s\n", input[i], i, input[i]);
                                                                                                                }
                                                                                                            
                                                                                                                printf("\n");
                                                                                                            
                                                                                                                qsort(input, stringLen, sizeof(char *), myCompare);
                                                                                                            
                                                                                                                for (i = 0; i < stringLen; ++i) {
                                                                                                                    printf("%p: %d: %s\n", input[i], i, input[i]);
                                                                                                                }
                                                                                                            }

                                                                                                            Результаты
                                                                                                            Как можно видеть, адреса строк остаются те же самые.


                                                                                                            0x4007b4: 0: a
                                                                                                            0x4007b6: 1: orange
                                                                                                            0x4007bd: 2: apple
                                                                                                            0x4007c3: 3: mobile
                                                                                                            
                                                                                                            0x4007b4: 0: a
                                                                                                            0x4007bd: 1: apple
                                                                                                            0x4007c3: 2: mobile
                                                                                                            0x4007b6: 3: orange
                                                                                                              0
                                                                                                              Ну и замечательно! Нормально запрограммировано! Это же не говорит о том, что элементы ПЕРЕМЕЩАЮТСЯ! Как считались, так и лежат, до самого выхода!
                                                                                                                0
                                                                                                                Это говорит о том, что это не преимущество вашего алгоритма, и не надо его за таковое выдавать. В любых сравнениях сортировок количество перемещений означает логическое количество, неважно, копируются там данные целиком или только указатели на них. Потому и называется «алгоритмическая сложность», независимая от природы данных.

                                                                                                                Еще раз — если вы считаете, что у вас нет никаких перемещений, то и в квиксорте их тоже нет. Но в остальном мире перемещения указателей тоже считаются перемещениями. Потому что в этом и заключается сортировка.
                                                                                                                  +1
                                                                                                                  При чём тут «преимущество алгоритма»? Просто тут разные «программисты» что-то говорят про «копирование/перемещение». Нет из в квиксорте — значит, нормальный программист писал. А вот в Тимсорте, насколько я помню, говорится именно о копировании, причём даже не элементов, а массивов!

                                                                                                                  Это теоретикам «неважно». А я — практик! А потому мне важно всё, включая время загрузки и выгрузки.
                                                                                                                    +1

                                                                                                                    Вы поняли, что я написал? Про копирование/перемещение говорят во всех сортировках. Да, даже если копируются/перемещаются только указатели. Потому что нет никакой разницы, перемещаются там четырехбайтовые инты или четырехбайтовые указатели на строку, в обоих случаях это занимает одинаковое время.

                                                                                                                      +2
                                                                                                                      Не важно, перемещаются там четырехбайтовые указатели или килобайтные нуль-терминальные строки. Важен не объем перемещаемых/переписываемых данных, а сам факт выполнения этих операций. Ибо, скоь быстрой не была бы операция, если она имеет временнУю алгоритмическую сложность O(N^2), то при росте N она «съест» все прочие операции, встречающиеся O(N*log(N)) раз, даже если они по отдельности и весьма «тяжелые».
                                                                                                              0
                                                                                                              Операция по изменению порядка следования элементов в списке — это сраный оператор присвоения! Грубо говоря, mov И НИЧЕГО БОЛЕЕ!

                                                                                                              И что? От того что Вы обосрали этот оператор, эта операция перестала быть операцией перемещения? От этого она куда-то исчезла, может быть, или перестала выполняться?

                                                                                                              Конечно, можете не называть это перемещением (хотя MOV это как раз от англ. Moving — двигать, перемещать). Но от этого данная операция перемещением быть не перестанет. Даже если это единственная ассемблерная инструкция «mov».

                                                                                                              И мой совет Вам: заведите счетчик на каждую такую инструкцию «неперемещения» элеметов между списками и посмотрите характер роста их числа выполнений в зависисмости от общего числа элементов. Вы будете «приятно» удивлены, что эти инструкции не только считаются (т.е. выполняются, ибо существуют), но и имеют рост, по меньшей мене как O(N*log(N)), но никак не O(N).

                                                                                                              Здесь и сейчас Вы никакой не программист — Вы здесь просто полуграмотный тролль.

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

                                                                                                              Но так уж случилось, что я «не программист» хоть немного разбираюсь в аналитике производительности программ, в отличие от Вас :)
                                                                                                              Так что, пожалуйста, не надо причислять меня к Вашей Лиге. Мне в ней скучно…
                                                                                                              А вот Вы сами — забавный. Давно не встречал таких пещерных поверхностных взглядов.
                                                                                                                –2
                                                                                                                Под mov, сударь, я имел в виду команду ассемблера. И ничего она никуда не «перемещает», а просто инициализирует некую ячейку неким значением. Повторяю в стотысячный раз: к меня НЕТ никаких перемещений! Как данные записались из входного потока, так они там и лежат, до самого конца. Я доступно излагаю? И в заметке русским языком написано: «Поскольку массивы в ОЗУ представлены в виде списков, слияние двух подмассивов происходит без перемещения самих элементов данных, что гораздо быстрее».
                                                                                                                  0
                                                                                                                  И в заметке русским языком написано: «Поскольку массивы в ОЗУ представлены в виде списков, слияние двух подмассивов происходит без перемещения самих элементов данных, что гораздо быстрее».

                                                                                                                  Вот не надо смешивать мягкое с теплым.
                                                                                                                  Вы имеете в виду, что не происходит перемещения самих данных, но это совсем не то же самое, что перемещение элементов.

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

                                                                                                                  И процедура объединения списков как раз очень активно выполняет операции перемещения. В зависимости от реализации элементы либо исключаются из обоих подсписков и заносятся в результирующий, либо исключаются из одного подсписка и вставляются в середину/начало/конец другого.

                                                                                                                  Так что, если Вы не перемещаете сами данные в памяти, это совершенно не означает, что не происходит их логического перемещения между списками или внутри них.

                                                                                                                  Под mov, сударь, я имел в виду команду ассемблера. И ничего она никуда не «перемещает», а просто инициализирует некую ячейку неким значением.

                                                                                                                  Ну а откуда взялось это значение? С потолка? Или было прочитано из какого-то другого места памяти?

                                                                                                                  Вот эта последовательность (вычислить адрес источника/прочитать из источника в регистр/вычислить адрес получателя/записать из регистра в получатель) и есть «операция перемещения». Пусть даже меняется не расположение данных в памяти, а только их принадлежность к тому или иному списку, либо порядок в одном и том же списке.

                                                                                                                  Вот и посчитайте зависимость количества таких блоков инструкций (или аналогичных) от количества входных данных. И постройте простенький график. Подали на вход 1000000 строк — инструкция MOV была выполнена столько-то раз. Подали на вход 10000000 строк — это число увеличилось. Причем, заметно нелинейно.
                                                                                                                    +1
                                                                                                                    Сударь, Вы меня утомили своими занудливыми глупостями. Считаете, что там где-то «перемещения» — ну и считайте! А мои элементы стоят на месте — от момента их загрузки в ОЗУ до момента их выгрузки в файл.
                                                                                                                      +1
                                                                                                                      Ну и пусть стоят на месте. Никто не запрещает. им стоят.

                                                                                                                      Но я-то как раз и «считаю» количество операций/инструкций, участвующих в переназначении элементов из одного списка в другой.

                                                                                                                      Если Вам так не нравится слово «перемещение», используйте «переназначение». Или «отправление».

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

                                                                                                                      Вот и посчитайте зависимость этих «отправлений» от количества входных строк.
                                                                                                                        0
                                                                                                                        Господи, ДА СРАЛ Я на Ваши «перемещения и отправления»! Меня интересует утилита сортировки, которая работает быстро и эффективно. Она у меня ЕСТЬ. А онанизмом с подсчётами чего бы то ни было занимайтесь сами — у меня других дел по горло.
                                                                                                                          +2
                                                                                                                          Не верим мы в Ваше бахвальство. Предьявите исходники, если она у Вас есть. Чтобы мы могли ее проанализировать и сделать экспертное заключение.

                                                                                                                          Все так делают, а Вы только хвастаетесь.

                                                                                                                          Можете срать и дальше, но, пожалуйста, занимайтесь этим у себя в сортире:

                                                                                                                          http://sint.wc.lt/sortir.htm

                                                                                                                          А сюда эту хрень не несите больше.
                                                                                                                            –1
                                                                                                                            Ха-ха-ха! Это не Вы, случайно, «эксперт»? Спасибо за пару минут весёлого смеха.

                                                                                                                            Да, кстати: что и как мне делать, я решаю САМ, без сопливых. ;)

                                                                                                                            Блин, опять карма -2… как же вы затрахали, быдло закомплексованное! Что пацаньё играется в погремушки с рейтингами — я уже писал администрации, еще до получения статуса члена сообщества, а что «К сожалению, не могу оставить коммент из-за злобных мерзавцев, набросавших мне минусов до уровня один пост в 24 часа» — это уже мне писали. Да ещё какую-то херню со значками «захабренный», да «отхабренный» на мыло присылают…
                                                                                                                              +1
                                                                                                                              По сравнению с Вами, дилетантом, — эксперт :)
                                                                                    0
                                                                                    И к вопросу насчет «немножко программист»…

                                                                                    Нет, я не программист. Если не считать, конечно, СУБД для родного предприятия для расчетов с потребителями. Примерно 60000 строк исходников на Clarion. 25 лет эксплуатации. Только в прошлом году отказались от нее — во первых, сложно стало работать с DOS-программой на современной Винде в режиме эуляции. Да и законодательство сильно изменилось, а подгонять старую прогу под новые веяния тяжко. Пришлось на «1С-УСТВ» переходить.

                                                                                    И если не считать участие в разработке «решателя» преферансных раскладов. Это тот же самый перебор с отсечениями, транспозиции, хэширование, кэширование, эвристики. Но, т.к. преферанс игра с неполной информацией, то интересно решать не конкретный расклад, а все 184756 возможных раскладов соперников.
                                                                                    Ну и в отличие от шахмат в преферансе больше двух игроков (правда, делятся на две антогонистические стороны, обычно) и ход не переходит строго от одной стороны к другой и обратно. И оценочной функции терминальной позиции не существует, в отличие от шахмат. Поэтому оценку хода надо делать не по достижимой в конце глубины перебора позиции, а значит меняются и подходы к кэшированию.
                                                                                    Но тут я не при чем, можно сказать. Я только алгоритмами помогаю. Реализацию делает другой человек, но всё никак не завершит. Хотя начинали мы с 60 секунд на 1 расклад, а пришли сейчас к 184756 раскладов за 6 секунд.

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

                                                                                    Так что, я совсем не программист. Но лет 25 назад еще для DOS писал программу демонстрации сортировок массивов без использования дополнительной памяти — столбики по экрану двигала/сортировала. Начиная от Пузырька и заканчивая Хоаром. А вот слияние (merge) «in place» придумать тогда не смог. Сделал что-то похожее, но работало не так эффективно. Но все равно лучше Шелла, но хуже Хоара.

                                                                                    Так что, не программист я :) Но предметом владею.
                                                                                      +2
                                                                                      Да, Вы не программист. Это очевидно. Но если Вы «только алгоритмами помогаете», до описания такого простого алгоритма, кака сортир, должны бы допереть?
                                                                                        0
                                                                                        Я то допер сразу. Но вот никак не мог допереть, почему Вы считаете, что его производительность O(N).

                                                                                        Теперь то понятно, что это из-за того, что Вам помстилось, любезный, что при сортировке списков перемещений не производится.
                                                                                          0
                                                                                          Да и не сразу не допёрли. ;) Впрочем, я уже всё сказал чуть выше.
                                                                                  +2
                                                                                  У меня есть код

                                                                                  Под словами "У вас нет ни кода" я подразумевал, что у вас нет кода, который вы можете предъявить. От того, что он у вас на диске лежит, пользы другим никакой. Как вы собрались мир менять, если никому его не показываете?


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

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

                                                                                    0
                                                                                    Совершенно верно: код я не собираюсь предъявлять. По моим представлениям, любой профессионал по приведённому описанию алгоритма способен за пару дней написать аналогичный код. Я и не хочу, чтобы мне верили! А Вы можете говорить, что Вам угодно, только ОПИСАНИЕ алгоритма, который работает быстрее моего приведите. :)
                                                                                      +4
                                                                                      Ну да, ну да… Удобная позиция для троллинга. Судя по Вашему поведению, если у этого аналогичного кода окажутся показатели хуже O(N), Вы скажете, что здесь нет профессионалов, а есть только кучка баранов и идиотов, не способных даже по подробному описанию написать правильный код. Мол алгоритм правильный, а неправильные те, кто его пытался повторить…

                                                                                      Так что, давайте опираться не на Ваши «представления», а на сложившиеся традиции. Не лезьте со своим уставом в чужой монастырь. Есть чем поделиться — делитесь. Не хотите выкладывать код — покиньте аудиторию. Хвастуны, пустословы и бахвальщики здесь не нужны.
                                                                                        0
                                                                                        Да какой у вас «монастырь»? Одна только ветка по ИИ чего стоит! Хотя я на ней всё-таки набрал эту дурацкую карму до 13, а здесь даже её сбросили до нуля! Кстати, если она уйдёт в минус, я лишусь способности что-то писать и комментировать? Если да, то не удивлюсь.
                                                                                        +1
                                                                                        А Вы можете говорить, что Вам угодно, только ОПИСАНИЕ алгоритма, который работает быстрее моего приведите

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

                                                                                          0
                                                                                          Так Вы же говорили про ВАШ алгоритм! ;) Или мне послышалось? А быстрая сортировка, если я правильно помню, даёт квадрат как раз для полностью отсортированных массивов? Нет? А у меня число сравнений в этом случае РАВНО N-1! Арифметика для первого класса… :)
                                                                                            0
                                                                                            Ну да, по Вашей же ссылке, чёрным по белому:
                                                                                            Сложность данной быстрой сортировки падает до O(n2), когда массив уже отсортирован или все его элементы равны.