Цена естественности или как обогнать QuickSort

    Сортировка — такая же «вечная» тема для алгоритмистов, как любовь — для поэтов. Казалось бы, новое слово в этой области сказать трудно, а поди же ты — продолжают придумывать новые алгоритмы сортировок (TimSort...) Есть, однако, базовые факты, которые знает каждый приличный студент. Известно, к примеру, что универсальный алгоритм сортировки не может быть быстрее O(n*log(n)). Такой показатель производительности имеет знаменитая QuickSort (придуманная в 1960-м году Хоаром), а также сортировка слиянием (Фон Неймана) и пирамидальная сортировка. Что же касается элементарных алгоритмов («пузырек», «вставки», «выбор»), то их показатель существенно хуже — O(n^2). Но всегда ли QuickSort является «абсолютным чемпионом»?

    Ведь кроме показателя производительности есть и другие характеристики, зачастую — не менее важные. Один из них — естественность. Что это такое? Сортировка называется естественной, если она выполняется быстрее в том случае, когда массив уже почти отсортирован. А какой массив можно считать «почти отсортированным»? Вот два массива, состоящие из одних и тех элементов:

    {1,2,9,3,4,5,7,6,8,10} и {9,1,6,3,10,5,4,2,8,7}

    Даже на глаз видно, что первый массив более упорядочен (только 9 и 7 стоят «не на месте»). Тогда как во втором массиве числа перемешаны хаотически. Что же является мерой упорядоченности? Ответ известен — количество инверсий. Пара элементов A[i] и A[j] при j > i составляют инверсию, если A[j] < A[i]. (В этой заметке целью сортировки всегда является упорядочение по возрастанию).

    Теперь можно дать точное определение: сортировка называется естественной, если время ее работы снижается при снижении количества инверсий в исходном массиве.
    Естественность — достаточно «редкий фрукт» в мире сортировок — ни QuickSort ни сортировка Шелла не обладают этим свойством, увы. Но есть один алгоритм, который, можно сказать, является абсолютно естественным — это сортировка вставками. Хотя этот алгоритм известен каждому культурному человеку, позволю себе кратко повторить его суть.

    Сортируемый массив просматривается один раз от начала к концу. Как только обнаруживается, что i-й и (i-1)-элементы образуют инверсию, i-й элемент «закидывается» назад (что достигается сдвигом нужного отрезка начала массива вправо на одну позицию). Из этого описания понятно, что если в массиве мало инверсий, алгоритм «пролетит» по массиву очень быстро. Если инверсий нет совсем, то алгоритм завершится за время O(n). А вот QuickSort в этом случае будет долго и утомительно выбирать разделяющий элемент, делить уже упорядоченный массив на отрезки и т.п. Но при наличии большого количества инверсий ситуация, разумеется, будет обратной: производительность сортировки вставками упадет до O(n^2), а QuickSort будет чемпионом — O(n*log(n)).

    Сложившаяся ситуация порождает естественный с моей точки зрения вопрос: при каком количестве инверсий перевешивает естественность и сортировка вставками работает быстрее QuickSort?

    Для ответа на этот вопрос я провел серию вычислительных экспериментов. Суть их состояла в следующем. Брались массивы целых чисел размером от 3000 до 30000 элементов, в них вносилось некоторое количество инверсий, затем массивы сортировались вставками и быстрой сортировкой. Замерялось время сортировки (в системных тиках). Для усреднения каждая сортировка повторялась 10 раз. Результаты оказались следующими:

    image

    На картинке представлены зависимости времени сортировки от количества внесенных инверсий. Малиновая серия — это, естественно, QuickSort, а синяя — сортировка вставками. Для размера массива 30 тыс. элементов, до примерно 400 тыс. инверсий «побеждает естественность». Для менее упорядоченных массивов уже выгоднее QuickSort.

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

    image

    Легко видеть, что для массива размера n критическое количество инверсий составляет примерно 10*n. При большем количестве инверсий выгоден QuickSort. Следует отметить, что максимальное количество инверсий для массива длины n составляет n*(n-1)/2. Величина 10*n есть весьма незначительная их часть. Что и неудивительно.

    К сказанному осталось добавить, что результаты таких экспериментов зависят от многих факторов (языка программирования, типа сортируемых данных и т.п.) Мне, честно говоря, было лень исследовать эти вопросы более детально. Мои эксперименты проводились в Microsoft Excel в среде VBA:

    Исходный код тестов
    Private Declare Function GetTickCount Lib "kernel32" () As Long
    
    '::: Сортировка вставками 
    
    Sub JSort(A() As Long)
        n& = UBound(A, 1)
        For i& = 2 To n
            If A(i&) < A(i& - 1) Then
               j& = i& - 1
               x& = A(i&)
               Do While (A(j&) > x&)
                  A(j& + 1) = A(j&)
                  j& = j& - 1
                  If j& = 0 Then Exit Do
               Loop
               A(j& + 1) = x&
            End If
        Next i&
    End Sub
    
    '::: Быстрая сортировка
    
    Sub QSort(A() As Long, Optional b As Long = 1, Optional e As Long = 0)
        If (e - b) <= 1 Then Exit Sub
        i& = b
        j& = e
        w& = A((i& + j&) / 2)
        Do While (i& < j&)
          Do While (A(i&) < w&)
             i& = i& + 1
          Loop
          Do While (A(j&) > w&)
             j& = j& - 1
          Loop
          If i& < j& Then
             tmp& = A(i&)
             A(i&) = A(j&)
             A(j&) = tmp&
             i& = i& + 1
             j& = j& - 1
          End If
        Loop
        If j& > b Then QSort A, b, j&
        If i& < e Then QSort A, i&, e
    End Sub
    
    '::: Случайные перестановки элементов (внесение инверсий)
    
    Sub InsInv(A() As Long, k As Long)
        n& = UBound(A, 1)
        For i& = 1 To k
            Do
               k1& = n& * Rnd
               k2& = n& * Rnd
               If (k1& <> k2&) And (k1& >= 1) And (k2& >= 1) Then Exit Do
            Loop
            tmp& = A(k1&)
            A(k1&) = A(k2&)
            A(k2&) = tmp&
        Next i&
    End Sub
    
    '::: Подсчет числа инверсий в массиве
    
    Function NumInv(A() As Long) As Long
        n& = UBound(A, 1)
        For i& = 1 To n& - 1
            For j& = i& + 1 To n&
                If A(j&) < A(i&) Then NumInv = NumInv + 1
            Next j&
        Next i&
    End Function
    
    '::: Главный тест
    
    Sub Gtest_1()
    Dim Eta() As Long
    Dim Arr() As Long
        Size& = CLng(InputBox("Sz="))
        ReDim Eta(1 To Size&) As Long
        ReDim Arr(1 To Size&) As Long
        Randomize
        For i& = 1 To Size&
            Eta(i&) = i&
        Next i&
        q# = Size& * (Size& - 1) / 2
        For iii% = 1 To 10
            InsInv Eta, CLng(iii%)
            ni# = CDbl(NumInv(Eta))
            Cells(iii%, 1).Value = ni#  
            DoEvents
            S# = 0
            For l% = 1 To 10
                For i& = 1 To Size&
                    Arr(i&) = Eta(i&)
                Next i&
                TBeg& = GetTickCount
                JSort Arr
                TEnd& = GetTickCount
                S# = S# + TEnd& - TBeg&
            Next l%
            Cells(iii%, 2).Value = S#
            DoEvents
            S# = 0
            For l% = 1 To 10
                For i& = 1 To Size&
                    Arr(i&) = Eta(i&)
                Next i&
                TBeg& = GetTickCount
                QSort Arr, 1, Size&
                TEnd& = GetTickCount
                S# = S# + TEnd& - TBeg&
                If Not check(Arr) Then Exit Sub
            Next l%
            Cells(iii%, 3).Value = S#
            DoEvents
        Next iii%
        MsgBox "OK"
    End Sub
    


    Спасибо за внимание!

    PS
    И спасибо всем, кто отметил мои ошибки! (Неверное написание Timsort — в первой редакции было «TeamSort» и пропущенное «i» в QuickSort), скорость-время в определении естественности. И — да! — (специально для перфекционистов) QuickSort может «деградировать» до квадратичной производительности. Но в заметке я рассматриваю не худший, а лучший случай применения QuickSort.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 28

      0
      Но всегда ли QuickSort является «абсолютным чемпионом»?

      Нет, не всегда.


      Мне вот интересно, вы про timsort слышали?

        +2
        А Вы первый абзац сообщения прочитали?
          +1

          Когда я читал, там был TeamSort, который мне неизвестен.


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

            0
            Это я ошибся в названии timsort — не так написал.
              0
              Так я с QuickSort сравниваю…
                –3

                … а зачем?

                  –6
                  Было интересно. Забыл спросить разрешения у вас…
          +2
          Что то вспомнилось выступление Андрея Александреску www.youtube.com/watch?v=FJJTYQYB1JQ Там примерно о том же, но подробнее.
          +2
          А еще есть вариант Квиксорта с разбиением Ломуто, которое, как показано тут в блоге D Александреску, можно сделать с минимизацией условных переходов в коде и выиграть >20%.
            +2
            Поздравляю, вы открыли адаптивные сортировки, упомянутый timsort как раз из этих ребят.
            +7
            прочитал первый абзац. Сложность QuckSort — n^2 на ворст кейсе. Рассказывают на первом курсе.
              –8
                +4
                Худшее время у него -квадратичное, Вы хотя бы сами читали то, на что ссылаетесь
                  –7
                  Худшее — да. Среднее — нет. Я рассматривал QuickSort в выгодной для нее области.

                    +3
                    В выгодной области сортировка у меня занимает о(1). Обычно все таки принято указывать худшее время для алгоритмов, а не среднее, когда говорят о теоретической производительности.
                      –7
                      Какая универсальная сортировка у вас выполняется за O(1)?
                        +7
                        «Ничего не делать» — это универсальный метод, переоткрытый лично мной. Возможно напишу статью на эту тему. Работает за 0 времени. В случае уже отсортированных данных работает отлично за О(1). В других случаях — хуже, может сортировать за О(inf). Но важна ведь удобная для него область…
                          –4
                          А… Ну понятно. Уровень возражения чувствуется.
                        0
                        Ну тут все, конечно, можно притянуть за уши.

                        Есть такая теорема, что если мы считаем QuickSort недетерминированным (случайный выбор элемента для partition на каждом шаге), а потом посчитаем среднее время для всех возможных стартовых сидов этого случайного алгоритма, то мы действительно получим n log(n). Тоесть, в каком-то смысле QS «всреднем» эффективен, а «неудобная область» для него довольно мала.

                        Но в этом случае:
                        1) Нужно обговорить что мы имеем ввиду под «показатель производительности». Это может быть и не сложность алгоритма.
                        2) Нельзя использовать O-нотацию.
                        3) Вообще, упомянуть эти вещи

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

                          0
                          Да я знаю, что я не совсем прав, но автор статьи так забавно поставляется под троллинг и так на него ведётся…
                          А О нотация — это просто нотация. Ей можно характеризовать и теоретическую и практическую производительность, но с оговорками.
                          Обычно они совпадают и оговорок не требуется.
                          А статья — да, согласен, школьная. Другие у автора получше.
                            –2
                            А некоторым читателям и школьные знания будут нелишиними…
                            –3
                            «Ну и еще могу набросать претензий» — у вас, часом, не юридическое образование?
                        +2

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


                        Если тупо выбирать случайный pivot, то вероятность быть заметно медленее n log n пренебрежимо мала.

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

                            Нет, алгоритм по ссылке — именно находит медиану (вернее любую к-ую порядковую статистику) за O(n). Медиана медиан в нем используется в качестве разделителя, чтобы две половины были достаточно равные.

                              0
                              Не убедили.Ни относительно порядка, ни относительно медианы… Будет время, проанализирую повнимательней.

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