Редактирование: Быстрая сортировка

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 3: Строка 3:
 
==Алгоритм==
 
==Алгоритм==
 
Быстрый метод сортировки функционирует по принципу "разделяй и властвуй".  
 
Быстрый метод сортировки функционирует по принципу "разделяй и властвуй".  
* Массив <tex> a[l \ldots r]</tex> типа <tex> T </tex> разбивается на два (возможно пустых) подмассива <tex> a[l \ldots q]</tex> и <tex> a[q+1 \ldots r]</tex>, таких, что каждый элемент <tex> a[l \ldots q]</tex> меньше или равен <tex> a[q]</tex>, который в свою очередь, не превышает любой элемент подмассива <tex> a[q+1 \ldots r]</tex>. Индекс  вычисляется  в ходе процедуры разбиения.
+
* Массив <tex> a[l \ldots r]</tex> типа <tex> T </tex> разбивается на два (возможно пустых) подмассива <tex> a[l \ldots q-1]</tex> и <tex> a[q+1 \ldots r]</tex>, таких, что каждый элемент <tex> a[l \ldots q-1]</tex> меньше или равен <tex> a[q]</tex>, который в свою очередь, не превышает любой элемент подмассива <tex> a[q+1 \ldots r]</tex>. Индекс  вычисляется  в ходе процедуры разбиения.
* Подмассивы <tex> a[l \ldots q]</tex> и <tex> a[q+1 \ldots r]</tex> сортируются с помощью рекурсивного вызова процедуры быстрой сортировки.
+
* Подмассивы <tex> a[l \ldots q-1]</tex> и <tex> a[q+1 \ldots r]</tex> сортируются с помощью рекурсивного вызова процедуры быстрой сортировки.
 
* Поскольку подмассивы сортируются на месте, для их объединения не требуются никакие действия: весь массив <tex> a[l \ldots r]</tex> оказывается отсортированным.
 
* Поскольку подмассивы сортируются на месте, для их объединения не требуются никакие действия: весь массив <tex> a[l \ldots r]</tex> оказывается отсортированным.
  
Строка 10: Строка 10:
 
   '''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)
 
   '''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)
 
       '''if''' l < r
 
       '''if''' l < r
         '''int''' q = partition(a, l, r)
+
         q = partition(a, l, r)
         quicksort(a, l, q)
+
         quicksort(a, l, q - 1)
 
         quicksort(a, q + 1, r)
 
         quicksort(a, q + 1, r)
 
Для сортировки всего массива необходимо выполнить процедуру <tex>\mathrm{quicksort(a, 0, length[a] - 1)}</tex>.
 
Для сортировки всего массива необходимо выполнить процедуру <tex>\mathrm{quicksort(a, 0, length[a] - 1)}</tex>.
Строка 18: Строка 18:
 
Основной шаг алгоритма сортировки {{---}} процедура <tex>\mathrm{partition}</tex>, которая переставляет элементы массива <tex>a[l \ldots r]</tex> типа <tex> T </tex> нужным образом.
 
Основной шаг алгоритма сортировки {{---}} процедура <tex>\mathrm{partition}</tex>, которая переставляет элементы массива <tex>a[l \ldots r]</tex> типа <tex> T </tex> нужным образом.
 
Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента произвольно выбирается элемент  
 
Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента произвольно выбирается элемент  
<tex> a[(l + r) / 2] </tex>. Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий элемент, затем выполняется просмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разделенном массиве, и потому они меняются местами. Так продолжаем дальше, пока не убедимся в том, что слева от левого указателя не осталось ни одного элемента, который был бы больше по значению разделяющего, и ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента.
+
<tex> a[r] </tex> — он сразу займет свою окончательную позицию. Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий элемент, затем выполняется просмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разделенном массиве, и потому они меняются местами. Так продолжаем дальше, пока не убедимся в том, что слева от левого указателя не осталось ни одного элемента, который был бы больше по значению разделяющего, и ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента.
  
