Курсовая работа: Информационная система начальника жилищно-эксплуатационной службы

2. Вычисляется индекс опорного элемента m.

3. Индекс l последовательно увеличивается до m до тех пор, пока l-й элемент не превысит опорный.

4. Индекс r последовательно уменьшается до m до тех пор, пока r-й элемент не окажется меньше опорного.

5. Если r = l – найдена середина массива – операция разделения закончена, оба индекса указывают на опорный элемент.

6. Если l < r – найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.

3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.

4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.

Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута всегда и обработка гарантированно завершится.

Этот алгоритм в применении к нашему вектору FArr реализован следующи методом класса TVector:

// xMode = 1 – по возрастанию

// xMode = 2 – по убыванию

// xMode = 0-использовать текущий режим SortMode и затем поменять его

procedure TVector. Sort (xMode: integer = 0);

procedure QSort (l, r: Integer);

function Less (var x, y: Variant): boolean;

begin

if (X < Y) and (SortMode=1) // повозрастанию

then Less:=true

else Less:=false;

end;

var

i, j, x: integer;

y: TVarMas; //Variant;

begin

i:= l; j:= r; x:= (l+r) DIV 2;

repeat

while Less (FArr[i] [SortId], FArr[x] [SortId]) do i:= i + 1;

while Less (FArr[x] [SortId], FArr[j] [SortId]) do j:= j – 1;

if i <= j then