
Доброго всем времени суток!!!
Суть (если коротко) данного вида сортировки заключается в определении места опорного элемента (нулевой элемент в массиве) и постановки его на место (т. е. его надо поставить на место, которое он бы занял в отсортированном массиве). Попутно происходит частичная сортировка массива. Рассмотрим первую стадию сортировки:
ИМЕЕМ МАССИВ
0. 12, 0, 25, 1, 36, 11, 7, 19, 23, 21
С правой стороны начинаем перебирать элементы, ищем элемент < 12. 7 < 12. Меняем их местами. Получим:
1. 7, 0, 25, 1, 36, 11, 12, 19, 23, 21
С левой стороны начинаем перебирать элемены, ищем элемент > 12. 25 > 12. Меняем их местами. Получим:
2. 7, 0, 12, 1, 36, 11, 25, 19, 23, 21
С правой стороны начинаем перебирать элементы, ищем элемент < 12. 11 < 12. Меняем их местами. Получим:
3. 7, 0, 11, 1, 36, 12, 25, 19, 23, 21
С левой стороны начинаем перебирать элемены, ищем элемент > 12. 36 > 12. Меняем их местами. Получим:
4. 7, 0, 11, 1, 12, 36, 25, 19, 23, 21
В результате получаем массив, где все элементы слева от опорного не превышают опорный элемент и все элементы справа от опорного не менее опорного.
Первая стадия закончена. Далее запускаем рекурсию. Левый и правый подмассивы должны произвести прогон и разбить два подмассива еще на два подмассива. И так далее.
Сортировка действительно быстрая. 1000 000 элементов массива данным методом сортируются быстрее, чем 10 000 пузырьковым методом (секундомером не мерял, все строго по ощущениям).