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

 

Для достижения наибольшей эффективности при сортировке Ч.Хоар предложил обеспечить обмен элементов на больших расстояниях.

Идея быстрой сортировки Ч. Хоара такова: в последовательности сортируемых элементов (а₁,…,a_n) выберем наугад какой-нибудь элемент (назовем его Х); будем просматривать слева нашу последовательность до тех пор, пока не найдем элемент а_і> X; потом будем просматривать последовательность справа, пока не встретим a_j< X; поменяем местами эти два элемента и продолжим процесс просмотра и обмена, пока эти два просмотра не встретятся в середине последовательности. В результате этого последовательность будет разбита на левую часть, которая имеет ключи меньшие (или равные) Х, и правую – с ключами большими (или равными) Х. Сортировку от распределения отделяет только небольшой шаг: необходимо применить этот процесс разбиения к получившимся двум частям, потом к частям частей, и так до тех пор, пока каждая из частей не будет состоять из одного элемента.

Описание алгоритма быстрой сортировки имеет вид:

1. В последовательности элементов А =(а₁,…,a_n) выбрать элемент Х.

2. Просматривая последовательность А слева направо, найти элемент а_i < Х.

3. Просматривая последовательность А справа налево, найти элемент а_к >= Х.

4. Поменять местами элементы а _і и а _k. Продолжить процесс встречного просмотра и обмена, пока два просмотра не встретятся где-то внутри последовательности элементов А. Если down >= up, то поменять местами Х и а _up, где down – текущий индекс при движении слева направо,

5. а up - текущий индекс при движении справа налево. В результате элемент Х помещается в позицию j и выполнятся следующие условия: - элементы в позициях с 1-й по (j -1)-ю меньше (равны) Х, - элементы в позициях с (j +1)-й по n -ю, больше (равны) Х. То есть элемент Х является j -м наименьшим элементом в последовательности А и Х останется в позиции j и когда последовательность А будет полностью отсортирована.

6. Применить пункты 1,..,5 к подпоследовательностям (а ₁,…, a _j) (а _j-1,…, a _n) и так далее, пока каждая из подпоследовательностей не будет состоять из одного элемента.

Первая часть процесса быстрой сортировки для последовательности А =(11, 7, 4, 49, 9, 18, 2, 5, 11) показана в табл. 3, в качестве элемента разбиения Х выбран элемент а₅.

Таблица 3 Пример быстрой сортировки

Шаг	Состояние последовательности
1.
2.
3.

 

В примере Х = а ₅=9. Так как а ₁=11> Х, а а ₈=5< Х, то они меняются местами, что и показано во второй строке таблицы 1. Так как а ₄=49> Х, а а ₇=2< Х, то они тоже меняются местами, что и показано в третьей строке таблицы 1. Третья строка таблицы 1 также показывает, что элемент Х = а ₅=9 находится в своем окончательном месте и разделяет последовательность А на две подпоследовательности: с элементами меньше (равно) Х – (5, 7, 4, 2) и с элементами больше (равно) Х – (18, 49, 11, 11). Далее процесс сортировки необходимо аналогично применить к этим подпоследовательностям.

Для выбора элемента разбиения Х можно использовать:

1. Первый элемент последовательности.

2. Последний элемент последовательности.

3. Элемент находящийся посередине последовательности.

4. Медиану последовательности.

5. Медиану среди элементов (а ₁, a _n/2, a _n).

6. Генератор случайных чисел.

Для алгоритма быстрой сортировки имеем следующие выводы:

1. быстрая сортировка работает наилучшим образом для полностью неотсортированных последовательностей;

2. лучший выбор элемента разделения – медиана последовательности;

3. быстрая сортировка работает наихудшим образом для полностью отсортированных последовательностей при выборе в качестве элемента разбиения наименьшего (наибольшего) значения;

4. в среднем (по всем последовательностям размера n) быстрая сортировка имеет сложность O (n · log ₂ n);

5. в наихудшем случае быстрая сортировка имеет сложность O (n ²);

6. быстрая сортировка является одним из наилучших алгоритмов сортировки (за счет наименьшей мультипликативной константы C _Q по сравнению с пирамидальной сортировкой).

