|
Цитата:
|
Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:
1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:
2.1 Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.
2.2 Вычисляется индекс опорного элемента m. (??? а п.1 что делал?)
2.3 Индекс l последовательно увеличивается до m до тех пор, пока l-й элемент не превысит опорный.
2.4 Индекс r последовательно уменьшается до m до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
2.5 Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
2.6 Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.
3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.
|
вся соль разделения массива заключается в подчеркнутой строчке?
Алгоритм 2.N выполняется только 1 раз для целого массива? Далее он выполняется для левых и правых подмассивов?
Как все это с sort(foo(a,b)) в JS стыкуется?
a,b - это что за элементы относительно вышеописанного?
просто любые 2 элемента, а в функции показано условие?