Сортировка Хоара (Quick Sort)

1.

англ. quick sort , сортировка Хоара
ИВТб-1302

2.

Сортировка Хоара один
из самых известных
и широко используемых
алгоритмов сортировки.
Quick Sort является
существенно улучшенным
вариантом алгоритма
сортировки с помощью
прямого обмена

3.

Работает по принципу «разделяй и властвуй»
1. Выбрать произвольный элемент (опорный)
из массива. Назовём его pivot.
2. Массив A[l…r] разбивается на 2 подмассива
A[l…pivot] и A[pivot + 1…r] таких,
что каждый элемент
A[l…pivot] ≤ A[pivot] ≤ A[pivot + 1…r]
3. Подмассивы A[l…pivot] и A[pivot + 1…r]
сортируются c помощью рекурсивного
метода сортировки.
4. Получаем отсортированный массив A[l…r]

4.

Среднее время работы
составляет