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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 80: Строка 80:
 
! Шаг 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: Строка 107:
 
</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>.
Строка 125: Строка 125:
 
<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>
Строка 154: Строка 154:
 
             '''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: Строка 161:
 
             s.push(l, i - 1)
 
             s.push(l, i - 1)
  
В качестве альтернативного варианта можно использовать обычную рекурсивную версию, в которой вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит <tex>\log n</tex>, а в худшем случае вырожденного разделения она вообще будет не более <tex>1</tex> — вся обработка пройдёт в цикле первого уровня рекурсии.
+
В качестве альтернативного варианта можно использовать обычную рекурсивную версию, в которой вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит <tex>\log n</tex>, а в худшем случае вырожденного разделения она вообще будет не более <tex> n </tex> — вся обработка пройдёт в цикле первого уровня рекурсии.
  
 
===Улучшенная быстрая сортировка===
 
===Улучшенная быстрая сортировка===

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

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

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

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