Добрый день!
Ничего не могу поять. Я уже делал быструю сортировку на джаве, сейчас читаю Вирта, попробовал ТОЧЬ-В-ТОЧЬ реализовать его алгоритм (такой же, кстати, и на википедии), и у меня ничего не получается на этапе разделения массива на 2 подмассива. Набор чисел такой, например: 6 39 5 33 9 18 40 42 49 23
Алгоритм (взято с вики):
введите код здесь
procedure sort(var ar: array of real; low, high: integer);
var i, j: integer;
m, wsp: real;
begin
i:=low; //начальный индекс для итерации, 0 в нашем случае
j:=high; //конечный индекс, 9 в нашем случае
m:=ar[(i+j) div 2]; // Взятие среднего опорного элемента, в нашем случае это 9, индекс - 4
repeat
while ar[i]<m do Inc(i); //увеличиваем начальный итератор, прекратится while когда индекс будет 1 (значение 39)
while ar[j]>m do Dec(j); //уменьшаем конечный итератор, получаем индекс опорного элемента 4 (значение 9)
if i<=j then begin //условие соблюдено, далее -
wsp:=ar[i]; ar[i]:=ar[j]; ar[j]:=wsp; //меняем их местами, массив теперь выглядит так: 6 9 5 33 39 18 40 42 49 23,
Inc(i); Dec(j); // а индексы 2 и 3 соответственно
end;
until i>j;
/// условие соблюдено, идем на следующий шаг внешнего цикла -
//while ar[i]<m do Inc(i); - увеличиваем начальный итератор до индекса 3 (значение 33)
//while ar[j]>m do Dec(j); уменьшаем конечный индекс до 2 (значение 5)
// if i<=j -все, условие не выполнено, конец
//В результате мы получили массив 6 9 5 33 39 18 40 42 49 23, в котором нет никакого смысла - и слева, и справа от 9 есть элементы со значением ниже
//Если смотреть относительно конечных индексов и начального индекса опорной точки - то же самое.
Так вот, я часто начинаю вот так подробно расписывать что-то на форуме, и почти всегда в процессе написания я разбираюсь что к чему (как кто-то великий говорил, что кот его кот очень хороший программист, т.к. если ему начать подробно рассказывать о своей проблеме, как ни странно, зачастую находится ее решение). Вот сейчас не разобрался. Помогите.
>= 9
. В массиве образовались «дыры», и вы уплотнили его влево. Потом то же для остальных элементов. Вот только эта операция проводится без фактического удаления, «на месте». Есть?