Сортировка считается самой фундаментальной проблемой в изучении алгоритмов, поскольку она используется повсеместно. Существует огромное количество алгоритмов сортировки. От сортировки вставками до сортировки слиянием все имеют свои плюсы и минусы в зависимости от размера входных данных и других факторов. мы будем говорить о быстрой сортировке, время работы которой в наихудшем случае составляет O(n ^ 2), но она по-прежнему является хорошим выбором для сортировки, поскольку в среднем она эффективна с ожидаемым временем работы O(n log n).
Быстрая сортировка
Как и сортировка слиянием, алгоритм быстрой сортировки использует парадигму «разделяй и властвуй», но имеет преимущество сортировки на месте.
Трехэтапный процесс «разделяй и властвуй» для сортировки массива A[p..r]
Разделить
Выбирается опорный элемент, вокруг которого происходит разбиение. Разделение A[p..r] на два подмассива A[p..q-1] и A[q+1..r] так, что каждый элемент A[p..q-1] меньше или равно A[q] (стержень), и каждый элемент A[q+1..r] больше, чем A[q].
Завоевать
Отсортируйте два подмассива A[p..q-1] и A[q+1..r] путем рекурсивного деления
Объединить
Подмассивы уже отсортированы из-за разделения, поэтому для их объединения не требуется никаких дополнительных действий. После объединения массив A[p..r] сортируется.
На приведенной выше диаграмме мы видим, что массив рекурсивно делится на две части, и деление выполняется таким образом, что левая часть всегда меньше, чем стержень, а правая часть всегда больше, чем стержень. После объединения результатов каждой ветки мы получаем наш отсортированный массив.
так как разделяется массив? какой алгоритм стоит за этим?
Разделение массива
Самый важный шаг в быстрой сортировке — это разбиение массива на два подмассива вокруг опорного элемента. Он переставляет элементы массива на место.
Для массива A[p…r]
Время разбиения массива составляет o(n)
- установить опорный элемент: A[r]
- установите переменную i = p -1 (чтобы сместить элементы, меньшие, чем точка поворота, влево при обходе)
- цикл j от p до r-1 (для обхода массива)
- если в цикле элемент меньше или равен стержню, то увеличьте i и замените A[i] на A[j]
- после завершения цикла поменяйте местами A[i+1] на A[r], чтобы поставить точку поворота в нужное место (между двумя подмассивами)
теперь у вас есть два подмассива, где элементы в A[p..i] ≤ A[i+1] и элементы в A[i+2..r] > A[i+1]
предположим, у нас есть массив «А» из 8 элементов —
A = [2,8,7,1,3,5,6,4]
- Слегка заштрихованные элементы массива находятся в первом разделе со значениями меньше опорного.
- Сильно заштрихованные элементы находятся во втором разделе со значениями, превышающими точку опоры.
- Незаштрихованные элементы еще не были пройдены.
Производительность
Время выполнения быстрой сортировки зависит от того, как разбит массив. Если раздел сбалансирован, это так же быстро, как сортировка слиянием — O (n log n) . если раздел несбалансирован, он может работать так же медленно, как сортировка вставками — O (n²).
разбиение в худшем случае
когда раздел создает один подмассив с n-1 элементами и один с 0 элементами, считается несбалансированным разделом. мы будем видеть это несбалансированное разделение в каждом рекурсивном вызове.
Рекуррентное отношение для несбалансированного раздела -
T(n) = T(n-1) + n
После решения этого отношения (методом подстановки) мы получаем арифметический ряд, который оценивается как O (n²). Следовательно, время выполнения быстрой сортировки в худшем случае равно T(n) = O(n²).
Оптимальное разделение
При наиболее равномерном разбиении PARTITION создает два подмассива, размер каждого из которых не превышает n/2, поскольку один имеет размер [n/2], а другой — [n/2] -1. В этом случае быстрая сортировка выполняется намного быстрее.
Тогда рекуррентное соотношение для сбалансированного раздела будет
T(n) = 2T(n/2) + n
После решения,
T (n) = O (n log n)
Равным образом уравновешивая две стороны раздела на каждом уровне рекурсии, мы получаем более быстрый алгоритм.
Сбалансированное разделение
Среднее время выполнения быстрой сортировки гораздо ближе к лучшему, чем к худшему. Чтобы понять это, предположим, что алгоритм разбиения разделил массив в соотношении 9 к 1.
который на первый взгляд кажется довольно несбалансированным, но рекуррентное соотношение для такого разделения равно
T(n) = T(9n/10) + T(n/10) + n
время выполнения повторения которого будет T (n) = O (n log n), таким же, как если бы разделение было равным. Действительно, даже разделение 99 к 1 дает время работы O(n log n). На самом деле любое разделение с постоянной пропорциональностью дает дерево рекурсии глубины O (log n), где стоимость на каждом уровне равна O (n). Таким образом, время выполнения равно O(n log n).
Средний случай
В среднем случае мы заметим рандомизированное поведение быстрой сортировки, что означает, что РАЗДЕЛ производит смесь сбалансированных и несбалансированных разбиений на каждом уровне рекурсии.
Чтобы упростить расчеты, предположим, что сбалансированное и несбалансированное разделение происходит на чередующихся уровнях дерева. Таким образом, массив размера «n» на 1-м уровне подвергается несбалансированному разбиению и создает два подмассива размера 0 и n -1 соответственно. На следующем уровне подмассив размера n-1 подвергается сбалансированному разбиению и образует два подмассива размером [n-1/2] и [n-1/2]–1.
Таким образом, общая стоимость этих перегородок будет равна — 0 + O(n) + O(n-1) = O(n)
Стоимость двухуровневого разбиения аналогична одноуровневому разбиению, которое создает два подмассива размера (n-1)/2 при стоимости O(n). Выполнение быстрой сортировки, когда уровень чередуется между хорошими и плохими разбиениями, похоже на время выполнения только хороших разбиений: O (n log n), но с большей константой.
Заключение
- Алгоритм быстрой сортировки использует парадигму «разделяй и властвуй» и сортирует массив на месте.
- Быстрая сортировка в среднем эффективна с ожидаемым временем работы O (n log n), но в худшем случае время работы O (n ^ 2).
- Самый важный шаг в быстрой сортировке — разбиение на разделы. Для массива размером n время, необходимое для его разделения на два подмассива, равно O(n).
- В худшем случае время работы быстрой сортировки составляет O(n²), когда раздел несбалансирован.
- В лучшем случае время выполнения быстрой сортировки составляет O(n log n), когда раздел сбалансирован.
- Среднее время выполнения быстрой сортировки составляет O(n log n), когда раздел представляет собой смесь хороших и плохих разбиений, случайно распределенных по всему дереву.
Если вам понравилась эта запись в блоге, поделитесь ею с другом!
ссылка:
Введение в алгоритм (третье издание) Томаса Х. Кормена.
