Цена естественности или как обогнать 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 раз. Результаты оказались следующими:

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

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

Легко видеть, что для массива размера 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 

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