Форум программистов, компьютерный форум, киберфорум
Catstail
Войти
Регистрация
Восстановить пароль
Рейтинг: 5.00. Голосов: 3.

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

Запись от Catstail размещена 03.11.2020 в 22:19
Обновил(-а) Catstail 04.11.2020 в 15:25

Сортировка — такая же «вечная» тема для алгоритмистов, как любовь — для поэтов. Казалось бы, новое слово в этой области сказать трудно, а поди же ты — продолжают придумывать новые алгоритмы сортировок (TeamSort...) Есть, однако, базовые факты, которые знает каждый приличный студент. Известно, к примеру, что универсальный алгоритм сортировки не может быть быстрее O(n*log(n)). Такой показатель производительности имеет знаменитая QuckSort (придуманная в 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 раз. Результаты оказались следующими:



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

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



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

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

Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
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
Спасибо за внимание!

ссылка на хабре
Миниатюры
Нажмите на изображение для увеличения
Название: iq-01.png
Просмотров: 103
Размер:	7.7 Кб
ID:	6555   Нажмите на изображение для увеличения
Название: iq-02.png
Просмотров: 66
Размер:	7.9 Кб
ID:	6556  
Размещено в Без категории
Просмотров 570 Комментарии 2
Всего комментариев 2
Комментарии
  1. Старый комментарий
    Аватар для Welemir1
    С удовольствием прочел, у вас определенно талант к изложению, отдельное спасибо за "этот алгоритм известен каждому культурному человеку"

    Ссылку не верно дали,это ваша авторская, надо вот такую

    Запись от Welemir1 размещена 04.11.2020 в 10:03 Welemir1 вне форума
  2. Старый комментарий
    Аватар для Catstail
    Спасибо за добрые слова! Ссылку исправлю.
    Запись от Catstail размещена 04.11.2020 в 15:23 Catstail вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.