Переменная <tex> v </tex> сохраняет значение разделяющего элемента <tex> a[(l + r) / 2] </tex>, a <tex> i </tex> и <tex> j </tex> представляет собой, соответственно, указатели левого и правого просмотра. Цикл разделения увеличивает значение <tex> i </tex> и уменьшает значение <tex> j </tex> на <tex> 1 </tex>, причем условие, что ни один элемент слева от <tex> i </tex> не больше <tex> v </tex> и ни один элемент справа от <tex> j </tex> не меньше  <tex> v </tex>, не нарушается. Как только значения указателей пересекаются, процедура разбиения завершается.
+
Переменная <tex> v </tex> сохраняет значение разделяющего элемента <tex> a[r] </tex>, a <tex> i </tex> и <tex> j </tex> представляет собой, соответственно, указатели левого и правого просмотра. Цикл разделения увеличивает значение <tex> i </tex> и уменьшает значение <tex> j </tex> на <tex> 1 </tex>, причем условие, что ни один элемент слева от <tex> i </tex> не больше <tex> v </tex> и ни один элемент справа от <tex> j </tex> не меньше  <tex> v </tex>, не нарушается. Как только значения указателей пересекаются, процедура разбиения завершается,  меняя местами <tex> a[r] </tex> и <tex> a[i] </tex>, при этом <tex> v </tex> присваивается значение <tex> a[i] </tex>, так что не будет ни одного большего элемента справа от <tex> v </tex> и ни одного меньшего элемента слева от <tex> v </tex>.
  
 
   '''int''' partition(a: '''T'''[n], '''int''' l, '''int''' r)
 
   '''int''' partition(a: '''T'''[n], '''int''' l, '''int''' r)
       '''T''' v = a[(l + r) / 2]
+
       '''T''' v = a[r]
 
       '''int''' i = l
 
       '''int''' i = l
       '''int''' j = r
+
       '''int''' j = r - 1
       '''while''' (i <tex> \leqslant </tex> j)
+
       '''while''' ''true''
         '''while''' (a[i] < v)
+
         '''while''' (a[i++] < v)
            i++
+
         '''while''' (a[j--] > v)
         '''while''' (a[j] > v)
+
        '''if''' (j == l)
             j--
+
             '''break'''
 
         '''if''' (i <tex> \geqslant </tex> j)  
 
         '''if''' (i <tex> \geqslant </tex> j)  
 
             '''break'''
 
             '''break'''
         swap(a[i++], a[j--])
+
         swap(a[i], a[j])
       '''return''' j
+
      swap(a[i], a[r])
 +
       '''return''' i
  
 
==Асимптотика==
 
==Асимптотика==
Строка 80: Строка 81:
 
! Шаг 1.0 || Шаг 1.1 || Шаг 1.2 || Шаг 2.0 || Шаг 2.1 || Шаг 2.2 || Шаг 3.0
 
! Шаг 1.0 || Шаг 1.1 || Шаг 1.2 || Шаг 2.0 || Шаг 2.1 || Шаг 2.2 || Шаг 3.0
 
|-align="right"
 
|-align="right"
|style="text-align: center;"|1 2 3 4 <br> 0 '''0''' 0 0
+
|style="text-align: center;"|1 2 3 4 <br\> 0 '''0''' 0 0
| style="text-align: center;"|1 2 3 4 <br> 0 '''4''' 0 0
+
| style="text-align: center;"|1 2 3 4 <br\> 0 '''4''' 0 0
|style="text-align: center;"|1 4 3 2 <br> 0 0 0 '''4'''
+
|style="text-align: center;"|1 4 3 2 <br\> 0 0 0 '''4'''
|style="text-align: center;"|1 4 3 2 <br> 0 '''0''' 0 4
+
|style="text-align: center;"|1 4 3 2 <br\> 0 '''0''' 0 4
|style="text-align: center;"|1 4 3 2 <br> 0 '''3''' 0 4
+
|style="text-align: center;"|1 4 3 2 <br\> 0 '''3''' 0 4
|style="text-align: center;"|1 3 4 2 <br> 0 0 '''3''' 4
+
|style="text-align: center;"|1 3 4 2 <br\> 0 0 '''3''' 4
|style="text-align: center;"|1 3 4 2 <br> '''0''' 0 3 4
+
|style="text-align: center;"|1 3 4 2 <br\> '''0''' 0 3 4
 
|-
 
|-
 
! Шаг 3.1 || Шаг 3.2 || Шаг 4.0 || Шаг 4.1 || Шаг 4.2 || colspan="2" style="vertical-align: middle;"| Результат
 
! Шаг 3.1 || Шаг 3.2 || Шаг 4.0 || Шаг 4.1 || Шаг 4.2 || colspan="2" style="vertical-align: middle;"| Результат
  
 
|-align="right"
 
