Курсач на алгоритм Хоара( с++)

[_grusha_]

Дана задачка..

Запрограммировать алгоритм Хоара сортировки одномерного массива действительных чисел.Подсчитать кол-во сравнений и перестановок эл-тов.Провести эксперимент с несколькими ( порядка нес. десятков) массивами случайных чисел и выдать статистику о кол-ве сравнений и перестановок в каждом случае..

Господа, требуется код и алгоритм задачки словами, по русски...

огромная просьба помочь, кто знает... буду оч. признателен..

[maladoy]

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:
два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно;
вычисляется опорный элемент m;
индекс l последовательно увеличивается до m или до тех пор, пока l-й элемент не превысит опорный;
индекс r последовательно уменьшается до m или до тех пор, пока r-й элемент не окажется меньше опорного;
если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент;
если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r или l соответственно.
Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.
Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута всегда и обработка гарантированно завершится.

Интересно, что Хоар разработал этот метод применительно к машинному переводу: дело в том, что в то время словарь хранился на магнитной ленте, и если упорядочить все слова в тексте, их переводы можно получить за один прогон ленты.

[_grusha_]

Спасибо за алгоритм)

если возможно, прошу написать код...у меня не хватает мозгов(