Сортировка на односвязном списке за O(nlogn) времени в худшем случае с O(1) дополнительной памяти

    Все началось с данного топика на сайте gamedev.ru. Топикстартер предложил найти сортировку, которая обладает следующими свойствами:
    1. Время выполнения — гарантированные O(nlogn).
    2. Использование O(1) дополнительной памяти.
    3. Применимость для сортировки данных в односвязных списках (но не ограничиваясь ими).

    Оговорки на все три ограничения:
    1. Гарантированные O(nlogn) означают, что, например, среднее время быстрой сортировки не подходит — должно получаться O(nlogn) для любых, даже самых худших входных данных.
    2. Рекурсию использовать нельзя, поскольку она подразумевает O(logn) памяти на хранение стека рекурсивных вызовов.
    3. Произвольного доступа к элементам сортируемого массива нет, мы можем двигаться итератором от любого элемента только к соседнему (за O(1)), причем только в одном направлении (вперед по списку). Модифицировать сам список (перевешивать указатели на следующие элементы) нельзя.

    Вся информация, которую мы знаем об элементах массива — это то, что они все образуют линейно упорядоченное множество. Все, что мы можем делать — это сравнивать два элемента массива (за O(1)) и менять их местами (тоже за O(1)).

    Под катом можно узнать, что в итоге получилось у нас.

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


    Оговорки


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

    Практическое применение нашего алгоритма вряд ли возможно, задача имеет скорее академический интерес.

    Сбор информации


    Известные сортировки, которые сразу приходят на ум, не удовлетворяют всем трем пунктам одновременно, например:
    • Пузырьковая сортировка (bubble sort) подходит под пункты 2 и 3, но работает за O(n2).
    • Быстрая сортировка (quick sort) удовлетворяет пунктам 2 и 3 (пункт 2 — со знанием кое-какой идеи), но для пункта 1 дает O(nlogn) времени лишь в среднем и существуют входные данные, на которых она будет работать за O(n2).
    • Сортировка кучей (heap sort) удовлетворяет ограничениям 1 и 2, но, к сожалению, требует произвольный доступ к памяти.
    • Сортировка слияниями (merge sort) подходит под ограничения 1 и 3, однако требует O(n) дополнительной памяти.
    • Сортировка слияниями на месте (in-place merge sort) укладывается в ограничения 1 и 2 (есть даже ее stable вариант, но там жесть), но совершенно непонятно, как ее эффективно реализовать без произвольного доступа к памяти.


    Median of Medians или алгоритм BFPRT


    В первом же комментарии товарищем FordPerfect был предложен не очень известный в широких кругах алгоритм Median of Medians. Другое его название BFPRT от фамилий ученых, его придумавших: Мануель Блюм, Роберт В. Флойд, Вон Пратт, Рональд Л. Ривест и Роберт Е. Тарьян. Алгоритм описан на википедии (ru, en), а также в Кормене, но я немного расскажу про него, поскольку на википедии он описан настолько топорно, что я понял его суть только после сопоставления русской и английской версии (и еще пришлось заглянуть в оригинальную статью). Да и на Хабре его описания еще не было. В Кормене, если что, описание нормальное, но то, что этот алгоритм там есть — я узнал уже позже. Если вы уже знаете этот алгоритм — данный кусочек статьи можно пропустить.

    Алгоритм Median of Medians позволяет найти k-ую порядковую статистику на любом массиве за линейное время в худшем случае. В библиотеке C++ STL имеется похожий алгоритм std::nth_element, который тоже находит k-ую порядковую статистику за линейное время, но в среднем, поскольку в его основе лежит алгоритм Quickselect. Последний по сути представляет собой quick sort, в котором на каждом шаге мы спускаемся только по одной ветви рекурсии (подробнее про Quickselect можно почитать здесь и здесь). Median of Medians является модификацией алгоритма Quickselect и не допускает выбора плохого элемента для «ветвления», который в худшем случае приводит к квадратичному времени работы.

    Зачем нам нужен этот Median of Medians? Да все довольно просто — с его помощью можно за линейное время найти медиану массива (n/2-ую порядковую статистику) и именно по этому элементу ветвить алгоритм быстрой сортировки. Это приведет к тому, что quick sort будет работать за O(nlogn) не в среднем, а в худшем случае.

    Описание алгоритма Median of Medians. Входные данные: массив (заданный, например, первым и последним элементами списка) и число k — какой по счету элемент нам требуется найти.
    1. Если массив достаточно маленький (меньше 5 элементов) — в лоб сортируем его пузырьком и возвращаем k-ый элемент.
    2. Разбиваем все элементы массива на блоки по 5 элементов. На возможный неполный последний блок пока не обращаем внимания.
    3. В каждом блоке сортируем элементы пузырьком.
    4. Выделяем подмассив из средних (третьих) элементов каждого блока. Можно их просто перенести в начало массива.
    5. Рекурсивно запускаем Median of Medians для этих [n/5] элементов и найходим их медиану (n/10-ый элемент). Этот элемент назовет опорным (pivot element).
    6. Делаем процедуру разделения, вероятно всем знакомую по алгоритмам quick sort и quickselect: перемещаем все элементы меньше опорного в начало массива, а все элементы больше — в конец. Элементы из возможного неполного блока в конце массива тоже учитываем. Итого, получаем три блока: элементы меньше опорного, равные ему и больше него.
    7. Определяем в каком из блоков нам нужно искать наш k-ый элемент. Если он во втором блоке — возвращаем любой элемент оттуда (они все равно все одинаковые). Иначе рекурсивно запускаем Median of Medians для этого блока с возможной поправкой на номер элемента: для третьего блока нужно из числа k вычесть длины предыдущих блоков.


    Рассмотрим на примере что тут происходит. Пусть имеется массив и мы хотим найти его медиану:



    Тут 27 различных чисел от 1 до 27. Мы ищем 14-ый по счету элемент. Разобьем элементы на блоки длины 5 и отсортируем числа внутри каждого блока:



    Медианы каждого блока выделены желтым. Перемещаем их в начало массива и рекурсивно запускаем наш алгоритм для поиска медианы в нем:



    Я не буду расписывать что там происходит внутри рекурсии, ясно одно — искомой медианой будет число 12.



    Это число 12 — опорный элемент или медиана медиан — обладает следующим замечательным свойством. Давайте вернемся на пару картинок назад и мысленно переместим наши блоки следующим образом:



    Все столбики отсортированы по среднему элементу, плюс элементы в каждом столбике тоже отсортированы. Мы можем видеть, что примерно 30% элементов (3/10n + O(1), если быть точным), которые выше и левее опорного элемента, не больше, чем он. Аналогично для примерно 30% элементов ниже и правее опорного элемента — они не меньше, чем он. Это означает, что когда мы осуществим процедуру разделения, примерно 30% всех элементов обязательно окажутся левее опорного элемента и примерно 30% — правее:



    На самом деле, тут небольшая неточность: нам повезло с тем, что элементов, равных опорному, ровно одна штука. Если таких элементов много, то они все образуют целый блок и куда именно встанет опорный элемент — непонятно. Но это и не важно на самом деле. Мы знаем, что элементов, которые не меньше опорного элемента, — не менее 30%, значит элементов, которые строго меньше опорного элемента, — не более 70%. Аналогично — элементов, которые строго больше опорного элемента тоже не более 70%. Таким образом, размеры первого и третьего блоков из описания алгоритма выше всегда будут иметь длину не более 7/10n+O(1)!



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

    Какова сложность рассмотренного нами алгоритма?

    Пусть T(n) — число операция алгоритма Median of Medians в худшем случае для массива длины n. На каждом шаге алгоритм дважды рекурсивно вызывает самого себя. Первый раз — для нахождения медианы медиан на массиве длиной n/5 + O(1) элементов. Второй раз — уменьшая пространство поиска, при этом в худшем случае размер массива уменьшается до 7/10n + O(1). Все остальные операции требуют линейного времени. Итого получаем соотношение:

    T(n) = T(2/10n) + T(7/10n) + Cn, где C — некоторая константа.

    Разложим это соотношение:

    T(n) = Cn + (2/10+7/10)Cn + (2/10+7/10)(2/10+7/10)Cn +… = Cn * ∑i=0..∞ (9/10)i = 10Cn = O(n)

    Отлично! Алгоритм имеет линейную сложность!

    Median of Medians несложно реализовать на списках с использованием рекурсии, что дает нам хорошее частичное решение изначальной задачи: гарантированная сортировка за O(nlogn) на односвязном списке с использованием O(logn) памяти.

    Код.

    Давайте теперь избавляться от рекурсии.

    Flat quick sort


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

    В данном разделе будет описана идея, которую предложил на форуме gamedev.ru товарищ FordPerfect (да, по сути все идеи данной статьи не мои — я просто разместил объяву). Первоисточник идеи неизвестен, гугл по этому поводу по большей части молчит и выдает много ссылок на так называемый iterative quicksort, где сплошь и рядом эмулируется стек (впрочем, тут нашлось обсуждение похожей идеи), а сам FordPerfect говорит, что ее придумал его одногруппник за 40 минут раздумий над задачей «quicksort с O(1) памяти». Название «Flat quick sort» тоже самопальное, возможно этот алгоритм известен под другим названием.

    Давайте вспомним как работает обычная рекурсивная быстрая сортировка. Входные данные: массив, заданный, например, двумя итераторами на начальный и конечный элементы односвязного списка.
    1. Проверка за один проход: если массив уже отсортирован, то делать нечего — выходим.
    2. Выбираем элемент (pivot) для процедуры разделения — обычно случайно, но для нашего случая — медиану с помощью алгоритма Median of Medians.
    3. Творим процедуру разделения — получаем три блока: элементы, что меньше, чем pivot; элементы, что равны ему; и элементы больше.
    4. Рекурсивно запускаем быструю сортировку для первого и третьего блоков.


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

    Заметим следующую вещь: любой элемент первого блока меньше любого элемента второго блока, а любой элемент второго блока меньше любого элемента третьего блока.

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

    Теперь алгоритм быстрой сортировки можно переписать следующим образом:
    1. Создадим указатели X и Y. Пусть указатель X указывает на начало массива, а указатель Y — на его конец. Еще создадим указатель Z, который будет указывать на конец текущего блока. Изначально Z=Y.
    2. Бесконечно выполняем следующие действия:
      1. Если текущий блок X-Z уже отсортирован — ищем следующий блок. Перемещаем X на элемент, следующий после Z. Если X переместить нельзя, поскольку Z=Y — выходим из цикла. Теперь ищем ближайший элемент a после X, который больше элемента, на который указывает X. Если такого нет — делаем Z=Y, иначе перемещаем Z на элемент перед a.
      2. Выполняем обычные действия быстрой сортировки: выбор элемента для разделения и само разделение. Получаем три блока.
      3. Делаем блокофикацию третьего блока: ищем в нем максимальный элемент и перемещаем его в начало.
      4. Перемещаем Z на конец первого блока.


    Теперь рассмотрим этот алгоритм на примере:



    Где-то я уже видел этот массив… Давайте расставим указатели X, Y и Z:



    Блок X-Z не отсортирован. Тогда найдем медиану:



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



    Получились 3 блока. Блокофицируем последний блок и переместим Z в конец первого блока:



    Теперь начинаем все с начала. Текущий блок X-Z не отсортирован, значит ищем в нем медиану:



    Выполняем процедуру разделения:



    Блокофицируем третий блок и перемещаем Z в конец первого блока:



    Опять смотрим на X-Z:



    Нам повезло! Блок отсортирован, поэтому его можно оставить в покое и искать следующий блок. Указатели X и Z переместятся следующим образом:



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



    Проверяем на упорядоченность — увы, на это раз не повезло, придется упорядочивать. Находим медиану, а потом делаем процедуру разделения:





    Далее, мы перейдем к блоку [8,9], он отсортирован, поэтому X и Z сдвинутся на блок [10], который тоже отсортирован, после чего алгоритм будет рассматривать блок [13, 11, 12], в котором все уже совсем тривиально. Разбор сортировки второй половины массива предлагается выполнить читателю самостоятельно.

    Код.

    Приблизительный Median of Medians с O(1) дополнительной памяти


    К сожалению, с Median of Medians такой фокус, как использование максимального элемента для идентификации блоков в flat quick sort, не пройдет, ибо элементы массива каждый раз перемешиваются непонятно каким образом. Здесь мы будем использовать другой фокус.

    На самом деле, чтобы заставить quick sort работать за гарантированные O(nlogn), не обязательно находить точную медиану для этапа разделения. Достаточно найти что-то приблизительное. Если дать гарантию, что первый и третий блок после этапа разделения не будут превосходить Cn для некоторого конкретного С<1, quick sort будет работать за O(nlogn). Даже для C=0.99. С лютой бешеной скрытой константой, но O(nlogn)!

    Поэтому мы модифицируем Median of Medians так, чтобы он находил медиану с некоторой погрешностью K = O(log2n). То есть будет найден элемент, порядковый номер которого где-то в границах от n/2-K/2 до n/2+K/2. Поскольку K порядка степени логарифма, легко найдется такое (конкретное) n, начиная с которого отрезок [n/2-K/2, n/2+K/2] будет лежать, скажем, между 1/4n и 3/4n. Для всех меньших n сортировать можно просто пузырьком.

    Почему K = O(log2n)? Да мы просто используем K элементов массива для того, чтобы хранить в них всю необходимую информацию по стеку (идея, опять же, товарища FordPerfect). Уровней рекурсии O(logn), на каждом из них нам нужно сохранить O(1) чисел на O(logn) бит. А медиану для quick sort найдем среди оставшихся N-K элементов.

    Каждый бит представляется двумя последовательными различными элементами массива. Если первый из них меньше второго — бит хранит состояние 0, иначе — 1 (или наоборот). Первая задача, которую нам нужно решить — это найти K/2 пар различных элементов массива и понять что делать если столько пар не найдется.

    Делается это очень просто. Пусть итераторы X и Y указывают на первый элемент массива. Будем двигать Y вперед пока не найдем элемент, не равный X. Если нашли — подвинем X вперед, поменяем местами элементы, на которые указывают X и Y, подвинем X еще раз вперед (+ еще надо обработать мелкий случай — подвинуть Y вперед, если он оказался перед X). И так пока не найдем K/2 пар. Что если Y уже дошел до конца массива, а K/2 пар еще не нашлись? Это означает, что все элементы от X до Y включительно одинаковые! (Довольно просто проверить, что этот инвариант сохраняется на протяжении выполнения всего алгоритма). Тогда в качестве опорного элемента можно сразу выбрать один из этих элементов. Если выбрать K < n/2, этот опорный элемент будет точной медианой.

    Теперь вопрос: а не поломает ли работа со стеком асимптотику алгоритма? Это очень хороший вопрос, поскольку на первый взгляд кажется, что вершин в нашем рекурсивном дереве порядка O(n) и на каждую вершину нам надо O(log2n) операций со стеком. Неужели асимптотика ухудшается до O(nlog2n) для нашего Median of Medians (и до O(nlog3n) для всего алгоритма)? Тут все несколько сложнее.

    Чтобы посчитать точное число вершин в дереве надо решить следующую рекурренту:

    N(n) = N(n/5) + N(7N/10) + 1
    N(n) = 1 для n<C

    Что-то подобное можно было видеть выше, но замена Cn на 1 делает рекурренту несколько более сложной для вычисления. На помощь приходит метод Акра-Бацци. Наша рекуррента подходит всем условиям и после всех соответствующих подстановок получаем, что число вершин N(n) растет как O(n0.84) (Θ(n0.839780...) если быть более точным). Итого временная сложность алгоритма составляет O(n + n0.84log2n) = O(n).

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

    Насколько непрактичен предложенный алгоритм? Вот некоторые выкладки:

    Пусть мы хотим получить отклонение не более 1/4n от настоящей медианы (то есть K < n/2). Тогда нам надо забить стек на 3[logn] уровней рекурсии (тут log — двоичный, 3 из-за того, что (3/4)3 < 0.5, а [x] — это округление числа x вверх до ближайшего целого). На каждый уровень рекурсии нам надо 2[logn] бит — надо хранить текущую длину массива, какой по порядку элемент мы ищем сейчас (это число всегда укладывается в [logn]-1 бит) и еще один бит на поддержание порядка обхода дерева рекурсии (надо помнить из какой ветви рекурсии мы вернулись). На каждый бит 2 элемента, итого надо 12[logn]2 элементов под стек.

    Теперь решаем уравнение: 12[logn]2 < n/2 или 24[logn]2 < n. Надо найти такое n', что для любого n>=n' 24[logn]2 < n. Такое n' порядка 3500. То есть для n<3500 надо сортировать пузырьком.

    Предел для n, начиная с которого K всегда не превышает n — 1500, то есть для n<1500 сортировка даже не заработает (не хватит элементов для эмуляции стека), тут уже без раздумий надо пользоваться пузырьком. Впрочем, если поиграться константами, то, вероятно, можно эту оценку улучшить.

    Код.

    Код


    Все ссылки на код по всей статье в одном месте:


    Почитать


    1. Обсуждение алгоритма на gamedev.ru.
    2. Median of Medians на википедии (en, ru).
    3. Про Quickselect можно почитать здесь и здесь.
    4. Метод Акра-Бацци на википедии.
    5. Manual Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. Time Bounds for Selection. (pdf, eng)
    6. S.Battiato, D.Cantone, D.Catalano and G.Cincotti. An Efficient Algorithm for the Approximate Median Selection Problem. (pdf, eng) — быстрый приблизительный вероятностный Median of Medians
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 85

      –14
      Есть ли реализация на ruby?
        +3
        Увы, пока только на C++
          –5
          Ой, а что происходит? рубихейтеры? теперь я точно найду время переписать на руби это решение.
          +1
          Если снять требование к памяти, можно использовать какой-нибудь вариант сортировки подсчетом. Время выполнения может быть равным двум проходам по массиву, а в некоторых случаях и меньше.
            –14
            А можно глупый вопрос? В чём измеряется «время» и «память»? Просто все эти О(1), О(n) и прочее — немного абстрактны и непонятны.
              +3
              --О(1) означает что как сильно бы вы не увеличивали размер входных данных — время выполнения всегда константа

              О(n) означает что время выполнения растет линейно с ростом размера входных данных
                –30
                O большое — количество операций для завершения алгоритма. Число платформенно независимое.

                Скажем, если вы тратите 1мс на операцию на своей архитектуре, то на сортировку десяти миллионов элементов массива алгоритмом O(N) вы затратите 10000000*0.001 секунд, алгоритмом O(logN) порядка 16*0.001 секунд.

                Подробнее --> в википедию.
                  +14
                  Если мне не изменяет память, то О (О большое) — термин из математического анализа, который задаёт класс функций, ограниченных относительно заданной.
                    0
                    кто-то может совсем не знать математического анализа, поэтому надо какое-то более общечеловеческое определение
                    +13
                    Что я только что прочитал…
                      –7
                      Ну, наверное, минусующие могут объяснить гораздо проще и доступнее и при этом строго показать, что O не связано с числом операций?

                      Если вам проще накидать минусов, чем помочь спрашивающему яснее, чем сделал я — давайте, ещё накидывайте. Так держать!

                      «Гики всех стран — разъединяйтесь через презрение!»
                        +6
                        Точное знание количества операций, выполненных алгоритмом, не играет существенной роли в анализе алгоритмов. Куда более важным оказывается скорость роста этого числа при возрастании объема входных данных. Она называется скоростью роста алгоритма. Небольшие объемы данных не столь интересны, как то, что происходит при возрастании этих объемов. Интересен только общий характер поведения алгоритмов, а не подробности этого поведения.
                          0
                          В случае сортировки для анализа алгоритмов может иметь значение точное число выполненных операций сравнения и обмена. Мы знаем, что для хороших алгоритмов оно растёт, как C*n*log_2(n), но какова константа C? 1.7? 1.1? Или держится меньше 1?
                          Для небольших объёмов тоже важно. За сколько сравнений можно найти медиану из 5 чисел? А из 7? От этого сильно зависит, на сколько частей делить массив для алгоритма «медианы медиан».
                            0
                            В случае сортировки любой алгоритм порядка O(NlogN) является наилучшим, и его можно считать оптимальным. Более того, любой алгоритм, решающий задачу сортировки быстрее, чем за O(NlogN) операций, не может работать правильно.
                              +1
                              А как же тогда сортировка подсчетом?
                                0
                                Да, тут мне следовало уточнить, что O(NlogN) это нижняя граница для алгоритмов сортировки работающих путем последовательного попарного сравнения элементов списка.
                                  0
                                  ripatti проблема в том, что сортировка подсчетом требует O(k) дополнительной памяти, где k — размер интервала чисел, которые сортируются. Т.е. если у нас могут быть числа от минус миллиона до плюс миллиона, то нам нужно два миллиона битов (а если мы сортируем словарь, а не просто числа, то нам потребуется гораздо больше, но опять же O(k) памяти). Проблему с памятью можно решить например так:
                                  а) разбиваем интервал 0..k на два (0..k/2 и k/2..k)
                                  б) делаем два прохода сортировок. В первом проходе делаем сортировку для чисел только из первого интервала, во втором делаем сортировку для чисел только из второго интервала
                                  в) объединяем результаты (поскольку у нас интервалы не пересекаются, то это сделать просто)
                                  Если мы все еще не решили проблему, то каждый из полученный подинтервалов делится еще раз на два, для подподинтверала делается два сортировка, результаты подподинтервалов объединяются, потом объединяются результаты подинтервалов. Итого получаем время O(NlogK) если хотим снизить потребление памяти до фиксированного. Ну как-то так.
                                    0
                                    Да я в курсе как она работает. Мне просто фраза
                                    любой алгоритм, решающий задачу сортировки быстрее, чем за O(NlogN) операций, не может работать правильно

                                    в глаза бросилась. Это утверждение справедливо только когда мы не знаем дополнительной информации об элементах и умеем только их попарно сравнивать и обменивать. Товарищ Informatik уже исправился.
                            +2
                            habrahabr.ru/post/247053/#comment_8211603
                            habrahabr.ru/post/247053/#comment_8211719
                            habrahabr.ru/post/247053/#comment_8212291

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

                              ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое

                              Читаем: «В частности: фраза «сложность алгоритма есть O(f(n))» означает, что...»

                              Смотрим, что такое «вычислительная сложность». Оп-па:

                              ru.wikipedia.org/wiki/Вычислительная_сложность

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

                              Ещё раз: «равная максимальному количеству элементарных операций».

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

                              Так что, коллеги, реплики по поводу математической безграмотности моего объяснения кое-кто поторопился. Моё пояснение хоть и упрощено, но наглядно и достоверно показывает что означает O.

                              Указанные «неидеальные комментарии» ничего внятного не проясняют, кроме как жестами показывают «ого-го как сложно!..»
                                +2
                                Вы правда не понимаете, в чем разница между этими определениями?
                                Википедия
                                фраза «сложность алгоритма есть O(f(n))» означает, что с увеличением параметра n, характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на f(n)
                                EndUser
                                O большое — количество операций для завершения алгоритма. Число платформенно независимое.
                                  –3
                                  Я прекрасно вижу, что семантически фраза означает «когда сложность алгоритма равна O(f(n)), то...» (и далее описываются свойства длительности от n с уже принятой договорённостью «сложность=О»), что фактически означает «Примем сложность равной О. Тогда...»

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

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

                                  И да, я знаю, что прикладному математику нужно более строго определение. Но спрашивающий — не математик и математиком скорее всего уже не будет.
                                    0
                                    Это не отменяет того факта, что спрашивающему нужно корректное определение. Потому что по вашему выходит, что сложность алгоритма может быть O(2n+5), и это вроде как лучше, чем O(3n+6).
                                      –5
                                      Ну так на вашем примере «2n+5 против 3n+6» это и действительно лучше, начиная от 1 до ∞.
                                      Мы ведь не рассматриваем 0 количество данных? Или отрицательную длину массива?

                                      Так что корректность соблюдается.

                                      Конечно, можно было бы добавить, что _обычно_ берётся наивысшая степень полинома, а остальные _обычно_ отбрасываются. Но для больших чисел это само по себе сработает.

                                      А так, да, я видел записи навроде вашей «O(2n+5)» у нормальных лекторов. Так что запись валидна.
                                        +4
                                        O(2n+5) у нормального лектора может быть написано только как промежуточный результат. И оно ничем не лучше O(3n+6) — потому что и то, и другое строго равно O(n).

                                        Внутри O-нотации, к сведению, отбрасываются не только младшие степени полинома — но и константные множители. И это отбрасывание совершенно не связано с большими числами — и именно в этом ваша ошибка и заключалась.

                                        К примеру, вот это утверждение неверно:
                                        Скажем, если вы тратите 1мс на операцию на своей архитектуре, то на сортировку десяти миллионов элементов массива алгоритмом O(N) вы затратите 10000000*0.001 секунд

                                        Этот алгоритм может проработать 10000000*0.001 секунд — а может и 10000000*1 лет. Все эти подсчеты вести бесполезно — просто потому что во фразе O(N) не указана константа. Никому не известно, сколько операций делает этот алгоритм.
                                  0
                                  Ваша упрощение не отражает того факта, что это лишь оценка сверху, причем с точностью до константы, а не точное значение числа операций. Например, функция 4n принадлежит как к классу (множеству функций) O(n), так и к классам O(n log n), O(n2) и так далее. Не обижайтесь, но по вашим постам складывается ощущение, что вы сами не понимаете (или понимаете очень поверхности), что это понятие значит.
                            +1
                            Очень грубо говоря, асимптотика показывает, что сложность вычисления определенной функции не будет расти стремительнее, чем заданная O(). Тоесть, если сложность O(n), то при линейном увеличении объема данных, сложность вычисления ф-ции, которая работает с этим объемом данных, не будет расти быстрее линейной зависимости.

                            Прошу прощения за дилетантскую форму изложения, я профан в CS.
                            +1
                            Мы не знаем природы элементов, может там какие-нибудь строчки или еще какая жесть.
                              –3
                              Хмм… То-есть вот совсем неизвестно что за элементы в массиве? А как можно сравнивать элементы неизвестной природы? Каким образом задается их отношение больше-меньше-равно-несравнимо?
                                +3
                                Пользовательским компаратором. Представьте, что вы пишете обобщенную сортировку для стандартной библиотеки. И потом пользователь сможет ей отсортировать, скажем, строчки, в своем компараторе прописав «сравнивай их лексикографически, предварительно развернув задом наперед».
                                  0
                                  Известно, что все элементы одинаковой длины (например, указатели), и что сравнение транзитивно. Время на сравнение элементов, а также на их копирование считается равным О(1) — вне зависимости от истинной сложности. Сложность сортировки вычисляется в «числе сравнений и копирований». Допустимо ли в память O(1) включать память, достаточную для хранения хотя бы одного элемента — вопрос спорный. qsort из stdlib.h обходится без неё.
                                    0
                                    qsort из stdlib.h обходится без неё.
                                    Сомневаюсь, что это правда, она должна использовать её для обмена двух элементов местами (размер элемента в байтах передается как параметр).
                                      0
                                      немного xor'овой магии, и можно вообще без выделения памяти обойтись при условии элементов одинакового размера) правда размер все равно пригодится
                                        +1
                                        Нужна память O(1) на индексы и указатели. А xor не нужен (он агрессивнее использует память): два объекта в памяти можно обменять байт за байтом.
                                          0
                                          ну конкретно для обмена двух элементов местами при сортировке можно обойтись таким:
                                          if( x!=y ) {
                                          x ^= y;
                                          y ^= x;
                                          x ^= y;
                                          }
                                          и никакой памяти дополнительной не надо ) причем даже для указателей на строки должно нормально работать)) речь же шла только о использовании памяти при обмене, понятно что в целом для сортировки доп память понадобится, если совсем не извращаться
                              0
                              Не очень понятно, как на последовательности выполнять «процедуру разделения»: «все элементы меньше опорного в начало массива, а все элементы больше — в конец.» Обычно элемент, больший опорного, кладут по указателю, изначально указывающему на последний элемент сортируемого участка, а этот указатель сдвигают на предыдущий элемент. Но мы двигаться назад не можем!
                              Насчёт адаптации InPlaceMergeSort к движению «только вперёд» посмотрю. Похоже, что основная проблема там — обменять фрагмент массива длиной A и следующий за ним свободный кусок длиной B местами (с сохранением порядка в первом фрагменте) в случае, когда A>B.
                                0
                                Я использовал 2 прохода: сначала пихаем в начало элементы "<", потом после них элементы "=".
                                В InPlaceMergeSort я не смог придумать как сортировать подмассивы длиной sqrt(n) друг относительно друга без рандомного доступа к памяти. Причем основная проблема — не обменять массивы, а добежать указателями до их начал.
                                  0
                                  Понятно. Получается больше обменов, но двумя бегущими вперёд указателями разделить элементы можно.

                                  Да, с сортировкой блоков проблема. Но есть ещё один алгоритм InPlaceMergeSort, основанный на том факте, что мы можем слить два блока длиной A и B, если рядом с ними есть свободное место длиной min(A,B). В случае списков это делается, когда сначала идёт свободное место, потом короткий фрагмент, потом длинный.
                                  Сортировка всего массива выглядит так. Сначала сортируем фрагмент длиной 2/3*N, используя оставшиеся K=N/3 как свободное место. Это можно сделать без рекурсии, работая с фрагментами длиной, равной степени двойки. Придётся, правда, сортировать все фрагменты длины 2, потом длины 4, потом длины 8…
                                  Теперь в цикле, пока K>1, сортируем массив длиной K/2, используя остальные K/2, как свободное место, а потом сливаем отсортированный кусок с большим отсортированным фрагментом. Записываем в K длину свободного куска.
                                  Проблема обмена отсортированного массива со свободным местом остаётся — в алгоритме свободное место всё время убегает в хвост списка, а перед слиянием надо возвращать его в начало.
                                    0
                                    Да вроде нету там никаких проблем. Пусть наш массив-список выглядит так: вначале 2К неотсортированных элементов, затем отсортированный кусок. Тогда сортируем первые К элементов слиянием, используя вторые К как буфер, а потом сливаем с отсортированным куском в конце, начиная записывать результат с К+1 элемента. Тогда неотсортированная часть сама собой переедет на место первых К элементов, и тем самым мы свели задачу к исходной, только с К вместо 2К. Со случаем, когда длина неотсортированной части нечетна, надо просто аккуратно побороться, можно, например, банально вставить один элемент в отсортированный кусок и свести её к четной.
                                      0
                                      Сложно. Придётся использовать обе операции (A, F, B) => (F, A+B) и (F, A, B) => (A+B, F), причём аккуратно. Возможно, один раз всё-таки придётся переставить массив длиной N/3 в конец — но там будет просто обмен со свободным местом.
                                        0
                                        Если я верно вас понял, то да, но ничего особо сложного. Если не сильно заморачиваться по поводу эффективности, то можно для обоих случаев использовать одну версию процедуры слияния, которая принимает итераторы начала сливаемых кусков и их длины, а также итератор по которому писать ответ, а как они там между собой расположены это не её дело. Или всегда использовать первый вариант, а перед слиянием двух соседних кусков в merge sort вначале обменивать второй кусок с буфером местами, как при слиянии с N/2 дополнительной памяти (но опять же не самый эффективный код).

                                        К слову, мне кажется, в качестве первого шага выгоднее сортировать N/2, а не 2N/3 элементов, потому что сортировка слиянием, когда у нас есть N дополнительной памяти, а не N/2, более эффективна за счет того, что мы можем использовать один кусок в качестве источника, а во второй писать ответ, а на следующем шаге просто делать наоборот.
                                +2
                                Возможно я не до конца понял условия, но сортировать списки за O(n log n) времени и O(1) памяти умеет обычная сортировка слиянием. Для слияния двух упорядоченных списков в один в отличии от массивов дополнительная память не нужна.
                                  0
                                  Да, немного неточно. Подразумевалось, что «и на списках в том числе», и еще «модифицировать список нельзя, только ходить по нему». Попробую эту неточность устранить.
                                    0
                                    модифицировать список нельзя, только ходить по нему

                                    А ответ куда писать тогда?
                                      0
                                      Можно менять местами два элемента списка (на которые есть указатели/итераторы).
                                      Т.е. структуру списка ломать нельзя, можно только обменивать пары элементов внутри него.
                                        +3
                                        Это извращенное ограничение, если честно, т. к. инвалидируются указатели на элементы списка + требуется использовать потенциально дорогой обмен элементов вместо гарантированно дешевых манипуляций с указателями. Тогда, как выше написали, помогает inplace merge sort (нестабильная версия).
                                          0
                                          Никогда не храните указатели на элементы внутри контейнеров. Мало ли как оно потом будет само себя модифицировать. Первая же реаллокация того же вектора инвалидирует все все ваши указатели.

                                          Фраза «и на списках в том числе» означает, что я могу запустить свою сортировку не только на списке, но и на массиве, и на векторе и на фиг знает еще какой структуре данных, которая предоставляет мне нужный для этого интерфейс, в котором перевешивание указателей не предусмотрено.
                                            +1
                                            Никогда не храните указатели на элементы внутри контейнеров.
                                            Просто одно из ключевых свойств списков, что операции с ним не меняют указатели на элементы.
                                              +1
                                              хм… замечание-то дельное, перечитал референс по std::list, по сути там можно сортить только так:
                                              some_list.sort();
                                              сортировка заточена под список, она перекидывает указатели, указатели остаются валидны.

                                              я же подразумевал вариант вроде этого, где вместо some_list, в принципе, может быть другой контейнер
                                              sort( some_list.begin(), some_list.end() );
                                              но для list оно что-то даже не компилируется:(
                                                0
                                                Не компилируется, потому что std::sort() хочет случайный доступ к элементам сортируемой структуры (более строго: итератор должен удовлетворять требованиям random access iterator).
                                                  0
                                                  Вообще, из всех STL-контейнеров помимо вектора указатели на элементы инвалидирует только std::deque, и то лишь при добавлении не в начало или конец, все остальные контейнеры их сохраняют.
                                                    0
                                                    ну, я просто в подавляющем большинстве случаев использую вектор, вот и не храню как-то на автомате указатели на элементы внутри любого контейнера.
                                                +2
                                                Извините, что вмешиваюсь, но вы точно понимаете друг друга?
                                                Лично я воспринимаю фразу «можно только обменивать пары элементов внутри него» как раз как обмен указателей, а не содержимого элементов. Если это именно то, что подразумевалось (элементы остаются там же, мы только меняем связку типа NextNode, то ответная претензия «т. к. инвалидируются указатели на элементы списка + требуется использовать потенциально дорогой обмен элементов вместо гарантированно дешевых манипуляций с указателями» несостоятельна.
                                                Или под «обменом пар» подразумевается что-то другое?
                                                  0
                                                  я подразумеваю под элементами — сами сортируемые данные, без отношения к списку.
                                                  то есть сам список — контейнер для элементов, является цепочкой вершин, внутри которых находятся элементы. как-то так.
                                                  я мог кое-где ошибиться в обозначениях, ибо четкой терминологии заранее не строил.
                                                  но, думаю, мы поняли друг друга верно)
                                                0
                                                Скажем, есть список ((a1. b1) (a2. b2)… (an. bn)). Вам нужно отсортировать b1...bn по возрастанию, оставив a1...an в том же порядке, в котором они были. Здесь структуру списка нарушать уже нельзя, придётся переставлять части элементов с помощью setcdr.
                                          –1
                                          Обычная сортировка слиянием работает рекурсивно, и тем самым требует O(log n) памяти.
                                            +3
                                            Если сливать за log(N) проходов, получая сначала отсортированные пары, потом четвёрки и т.д. то рекурсия не нужна. Можно отсортировать даже за один проход, сливая нужные фрагменты при первой возможности. И тоже без рекурсии.
                                              0
                                              Хм, сортировка слиянием без рекурсии — это и есть «обычная» сортировка слиянием? Не знал…
                                                +1
                                                Сортировка слиянием — это когда мы делим массив/список на две части, добиваемся того, чтобы каждая из них была отсортирована, и сливаем. Всё остальное — на какие части делить, в каком порядке сортировать, где брать дополнительную память для слияния и как её использовать, сливать массивы с начала или с конца — всего лишь детали реализации. И кто будет определять, какую из реализаций считать «обычной»? Википедия?
                                                +1
                                                Ну да, тут разница в том, сверху вниз или снизу вверх строится дерево рекурсии. Когда строим снизу вверх, рекурсия спокойно разворачивается в итерации.
                                            +1
                                            Интересно бы еще узнать практическую задачу. Задумался над массив vs linked-list, оверхеды на хранение указателей в каждой ноде, ограничения на доступ и проход по списку. Возможно, используя другие структуры данных или подготавливая входные данные для сортировки (создание массива из списка и потом обратно?) можно было бы проще сделать… Тогда бы и тесты и бенчмарки прогнать можно было, так сказать, эмпирически померяться :)
                                              +1
                                              Практическая задача — вряд ли, я же оговаривался в статье, что интерес чисто академический. Головоломка на пораскинуть мозгами. Впрочем, первый вариант кода можно где-нибудь использовать, лишней O(logn) памяти, думаю, найдется всегда.
                                                0
                                                Например, односвязный список из массивов? Или список, возникший в большом графе, где ссылки уже входят в глобальную структуру, а выделить массив за её пределами нельзя (всю память пустили на лес односвязных списков для большой LISP-машины)?
                                                0
                                                А уже есть тесты, с какого количества элементов эта реализация быстрее сортировки слиянием?
                                                  +2
                                                  Боюсь, она медленнее сортировки слиянием для любого количества элементов. Даже тесты делать руки опускаются.
                                                    –2
                                                    Она быстрее всегда, потому что обычные сортировки слиянием в этих условиях работать не будут — им нужен либо прямой доступ к памяти, либо модификация списка, либо стек. Вот необычная сортировка может оказаться быстрее…
                                                      0
                                                      Плохое требование тут имхо — это O(n log n) в худшем случае, без него вполне реально написать qsort за O(1) дополнительной памяти с выбором рандомного элемента в качестве pivot'а, который будет неплохое время на практике показывать. Можно впрочем сделать как в introsort и запускать предложенный алгоритм или тот же inplace merge sort (любой алгоритм, работающий за O(n log n) в худшем случае), если у qsort дела плохо идут.
                                                        0
                                                        Так ведь другие алгоритмы требуют прямого доступа к элементам, который запрещён.
                                                          0
                                                          Не очень вас понял, вы точно верно прочитали, что я написал? Я имел ввиду, что если бы требовалась производительность O(n log n) лишь в среднем, а не в худшем случае, то можно было бы написать специальную версию qsort, которая показывала бы неплохое время на практике.
                                                            0
                                                            Скорее, это я не очень вас понял. Вы имели в виду quicksort, или описанную в этой статье нерекурсивную адаптацию с последовательным доступом? Мы ещё не знаем, какое время она будет показывать при случайном выборе — заметим, что там процедура разделения массива не такая, как в классике. Имелся в виду обычный inplace merge sort для массива, или ещё не написанную, и не факт, что существующую адаптацию, опять же, для последовательного доступа?
                                                              0
                                                              Да, qsort без стека, реализованный по принципу описанному в начале статьи (или сходному с ним), но без всяких там выборов медианного элемента, выбираем случайный элемент в качестве разделителя. Метод разделения, когда идем не с двух сторон указателями, а только с начала в конец довольно известный, называется Lomuto partition. Оверхеда у такого qsort по сравнению с классическим по сути только дополнительный лишний проход по каждому сортируемому отрезку (чтобы определить его длину + на нем же сразу будем выбирать разделитель). Это должно давать неплохую скорость на практике, во всяком случае гораздо быстрее и inplace merge sort, и конечного алгоритма в статье.
                                                                0
                                                                Оверхеда у такого qsort по сравнению с классическим по сути только дополнительный лишний проход по каждому сортируемому отрезку (чтобы определить его длину + на нем же сразу будем выбирать разделитель).

                                                                Это получается в два раза больше сравнений (на каждом уровне мы дополнительно дважды проходим по каждому второму отрезку — итого вместо N сравнений на разделение получается 2*N), и в два раза больше обменов — если в классическом qsort перемещать нужно только элементы, которые меньше разделителя, но попали в правую часть отрезка — их в среднем N/4, то в разделении проходом с начала массива придётся двигать каждый элемент, меньший разделителя (кроме самых первых) — а их примерно N/2.
                                                                inplace merge sort с прямым доступом легко обгоняет как qsort, так и std::sort (если пускать их в равных условиях — скажем, если в std::sort используется дефолтное сравнение, то в merge sort будем использовать #define, который раскрывается в x<y. А при сравнении с qsort будем вызывать функцию через указатель). Для последовательного доступа ещё не дописал. Думаю, что у merge sort хорошие шансы на выигрыш.
                                                    +1
                                                    Первоисточник идеи неизвестен, гугл по этому поводу по большей части молчит
                                                    По запросу quicksort without stack мне гугл выдал интересную статью Quicksort without a stack, где в довольно странно выглядящей статье (1986 года) описывается очень похожий алгоритм.

                                                    Правда, кажется, тот алгоритм лучше в виду отсутствия необходимости искать максимумы в блоках. В самом деле, если включить pivot в левый от него блок, подлежащий сортировке, то он и будет наибольшим.
                                                      +1
                                                      Если бы к этой статье был бы еще бесплатный доступ… Или я не туда нажимал?

                                                      Пока сути алгоритма я совсем не понял, но сразу пару вопросов: корректно ли он ловит случаи, когда элементов равных pivot несколько? и еще когда первый или третий блок после разделения оказываются пустыми?
                                                        0
                                                        Из университетской сети мне показывают полную статью. Неуниверситетского интернета рядом не оказалось, попробовал зайти туда с машинки в Германии — показали полный текст. А так, в интернете, видимо, так просто этот текст не найти.

                                                        В самом алгоритме я пока особо не разбирался, лишь мельком посмотрел на описание и попробовал провести параллели с вышеизложенной версией.
                                                          0
                                                          Насколько я понимаю, показывает нахаляву только первые пару страниц.
                                                          0
                                                          В общем, вот код inplace merge, адаптированный для последовательного доступа. Надо определить три фунцкии:

                                                          void* LNext(void*) — перейти к следующему элементу
                                                          bool LLess(void *a,void *b) — сравнить два элемента, вернуть true, если a<b
                                                          void LSwap(void *a,void *b) — обменять местами два элемента.

                                                          Сейчас в качестве LLess стоит (x^5)<(y^5).
                                                          На массивах длиной от 6 млн до 100 млн сортировка работает быстрее, чем std::sort (с той же функцией сравнения), в 1.6-1.7 раза.
                                                            +1
                                                            Когда вы делаете вот так:
                                                            std::sort(arr,arr+len,myfunction);
                                                            
                                                            то вы передаете в качестве аргумента указатель на функцию, поэтому вызовы этой функции не будут заинлайнены внутри std::sort(), в отличии от вашей функции сортировки. Лучше сделайте вот так:
                                                            std::sort(arr,arr+len,[](int i, int j){ return (i^5)<(j^5); });
                                                            

                                                            Но даже несмотря на передачу по указателю, на gcc 4.9.0 и 10 миллионах (100 на онлайн-компиляторе не выполняется, чуть попозже дома погляжу) std::sort() чуть быстрее, а с заменой на функциональный объект становится быстрее почти в два раза coliru.stacked-crooked.com/a/9dbe1c48ab675c7a. Это так, первый взгляд, нету много времени разбираться пока.
                                                              +1
                                                              Да, с заменой на функциональный объект std::sort стал быстрее, чем ListSort, примерно на 5-10% (компилятор VS 2013). Есть за что побороться. Грустно и странно, что переход с последовательного на прямой доступ почти не прибавил скорости. Скорее всего, компилятор соптимизировал функцию Jump :)
                                                                0
                                                                Действительно…
                                                                _TEXT	SEGMENT
                                                                ?Jump@@YAPAXPAXH@Z PROC					; Jump, COMDAT
                                                                	dec	edx
                                                                	js	SHORT $LN2@Jump
                                                                	lea	ecx, DWORD PTR [ecx+edx*4]
                                                                	add	ecx, 4
                                                                $LN2@Jump:
                                                                	mov	eax, ecx
                                                                	ret	0
                                                                ?Jump@@YAPAXPAXH@Z ENDP					; Jump
                                                                _TEXT	ENDS
                                                                
                                                            0
                                                            Алгоритм описан на википедии (ru, en), а также в Кормене, но я немного расскажу про него, поскольку на википедии он описан настолько топорно, что я понял его суть только после сопоставления русской и английской версии (и еще пришлось заглянуть в оригинальную статью).

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

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

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