|-align="right"
|style="text-align: center;"|1 3 4 2 <br> '''2''' 0 3 4
+
|style="text-align: center;"|1 3 4 2 <br\> '''2''' 0 3 4
|style="text-align: center;"|3 1 4 2 <br> 0 '''2''' 3 4
+
|style="text-align: center;"|3 1 4 2 <br\> 0 '''2''' 3 4
|style="text-align: center;"|3 1 4 2 <br> '''0''' 2 3 4
+
|style="text-align: center;"|3 1 4 2 <br\> '''0''' 2 3 4
|style="text-align: center;"|3 1 4 2 <br> '''1''' 2 3 4
+
|style="text-align: center;"|3 1 4 2 <br\> '''1''' 2 3 4
|style="text-align: center;"|3 1 4 2 <br> '''1''' 2 3 4
+
|style="text-align: center;"|3 1 4 2 <br\> '''1''' 2 3 4
| colspan="2" style="text-align: center;vertical-align: middle;" |'''1 2 3 4''' <br> '''2 4 1 3'''
+
| colspan="2" style="text-align: center;vertical-align: middle;" |'''1 2 3 4''' <br\> '''2 4 1 3'''
  
 
|-
 
|-
Строка 107: Строка 108:
 
</center>
 
</center>
  
Покажем, почему на данном массиве будет достигаться максимальное время работы быстрой сортировки. На этапе построения мы каждый раз присваивали опорному элементу максимальное значение. Следовательно, при выполнении <tex>\mathrm{quicksort}</tex> алгоритм в качестве опорного всегда будет выбирать наибольший элемент массива (выборка будет производится в том же порядке ввиду детерминированности определения опорного элемента).  
+
Покажем, почему на данном массиве будет достигаться максимальное время работы быстрой сортировки. На этапе построения мы каждый раз присваивали опорному элементу минимальное значение. Следовательно, при выполнении <tex>\mathrm{quicksort}</tex> алгоритм в качестве опорного всегда будет выбирать наибольший элемент массива (выборка будет производится в том же порядке ввиду детерминированности определения опорного элемента).  
 
Таким образом, так как каждый раз массив разбивается на две части {{---}} большие или равные опорному элементы и меньшие его {{---}} на каждом шаге имеем разбиение на массивы длины <tex>1</tex> и <tex>n-1</tex>, чего мы, собственно, и добивались. При таком выполнении алгоритма происходит <tex>\Theta(n^2)</tex> разделений на два подмассива, и на каждом разделении выполняется <tex>\Theta(n^2)</tex> сравнений.  
 
Таким образом, так как каждый раз массив разбивается на две части {{---}} большие или равные опорному элементы и меньшие его {{---}} на каждом шаге имеем разбиение на массивы длины <tex>1</tex> и <tex>n-1</tex>, чего мы, собственно, и добивались. При таком выполнении алгоритма происходит <tex>\Theta(n^2)</tex> разделений на два подмассива, и на каждом разделении выполняется <tex>\Theta(n^2)</tex> сравнений.  
 
Следовательно, на данном массиве быстрая сортировка работает за <tex>\Theta(n^2)</tex>.
 
Следовательно, на данном массиве быстрая сортировка работает за <tex>\Theta(n^2)</tex>.
Строка 115: Строка 116:
 
Лемма
 
Лемма
 
|statement=Время работы алгоритма быстрой сортировки равно <tex>O(n \log n)</tex>.
 
|statement=Время работы алгоритма быстрой сортировки равно <tex>O(n \log n)</tex>.
|proof=Пусть <tex>X</tex> {{---}} полное количество сравнений элементов с опорным за время работы сортировки. Нам необходимо вычислить полное количество сравнений.
+
|proof=Пусть Х {{---}} полное количество сравнений элементов с опорным за время работы сортировки. Нам необходимо вычислить полное количество сравнений.
 
Переименуем элементы массива как <tex>z_1 \ldots z_n</tex>, где <tex>z_i</tex> наименьший по порядку элемент.
 
Переименуем элементы массива как <tex>z_1 \ldots z_n</tex>, где <tex>z_i</tex> наименьший по порядку элемент.
 
Также введем множество <tex>Z_{ij} = \{z_i, z_{i+1} \ldots z_j\}</tex>.
 
Также введем множество <tex>Z_{ij} = \{z_i, z_{i+1} \ldots z_j\}</tex>.
Строка 125: Строка 126:
 
<tex>X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}</tex>, где <tex>X_{ij} = 1</tex> если произошло сравнение <tex>z_i</tex> и <tex>z_j</tex>  и <tex>X_{ij} = 0</tex>, если сравнения не произошло.
 
<tex>X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}</tex>, где <tex>X_{ij} = 1</tex> если произошло сравнение <tex>z_i</tex> и <tex>z_j</tex>  и <tex>X_{ij} = 0</tex>, если сравнения не произошло.
  
