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

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

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

Сортировка — такая же «вечная» тема для алгоритмистов, как любовь — для поэтов. Казалось бы, новое слово в этой области сказать трудно, а поди же ты — продолжают придумывать новые алгоритмы сортировок (TimSort...) Есть, однако, базовые факты, которые знает каждый приличный студент. Известно, к примеру, что универсальный алгоритм сортировки не может быть быстрее 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
Просмотров: 171
Размер:	7.7 Кб
ID:	6555   Нажмите на изображение для увеличения
Название: iq-02.png
Просмотров: 134
Размер:	7.9 Кб
ID:	6556  
Размещено в Без категории
Показов 3152 Комментарии 6
Всего комментариев 6
Комментарии
  1. Старый комментарий
    Аватар для Welemir1
    С удовольствием прочел, у вас определенно талант к изложению, отдельное спасибо за "этот алгоритм известен каждому культурному человеку"

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

    Запись от Welemir1 размещена 04.11.2020 в 10:03 Welemir1 на форуме
  2. Старый комментарий
    Аватар для Catstail
    Спасибо за добрые слова! Ссылку исправлю.
    Запись от Catstail размещена 04.11.2020 в 15:23 Catstail на форуме
  3. Старый комментарий
    Применение правильного алгоритма, иногда, единственный способ решить вопрос со скоростью вычислений.
    Просматривал тематику алгоритмов сортировки, Ваша статья оказалась кстати, спасибо за более
    подробную информацию при освоении алгоритмов и структур данных.
    Запись от AlexMarkov размещена 19.03.2021 в 17:39 AlexMarkov вне форума
  4. Старый комментарий
    Аватар для CoderHuligan
    Catstail, - а сортировка Шелла разве не совмещает в себе преимущества быстрой сортировки с сортировкой вставками? Когда-то я сравнивал работу шелла и квиксорт и Шелл оказывался лучше квиксорт.
    Запись от CoderHuligan размещена 19.03.2021 в 19:11 CoderHuligan вне форума
  5. Старый комментарий
    Аватар для Catstail
    Цитата:
    Сообщение от CoderHuligan Просмотреть комментарий
    Catstail, - а сортировка Шелла разве не совмещает в себе преимущества быстрой сортировки с сортировкой вставками? Когда-то я сравнивал работу шелла и квиксорт и Шелл оказывался лучше квиксорт.
    - сортировка Шелла не обладает естественным поведением. Могут быть ситуации, когда Шелл лучше quicksort. Но предел
    любой универсальной сортировки O(n*log(n)). Анализ сортировки Шелла весьма сложен и этот вопрос до конца не изучен.
    Запись от Catstail размещена 11.04.2021 в 15:33 Catstail на форуме
  6. Старый комментарий
    Аватар для Catstail
    Цитата:
    Сообщение от AlexMarkov Просмотреть комментарий
    Применение правильного алгоритма, иногда, единственный способ решить вопрос со скоростью вычислений.
    Просматривал тематику алгоритмов сортировки, Ваша статья оказалась кстати, спасибо за более
    подробную информацию при освоении алгоритмов и структур данных.
    - спасибо за добрые слова!
    Запись от Catstail размещена 11.04.2021 в 15:34 Catstail на форуме
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.