Реализация быстрой сортировки со следующими аргументами функции: указатель на начало массива и его размер. В предыдущей реализации нумерация элементов подмассива всегда велась относительно начала исходного массива, в рекурсивные вызовы передавались аргументы left и right, обозначающие границы подмассивов.

Как и ранее, подмассив, с которым работает конкретный рекурсивный вызов, выделен чёрным цветом и подчёркнут синей линией. Для большей наглядности показано data[0] (значение самого левого элемента текущего подмассива).

Быстрая сортировка (quicksort) иначе называется сортировкой Хоара. Её идея предельно проста: в массиве выбирают некий опорный элемент (pivot), разбивают массив на две части: слева элементы меньше опорного, справа — больше. Затем процесс рекурсивно повторяется для левой и правой частей массива.

Существуют разные модификации быстрой сортировки и способы её реализации. В данном варианте в функцию передаётся массив и индексы крайних элементов: quickSort(data, 0, n- 1);. В другом варианте можно было бы передавать адрес начала массива и его размер: quickSort(data, n);.

Обратим внимание на два фрагмента из кода, который расположен далее. В каждом рекурсивном вызове водятся l = left; и r = right;, они хранят индексы крайнего левого и крайнего правого элементов.

Данный материал представляет собой обзор и анализ того, как в литературе и в цифровых ресурсах изображают рекурсивные сортировки — главным образом сортировку слиянием и быструю сортировку (сортировку Хоара).

Анализ литературы

Анализ литературы затруднён тем, что в некоторых книгах вовсе нет изображений, в иных — одна сортировка может сопровождаться иллюстрациями, а другая нет. Классики в части быстрой сортировки показывают прямой ход рекурсии [Ахо, 236]. Обратный ход довольно тривиален и не подразумевает каких-то манипуляций с данными.