noname00.pas
08-01-2002, 12:56
Идея метода заключается в следующем: выбираем в массиве произвольный элемент и ставим его "на своё место". Все элементы меньшие выбранного должны оказаться слева, а больше справа. И потом просто вызываем рекурсивную процедурку, которая аналогичным образом отсортирует левую и правую части массива.
Пример кода:
procedure swap(var a, b : integer);
var
*c : integer;
begin
*c := a;
*a := b;
*b := c;
end; *{Это просто процедурка, которая меняет местами значения A и B}
procedure sort(l, r : integer);
var
*Y, j, x : integer;
begin
*Y := l;
*j := r; {с помощью указателей Y и J мы будем "двигаться по массиву"}
*x := a[(l + r) div 2]; {выбрали произвольный элемент. Например из серединки}
*repeat
* *while (a[Y] < x) do inc(Y); {Двигаем левый указатель до близжайшего элемента, большего X}
* *while (a[j] > x) do dec(j); {Двигаем правый указатель до близжайшего элемента, меньшего X}
* *if Y <= j then begin
* * *swap(a[Y], a[j]);
* * *inc(Y);
* * *dec(j);
* *end; {поменяли элементы местами, сдвинули указатели}
*until Y > j;
*if Y < r then sort(Y, r);
*if j > l then sort(l, j);
end;
As is (я не несу ответственности за последствия получения вами данного кода)
Праверьте ещё раз, правильно ли работает... Если что - стучите :)
[Гневные ругательства в адрес BigMac-а]
Кстати говоря... Паскалевское обращение к элементу массива вида A[W], где вместо "W" стоит "I" твой форум распознал как открытие тэга... Сделай примочку, которая в тэге CODE игнорирует все другие тэги...
[/Гневные ругательства в адрес BigMac-а]
(Отредактировал(а) noname00.pas - 10:06 8-01-2002)
Пример кода:
procedure swap(var a, b : integer);
var
*c : integer;
begin
*c := a;
*a := b;
*b := c;
end; *{Это просто процедурка, которая меняет местами значения A и B}
procedure sort(l, r : integer);
var
*Y, j, x : integer;
begin
*Y := l;
*j := r; {с помощью указателей Y и J мы будем "двигаться по массиву"}
*x := a[(l + r) div 2]; {выбрали произвольный элемент. Например из серединки}
*repeat
* *while (a[Y] < x) do inc(Y); {Двигаем левый указатель до близжайшего элемента, большего X}
* *while (a[j] > x) do dec(j); {Двигаем правый указатель до близжайшего элемента, меньшего X}
* *if Y <= j then begin
* * *swap(a[Y], a[j]);
* * *inc(Y);
* * *dec(j);
* *end; {поменяли элементы местами, сдвинули указатели}
*until Y > j;
*if Y < r then sort(Y, r);
*if j > l then sort(l, j);
end;
As is (я не несу ответственности за последствия получения вами данного кода)
Праверьте ещё раз, правильно ли работает... Если что - стучите :)
[Гневные ругательства в адрес BigMac-а]
Кстати говоря... Паскалевское обращение к элементу массива вида A[W], где вместо "W" стоит "I" твой форум распознал как открытие тэга... Сделай примочку, которая в тэге CODE игнорирует все другие тэги...
[/Гневные ругательства в адрес BigMac-а]
(Отредактировал(а) noname00.pas - 10:06 8-01-2002)