Пример. Пошаговая работа алгоритма быстрой сортировки (первое разделение последовательности).

 

X=a(lb) // X - элемент разделения, для него ищется место окончательной позиции

Up=rb // Up – правая граница массива

Down=lb // Down – левая граница массива

While Down< Up do

While a(Down) <= X do

Down= Down+1

End

While a(Up) > X do

Up= Up-1

End

If Down< Up then

поменять местами a(Down) и a(Up)

End If

End

a(lb)= a(Up) // a(Up) меняется местами с a(lb)= X

a(Up)= X

j= Up // j – окончательная позиция элемента разделения X

Пусть имеется массив размерности n=9:

 

Проверим условие алгоритма: при движении слева-направо – "<=", справа-налево – ">".

X=a(1)=11

Up=n=9

Down=1

a(1)=11<=X=11 Да → Down= Down +1=2

a(2)=7<=X=11 Да → Down= Down +1=3

a(3)=2<=X=11 Да → Down= Down +1=4

a(4)=4<=X=11 Да → Down= Down +1=5

a(5)=18<=X=11 Нет → a(9)=11>X=11 → Нет

Down=5< Up=9 Да → обмен a(5) и a(9)

Получили 11, 7, 2, 4, 11, 9, 49, 5, 18

a(5)=11<=X=11 Да → Down= Down +1=6

a(6)=9<=X=11 Да → Down= Down +1=7

a(7)=49<=X=11 Нет → a(9)=18>X=11 Да → Up= Up-1=8

a(8)=5>X=11 Нет

Down=7< Up =8 Да → обмен a(7)=49 и a(8)=5

Получили 11, 7, 2, 4, 11, 9, 5, 49, 18

a(7)=5<=X=11 Да → Down= Down +1=8

a(8)=49<=X=11 Нет → a(8)=49>X=11 Да→ Up= Up-1=7

a(7)=5>X=11 Нет

Down=8< Up =7 Нет → обмен X=a(1)=11 с a(7)=5

После первого разделения получили последовательность вида:

 

Элемент разделения X=a(1)=11 занял окончательное место j=7 в почти что отсортированной последовательности, исходная последовательность разделилась на две части – первая с элементами <= X=11 – (5, 7, 2, 4, 11, 9, 11), вторая – с элементами > X=11 – (49, 18).

 

Список литературы

 

1. Лэнгсам И., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ. -М.: Мир, 1989.-568 с.(с.437-465).

2. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. -М.: МЦНМО, 2000. - 960 с. (с. 175 – 177, с.171 – 173)

3. Седжвик Р. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск. - К.: ДиаСофт, 2001. – 688 с. (с. 295-298, 401 - 437)

4. Ахо А., Хопкрофт Дж., Ульман Д. Структуры данных и алгоритмы. -М.: Вильямс, 2000. – 384 с. (с. 247 - 254)

5. Проценко В.С. та ін. Техніка програмування мовою Сі: Навч. Посібник,-К.:Либідь, 1993.-224 с.(с.72-73).

6. Мейер Б., Бодуэн К. Методы программирования Т.2.-М.:Мир, 1982.-368 с.(с.153-183).

7. Зубов В.С. Справочник программиста. Базовые методы решения графовых задач и сортировки.-М.: Филинъ, 1999.-256 с.(с.55-62).

8. Кнут Д. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск.-М.:Мир, 1978.-844 с.(с.140-151,177-190).

9. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов.-М.:Мир, 1981.-(с.223-240).

 

Контрольные вопросы и задания

 

1. В чем состоят задача и цель сортировки?

2. Приведите классификацию алгоритмов внутренней сортировки.

3. Каковы основные показатели качества исследуемых алгоритмов сортировки?

4. Отсортируйте пошагово по возрастанию массив целых чисел размерности 6 с помощью быстрой сортировки, сортировки подсчетом, поразрядной сортировки (LSD и MSD).

5. Каковы сложности алгоритмов быстрой сортировки, сортировки подсчетом, поразрядной сортировки?

6. Как задается качество массива для исследования алгоритмов сортировки?