Применим к обеим частям равенства операцию вычисления матожидания и воспользовавшись ее линейностью получим
+
Применим к обоим частям равенства операцию вычисления матожидания и воспользовавшись ее линейностью получим
  
 
<tex>E[X] = E\left[\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}\right] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} E[X_{ij}] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} Pr\{z_i</tex> сравнивается с <tex>z_j\}</tex>
 
<tex>E[X] = E\left[\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}\right] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} E[X_{ij}] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} Pr\{z_i</tex> сравнивается с <tex>z_j\}</tex>
Строка 148: Строка 149:
 
   '''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)
 
   '''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)
 
       '''stack'''< '''pair'''<'''int''','''int'''> > s   
 
       '''stack'''< '''pair'''<'''int''','''int'''> > s   
       s.push(l, r)
+
       s.push(l, r);
 
       '''while''' (s.isNotEmpty)
 
       '''while''' (s.isNotEmpty)
         (l, r) = s.pop()
+
         l = s.pop()
 +
        r = s.pop()
 
         '''if''' (r <tex> \leqslant </tex> l)
 
         '''if''' (r <tex> \leqslant </tex> l)
 
             '''continue'''
 
             '''continue'''
         '''int''' i = partition(a, l, r)
+
         '''int''' i = partition(a, l, r);
         '''if''' (i - l > r - i)  
+
         '''if''' (i - 1 > r - i)  
 
             s.push(l, i - 1)
 
             s.push(l, i - 1)
 
             s.push(i + 1, r)
 
             s.push(i + 1, r)
Строка 161: Строка 163:
 
             s.push(l, i - 1)
 
             s.push(l, i - 1)
  
В качестве альтернативного варианта можно использовать обычную рекурсивную версию, в которой вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит <tex>\log n</tex>, а в худшем случае вырожденного разделения она вообще будет не более <tex>1</tex> — вся обработка пройдёт в цикле первого уровня рекурсии.
+
В качестве альтернативного варианта можно использовать обычную рекурсивную версию, в которой вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит <tex>\log n</tex>, а в худшем случае вырожденного разделения она вообще будет не более <tex> n </tex> — вся обработка пройдёт в цикле первого уровня рекурсии.
  
 
===Улучшенная быстрая сортировка===
 
===Улучшенная быстрая сортировка===
  
 
Выбор медианы из первого, среднего и последнего элементов в качестве разделяющего элемента и отсечение рекурсии меньших подмассивов может  
 
Выбор медианы из первого, среднего и последнего элементов в качестве разделяющего элемента и отсечение рекурсии меньших подмассивов может  
привести к существенному повышению эффективности быстрой сортировки. Функция <tex>\mathrm{median}</tex> возвращает индекс элемента, являющегося медианой трех элементов. После этого он и средний элемент массива меняются местами, при этом медиана становится разделяющим элементом. Массивы небольшого размера (длиной <tex> M = 11</tex> и меньше) в процессе разделения игнорируются, затем для окончания сортировки используется [[Сортировка вставками | сортировка вставками]].  
+
привести к существенному повышению эффективности быстрой сортировки. Функция <tex>\mathrm{median}</tex> возвращает индекс среднего элемента в массиве. После этого он и крайний правый элемент массива меняются местами, при этом медиана становится разделяющим элементом. Массивы небольшого размера (длиной <tex> M = 11</tex> и меньше) в процессе разделения игнорируются, затем для окончания сортировки используется [[Сортировка вставками | сортировка вставками]].  
  
 
   '''const int''' M = 10
 
   '''const int''' M = 10
 
   '''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)
 
   '''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)
       '''if''' (r - l <tex> \leqslant </tex> M)
+
       '''if''' (r - 1 <tex> \leqslant </tex> M)
        insertion(a, l, r)
 
 
         '''return'''
 
         '''return'''
       '''int''' med = median(a[l], a[(l + r) / 2], a[r])
+
       int med = median(a[l], a[r - 1], a[r])
       swap(a[med], a[(l + r) / 2])
+
       swap(a[med], a[r - 1])
       '''int''' i = partition(a, l, r)
+
       '''int''' i = partition(l + 1, r - 1)
       quicksort(a, l, i)
+
       quicksort(a, l, i - 1)
 
       quicksort(a, i + 1, r)
 
       quicksort(a, i + 1, r)
  
