Вики
и
Algollist
А также почитал Н. Вирта
Сел писать. Наткнулся на несколько вопросов (раньше я писал уже этот алгоритм, но по-моему я половину "скопипастил").
Нашел здесь сишный код.
- Код: Выделить всё
template<class T>
void quickSortR(T* a, long N) {
// На входе - массив a[], a[N] - его последний элемент.
long i = 0, j = N; // поставить указатели на исходные места
T temp, p;
p = a[ N>>1 ]; // центральный элемент
// процедура разделения
do {
while ( a[i] < p ) i++;
while ( a[j] > p ) j--;
if (i <= j) {
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
}
} while ( i<=j );
// рекурсивные вызовы, если есть, что сортировать
if ( j > 0 ) quickSortR(a, j);
if ( N > i ) quickSortR(a+i, N-i);
}
Начал сравнивать со своим. Не пошло.
Стал отлаживать и сравнивать по шагам. И тут удивился. То что описано в той же вики на самом деле реализовано не так.
Код, приведенный на algollist не соответствует приведенному выше рисунку и описанному алгоритму.
Тестировал на массиве
- Код: Выделить всё
1 7 4 0 9 4 8 8 2 4
Теперь по алгоритму
1. Выбираем опорный элемент - выбирается элемент под индексом 4, значение 9
2. Начиная со первого элемента приращаем счетчика индекса, двигаясь вправо, пока не найдем значение, большее опорного (9). Приходим к тому же опорному элементу - индекс равен 4.
3. Начиная с последнего элемента двигаемся влево, пока не найдем элемент меньше опорного. Находим элемент с индексом 9, значение 4
4. Обмениваем элементы если индекс слева меньше либо равен индексу справа опорного элемента.
Ок, получили массив
- Код: Выделить всё
1 7 4 0 4 4 8 8 2 9
5. Далее в указанных источниках написано что двигаемся дальше по тем же правилам. Приводим в соответствие индексы слева и справа прибавляя и отнимая единицу соответственно. Проверяем, если индекс слева меньше индекса справа - можно продолжать. Опять прибавляем в цикле к левому индексу по единице. Здесь первое несоответствие (которое хоть как-то учтено в вики, но нет на алголлисте) - индекс переходит барьер (индекс 4) и принимает элемент под индексом 9, значение = 9.
6. Двигаемся влево по правому индексу. Находим индекс 8, значение = 2.
7. Проверяем меньше либо равно ли левый индекс правому? Не, не равен, поэтому не обмениваем.
Здесь уже много вопросов. Почем массив не делится на две части как предписано алгоритму? Здесь есть свой нюанс, который указан в вики
Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.
а также
Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
Но в коде все иначе. Не важно куда мы ушли от барьера.
Ладно. Далее. Алгоритм говорит что нужно таким же образом отсортировать левую и правую часть разделенного массива.
Но тут опять код иной. Здесь сортируется массив с 0 по 8-й элемент, а вторая часть естественно не сортируется. Короче дальше получается несколько шагов холостым ходом. Вообще за весь алгоритм правая часть сортируется всего два раза.
У Н. Вирта есть есть ответ почему делает именно так. И написано это оправдано. Но описание алгоритма в источниках и код не соответствуют, и не описано почему так.
Я может конечно туплю, но считаю это неверным.
