Яндекс.Метрика

Рассылка обновлений по электронной почте

четверг, 31 марта 2011 г.

Быстрая сортировка Хоара

Сегодня рассказывала на лекции про сортировки.
    Вставкой
    Пузырьком
    Шейкер
    Выбором
    Подсчетом
    Хоара — быстрая

Все кроме последней элементарно объясняются в википедии и в интернете вообще, а последняя через попу. Ща попытаюсь объяснить понятно. Скажете, что неясно.


Краткое описание
Суть этой сортировки заключается в том, что после каждого прохода все элементы разделяются на две группы: слева находятся меньшие, чем какой-либо элемент, а справа — большие. После каждого прохода берется каждая из двух частей и сортируется тем же способом, то есть задача сводится к предыдущей. Так происходит пока все подчасти не будут состоять из одного элемента. Таким образом, количество элементов в сортируемой части уменьшается при каждом следующем вызове функции из себя же.

Еще раз: после первого прохода список разделяется на две части. Затем, берется первая, и для нее вызывается та же сортировка, в результате которой этот подсписок (первая часть) тоже разбивается на 2, и т. д., пока в принимаемом списке не останется один элемент. То же повторяется и для второй части. Следовательно, удобно использовать рекурсию для написании этой сортировки.

Подробное описание. Пример
Для того, чтобы разбить список на 2 части относительного некоторого элемента, нужно выбрать этот элемент. Можно выбирать случайно, то есть любой. Я рассмотрю случай, когда элемент выбирается как серединный: (левая граница списка + правая граница) разделить на 2 = (l + r) / 2 = (0 + 7) / 2 = 3.

22    7    10    0    6    6   1
 0     1     2     3    4    5   6
 l                                         r

Серединный — a[3] = 0.

Итак, находим значение серединного элемента, затем, чтобы он не мешался, обмениваем его с нулевым.

0    7    10    22    6    6   1

Далее находим границы списка, который мы будем анализировать. Левая граница (назовем ее l) будет находиться на первой позиции (если считать с нуля), так как на нулевой лежит избранный элемент. А правая (назовем ее r) будет находиться на конце списка и будет равна его размерности. Итак, диапазон анализируемых значений будет [l ; r), не включая правую границу.

0    7    10    22    6    6   1
      l                                     r

Давайте анализировать. Элемент а[l] > 0, значит, меняем его с a[r - 1]. И так как справа у нас находятся большие элементы, то правая граница анализируемой части подвигается влево на один.

0    1    10    22    6    6   7
      l                                r

Далее, a[l] > 0, обмениваем его с a[r - 1]. Сдвигаем правую границу.

0    6    10    22    6    1   7
      l                           r

И так далее, пока r и l не станут равными: r = l.

0    6    10    22    6    1   7
      l                      r

0    22    10    6    6    1   7
       l               r

0    10    22    6    6    1   7
       l       r

0    10    22    6    6    1   7
      l r

Далее необходимо базовый элемент положить как раз на границу двух списков: чтобы справа от него были те, что меньше него, а слева — те, что больше него. Очевидно эта граница находится на позиции l - 1.
Поэтому в данном случае меньше нуля элементов нет и первый подсписок состоит из нуля элементов, а следовательно он отсортирован и сортировку нужно производить с оставшимся подсписком

10   22    6    6    1   7

Выбираем базовый элемент — a[3]. Срединный — «6», меняем его с нулевым.

10   22    6    6    1   7

6    22     6   10   1   7

Расставляем границы.

6    22    6   10   1   7
       l                           r

Сравниваем поочередно элементы a[l] с базовым «6». a[l] > 6, поэтому

   7     6    10   1   22
      l                         r

a[l] снова больше чем 6.

   1    6    10    7   22
      l                   r

А вот сейчас a[l] < 6, поэтому мы не производим обмен, а сдвигаем левую границу вправо на один элемент.

   1     6    10    7   22
             l             r

6 <= 6, левая граница подвигается

   1    6     10    7   22
                    lr

Сейчас r = l, вставляем базовый элемент в l - 1

6    1    6    10    7   22
                   lr     

Получилось, что мы разбили подсписок на 2 части (с нулевого по l-ый — третий и с l-ого по r-ый — с третьего по пятый, не включая правые границы, как всегда):

     6    1    и    10    7   22
№ 0    1           2     3    4 

Рассмотрим первую часть:

6    1

Выберем базовый элемент (0 + 2)/2 = 1, переместим на место первого, ставим границы

1    6  
      l   r

Проводим те же операции, в результате получим

1    6 
      lr

и разделим  на два подсписка: пустой и «6», которые уже отсортированы.

Далее, обработаем вторую часть исходного списка:

10    7   22

7    10   22
        l           r

7   22   10
      l      r

7   10   22
      lr

Делим на два списка:

пустой и «10   22»

Обработаем второй (0 + 2) / 2 = 1:

10    22

22    10
         l     r

22    10
              lr

Возвращаем базовый элемент на нужное место (l - 1):


10    22
              lr


Разбиваем на два списка: «10» и пустой, которые уже отсортированы. Соединим все полученные подсписки в один

0    1     6     6    7    10    22.


Сложность
Сложность данного алгоритма в худшем случае (когда после разделения на элементы, большие базового и меньшие базового, получается два списка: пустой и из оставшихся элементов) O(n^2), что не отличает данную сортировку от всех вышеперечисленных «небыстрых». Но в среднем случае, когда базовый элемент разбивает при каждом проходе список примерно на два подсписка равной длины, мы получаем сложность n * log_2(n). Почему:

За один проход мы перебираем n элементов — n операций. Но каждый следующий проход делит список на два (при этом количество перебираемых (сравниваемых) элементов не уменьшается, так как мы сортируем обе половины), в итоге количество проходов равно двоичному логарифму от n — log_2(n).


Для тех, кто не помнит, что такое логарифм: сколько раз нужно умножить 2 само на себя, чтобы получилось n? log_2(n). То есть количество делений нашего списка на два, пока не останется список из одного (или нуля) элементов.

7 комментариев:

  1. Доброго вечера, Елена! Если не возражаете у меня есть пара вопросов по Вашему объяснению сортировки Хоара.
    1. Почему в этих 2х строчках:
    0 10 22 6 6 1 7
    l r

    0 22 10 6 6 1 7
    l r
    Вы 22 и 10 меняете местами ведь 0 < 10 и 10 мы меняем с числом на позиции (r-1), т.е. получается с самим собой?
    2. Для выбора базового элемента на одном из этапов Вы используете выражение (0 + 2)/2 = 1. Почему его и откуда Вы получили эти слагаемые?

    Буду признательна за ответы.

    С уважением, Марина.

    ОтветитьУдалить
  2. 1. Спасибо, это моя ошибка. Сейчас исправлю. Все правильно, 10 остается на месте (это значение меняется с самим собой местами).

    2. Это выражение считает номер базового элемента. Здесь я беру элемент посередине. Имеется в виду номер начального элемента + количество элементов разделить на два.


    Спасибо за замечания, еще одну опечатку сама заметила. Сейчас все уточню и исправлю.

    ОтветитьУдалить
  3. мда...

    Итак, находим значение серединного элемента, затем, чтобы он не мешался, обмениваем его с нулевым.

    из каких соображений?)

    ОтветитьУдалить
  4. Далее необходимо базовый элемент положить как раз на границу двух списков: чтобы справа от него были те, что меньше него, а слева — те, что больше него.
    А не наоборот право-лево?

    ОтветитьУдалить
  5. Очень тяжело читать, когда не знаешь, опечатка это или ты туговат... :)

    ОтветитьУдалить