Алгоритмы, третья неделя - "Быстрая сортировка"
Вторая тема третьей недели - алгоритм так называемой "быстрой сортировки". Я написал "так называемой" потому что, вообще говоря, этот алгоритм (лично мое мнение) не является самой быстрой сортировкой. Самой быстрой сортировкой мне кажется сортировка деревом, которая по-английски называется "Heapsort" (о ней речь пойдёт дальше).
Алгоритм быстрой сортировки (Quicksort) был придуман Чарльзом Хоаром, за что в 1980 году ему была вручена Премия Тьюринга. В общих словах идея алгоритма описывается следующими пунктами:
1. Перемешать исходный массив
2. Разделить его на две части следующим образом: некоторый элемент находится на "своём" месте (то есть, на котором он находился бы в отсортированном массиве); элементы меньше него находятся слева от него, элементы больше - справа от него.
3. Рекурсивно повторять пункт 2 для каждой из двух частей массива (правой и левой).
Элемент, который оказывается на "своем" месте, называют "разделяющим элементом" и обычно для этого берут элемент, который в данный момент находится в начале сортируемого массива.
Разделение массива на две части происходит несложным образом:
- элементы сканируются слева направо до тех пор, пока не будет найден элемент больше разделяющего элемента (пусть его индекс будет i)
- элементы сканируются справа налево до тех пор, пока не будет найден элемент меньше разделяющего элемента (пусть его индекс будет j)
- элементы с индексами i и j меняются местами, а процесс продолжается до тех пор, пока точки сканирования не пересекутся на каком-либо элементе; как только они пересекаются, следуем обменять разделяющий элемент с точкой пересечения.
Перемешивание исходного массива делается на всякий случай: дело в том, что в худшем случае производительность этого алгоритма квадратична (это если массив уже отсортирован, как это ни парадоксально). Перемешивание производится для того, чтобы исключить этот случай и добиться высокой производительности. В общем случае алгоритм линеарифмичен.
Алгоритм быстрой сортировки (Quicksort) был придуман Чарльзом Хоаром, за что в 1980 году ему была вручена Премия Тьюринга. В общих словах идея алгоритма описывается следующими пунктами:
1. Перемешать исходный массив
2. Разделить его на две части следующим образом: некоторый элемент находится на "своём" месте (то есть, на котором он находился бы в отсортированном массиве); элементы меньше него находятся слева от него, элементы больше - справа от него.
3. Рекурсивно повторять пункт 2 для каждой из двух частей массива (правой и левой).
Элемент, который оказывается на "своем" месте, называют "разделяющим элементом" и обычно для этого берут элемент, который в данный момент находится в начале сортируемого массива.
Разделение массива на две части происходит несложным образом:
- элементы сканируются слева направо до тех пор, пока не будет найден элемент больше разделяющего элемента (пусть его индекс будет i)
- элементы сканируются справа налево до тех пор, пока не будет найден элемент меньше разделяющего элемента (пусть его индекс будет j)
- элементы с индексами i и j меняются местами, а процесс продолжается до тех пор, пока точки сканирования не пересекутся на каком-либо элементе; как только они пересекаются, следуем обменять разделяющий элемент с точкой пересечения.
Перемешивание исходного массива делается на всякий случай: дело в том, что в худшем случае производительность этого алгоритма квадратична (это если массив уже отсортирован, как это ни парадоксально). Перемешивание производится для того, чтобы исключить этот случай и добиться высокой производительности. В общем случае алгоритм линеарифмичен.