Здравствуйте, Sinclair, Вы писали:

S>Очевидно, переставляем элементы внутри подмассива от i до j так, чтобы сначала шли все элементы меньше pivot, а потом — все элементы больше pivot.
S>Конкретнее:
S>1. Ищем слева элемент, >= pivot
S>2. Ищем справа элемент <= pivot
S>3. Меняем их местами, и сдвигаем границы на следующую пару элементов.

Ну ок, теперь вроде понятно. Хотя надо ещё проверить, нет ли в gpt-шном алгоритме потенциального бага — в левую или правую часть пойдут эти элементы, если оба они = pivot? Т.е. как вы написали наверно уже неправильно, а это как GPT выдал; надо определиться что элементы, равные pivot, надо поместить например конкретно в левую часть, тогда надо наверно так:

repeat
while arr[i] <= pivot do
Inc(i);
while arr[j] > pivot do
Dec(j);

if i <= j then
begin
temp := arr[i];
arr[i] := arr[j];
arr[j] := temp;
Inc(i);
Dec(j);
end;
until i > j;

Кроме того, легко сделать ошибки, если например модифицировать этот алгоритм для указания ascending (сортировка по возрастанию или убыванию). Поэтому повторю моё мнение, что оптимальным является мой алгоритм в оп, он только в три раза медленнее gpt-шного, для 99.999% задач это неважно. Ну а если уж очень надо оптимизировать — тогда можно заменить его на gpt-шный.

K>>Как бы смутно уже понятно, но хочется чтобы кто-то сказал словами, так не придётся много думать.
S>Это вы зря. Мыслительный мускул нужно тренировать.

Не так. Ресурсы мозга ограничены, если их экономить тут — можно больше потратить на другое.

Здравствуйте, Sinclair, Вы писали:

S>Очевидно, переставляем элементы внутри подмассива от i до j так, чтобы сначала шли все элементы меньше pivot, а потом — все элементы больше pivot.
S>Конкретнее:
S>1. Ищем слева элемент, >= pivot
S>2. Ищем справа элемент <= pivot
S>3. Меняем их местами, и сдвигаем границы на следующую пару элементов.

Ну ок, теперь вроде понятно. Хотя надо ещё проверить, нет ли в gpt-шном алгоритме потенциального бага — в левую или правую часть пойдут эти элементы, если оба они = pivot? Т.е. как вы написали наверно уже неправильно, а это как GPT выдал; надо определиться что элементы, равные pivot, надо поместить например конкретно в левую часть, тогда надо наверно так:

repeat
while arr[i] <= pivot do
Inc(i);
while arr[j] > pivot do
Dec(j);

if i < j then
begin
temp := arr[i];
arr[i] := arr[j];
arr[j] := temp;
Inc(i);
Dec(j);
end;
until i >= j;

И я заменил if i <= j then на if i < j then, это не был баг но чуть некрасиво.


Кроме того, легко сделать ошибки, если например модифицировать этот алгоритм для указания ascending (сортировка по возрастанию или убыванию). Поэтому повторю моё мнение, что оптимальным является мой алгоритм в оп, он только в три раза медленнее gpt-шного, для 99.999% задач это неважно. Ну а если уж очень надо оптимизировать — тогда можно заменить его на gpt-шный.

K>>Как бы смутно уже понятно, но хочется чтобы кто-то сказал словами, так не придётся много думать.
S>Это вы зря. Мыслительный мускул нужно тренировать.

Не так. Ресурсы мозга ограничены, если их экономить тут — можно больше потратить на другое.