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

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

S>>

S>>Создайте систему, которой сможет пользоваться дурак, и только дурак захочет ею пользоваться.

K>Вот в стандартном алгоритме со схемой Хоара есть фрагмент:

K>

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

K>Как бы немного смущает, что если i=j, то алгоритм впустую произведёт обмен.
1. Давайте попробуем оценить, насколько велики потери от этого бесполезного обмена. Смотрите, на каждой итерации сортировки условие i == j встречается не более одного раза; значит, в худшем случае, алгоритм сделает столько же лишних обменов, сколько будет проходов сортировки. Количество проходов у нас зависит от длины массива: если массив длиной, скажем, 2, то обмен будет ровно 1. Если у нас массив длины N сортируется за X проходов, то массив длины N*2 будет сортироваться за 2X+1 проходов (две сортировки подмассивов по N элементов, плюс ещё один проход перед тем, как вызвать эти две сортировки). Отсюда мы понимаем, что X ~ Log2(N). Логарифмическая асимптотика затрат нас пугать не должна, т.к. она растёт достаточно медленно. Кроме того, мы знаем, что асимптотика quicksort — N * log(N), то есть она в N раз хуже, чем наши дополнительные затраты.
K>Я попробовал заменить if i <= j then на if i < j then, ан нет — начались глюки.
2. Если мы хотим исправить алгоритм, нужно внимательно смотреть на то, что он делает. Очевидно, что помимо обмена, под if стоят ещё и инкременты/декременты i и j. Если их не делать, то семантика алгоритма поменяется — отсюда и глюки.
3. С учётом вышесказанного, понятно, что просто поменять условие сравнения нельзя. Придётся сделать две раздельных проверки — одну про необходимость обмена, вторую — про необходимость перемещения счётчиков.

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

Возникает вопрос: а много ли мы экономим? Мы экономим один лишний обмен для i == j, но зато теперь мы на каждой итерации дополнительно сравниваем i и j. Результат может зависеть от точных стоимостей обмена и сравнения. Если в массиве лежат какие-то простые значения, то перестановка — это копирование память-регистр-память и сводится к трём инструкциям CPU. Если там структуры — то копирование может потребовать чего-то более существенного. Проверка — это сравнение регистр-регистр, к тому же она будет неплохо предсказываться процессором, и вряд ли приведёт к потерям больше 1 такта на итерацию.
Но, вспомнив, что в среднем наша "оптимизация" срабатывает 1 раз из N, получаем, что с ростом длины массива даже дорогие обмены будут задоминированы стоимостью дополнительной проверки.
Bottom line: чтобы понять, какой будет реальный эффект в конкретной задаче, нужно точно замерить производительность. Если вас интересует экономия уровня единиц процентов — тогда да, настраиваем окружение, обучаемся корректно тестировать производительность (со сбором статистики, отбрасыванием нерелевантных результатов, и оценкой значимости разницы), тюним всё до мелочей. Если интересует асимптотическая оптимизация — то останавливаемся прямо на шаге №1 выше: наша оптимизация на асимптотику не повлияет, так что лучше не трогать то, что не сломано.
K>Такие подводные камни могут всё порушить в программе. Поэтому повторюсь что мой изначальный алгоритм, как мне кажется, во многих отношениях предпочтителен.
Ваш изначальный алгоритм проигрывает коробочному во всех отношениях:
1. Он протестирован заведомо не лучше, чем библиотечная реализация. Просто потому, что у вас нет столько ресурсов, сколько у производителей библиотеки.
2. Он работает медленнее — стало быть, задачу "оптимизации" он не решил.
3. Он гораздо более хрупкий — вы не умеете вносить изменения в алгоритмы так, чтобы не ломать их семантику; и написан он (в отличие от коробочной реализации) без разделения на логику сравнения элементов и логику выбора того, когда и какие элементы сравнивать.