Вообще, можно применять любые эвристики по выбору опорного элемента. Например, в стандартной реализации в Java в качестве разделяющего выбирается средний из 7 элементов, равномерно распределённых по массиву.
+
  '''void''' hybridsort(a: '''T'''[n], '''int''' l, '''int''' r)
 +
      quicksort(a, l, r)
 +
      insertion(a, l, r)
  
 
===Быстрая сортировка с разделением на три части===
 
===Быстрая сортировка с разделением на три части===
Строка 205: Строка 208:
 
       '''int''' p = l - 1
 
       '''int''' p = l - 1
 
       '''int''' q = r
 
       '''int''' q = r
       '''while''' ''(i <tex> \leqslant </tex> j)''  
+
       '''while''' ''true''  
         '''while''' (a[i] < v)  
+
         '''while''' (a[i++] < v)
            i++
+
         '''while''' (a[j--] > v)
         '''while''' (a[j] > v)  
+
        '''if''' (i == j)
             j--
+
             '''break'''
 
         '''if''' (i <tex> \geqslant </tex> j)
 
         '''if''' (i <tex> \geqslant </tex> j)
 
             '''break'''
 
             '''break'''
Строка 216: Строка 219:
 
             p++
 
             p++
 
             swap(a[p], a[i])
 
             swap(a[p], a[i])
        i++
 
 
         '''if''' (a[j] == v)
 
         '''if''' (a[j] == v)
 
             q--
 
             q--
 
             swap(a[q], a[j])
 
             swap(a[q], a[j])
        j--
 
 
       swap(a[i], a[r])
 
       swap(a[i], a[r])
 
       j = i - 1
 
       j = i - 1
 
       i++
 
       i++
       '''for''' ('''int''' k = l; k <tex> \leqslant </tex> p; k++, j--)  
+
       '''for''' ('''int''' k = 1 ; k <tex> \leqslant </tex> p; k++, j--)  
         swap(a[k], a[j])
+
         swap(a[k],a[j])
       '''for''' ('''int''' k = r - 1; k <tex> \geqslant </tex> q; k--, i++)  
+
       '''for''' (k = r-1; k <tex> \geqslant </tex> q; k--, i++)  
         swap(a[k], a[i])  
+
         swap(a[k],a[i])  
       quicksort(a, l, j)  
+
       quicksort(a, 1, j)  
 
       quicksort(a, i, r)
 
       quicksort(a, i, r)
  
Строка 237: Строка 238:
  
 
===Introsort===
 
===Introsort===
 
Для предотвращения ухудшения времени работы быстрой сортировки до <tex>O(n^2)</tex> при неудачных входных данных, также можно использовать алгоритм сортировки Introsort.
 
Он использует быструю сортировку и переключается на [[Сортировка кучей|пирамидальную сортировку]], когда глубина рекурсии превысит некоторый заранее установленный уровень (например, логарифм от числа сортируемых элементов). Так как после нескольких итераций быстрой сортировки с применением разных эвристик массив с большей вероятностью окажется «почти отсортированным», то пирамидальная сортировка может довольно быстро закончить дело. Также, пирамидальная сортировка хороша тем, что требует <tex>O(1)</tex> дополнительной памяти, в отличие от, например, сортировки слиянием, где потребуется <tex>O(n)</tex> дополнительной памяти.
 
  
 
==См. также==
 
==См. также==
Строка 252: Строка 250:
 
* [[wikipedia:ru:Быстрая сортировка|Википедия {{---}} Быстрая сортировка]]
 
* [[wikipedia:ru:Быстрая сортировка|Википедия {{---}} Быстрая сортировка]]
 
* [[wikipedia:en:Quicksort|Wikipedia {{---}} Quicksort]]
 
* [[wikipedia:en:Quicksort|Wikipedia {{---}} Quicksort]]
* [[wikipedia:en:Introsort|Wikipedia {{---}} Introsort]]
 
 
* ''Т. Кормен, Ч. Лейзерсон, Р. Ривест'': Алгоритмы: построение и анализ глава 7
 
* ''Т. Кормен, Ч. Лейзерсон, Р. Ривест'': Алгоритмы: построение и анализ глава 7
 
* ''Р. Седжвик'': Фундаментальные алгоритмы на С++ части 1 - 4
 
* ''Р. Седжвик'': Фундаментальные алгоритмы на С++ части 1 - 4
 
+
https://en.wikipedia.org/wiki/Introsort
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Сортировка]]
 
[[Категория: Сортировка]]
 
[[Категория: Сортировки на сравнениях]]
 
[[Категория: Сортировки на сравнениях]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: