albobin писал(а):
alexus писал(а):
Таким образом, задача свелась к тому, что надо найти "нужное место", попутно перенося меньшие элементы влево, а большие элементы вправо. Но операция переноса, не тождественна операции обмена, это всего одно присваивание, а не три...
Интересно, продолжает ли автор настаивать на своём тезисе.
К слову, обмен в исходном варианте - это два переноса у автора, выполняющихся в разных ветках
Операции переноса (присваивания) разнесены по разным веткам. Согласен с тем, что эквивалентом операции обмена в алгоритме оригинальной быстрой сортировке надо считать две операции переноса (два присваивания вместо трёх). Вы правы. Приношу извинения. Возможно, меня подвело то, что перенос спаривается со следующей операцией (выполнение нескольких операций за такт), а обмен не спаривается из-за зависимостей по данным. В результате обмен длится несколько дольше... (но это уже относится не к алгоритму, а его ассемблерной реализации)
Добавлю для Алексей Донского...
Для борьбы с избыточной рекурсией в алгоритме быстрой сортировки можно использовать интересный приём. Суть его состоит в следующем: когда мы нашли место для элемента (x), то дальше следуют два рекурсивных вызова процедуры QS, один для левой части, второй для правой части последовательности (массива). После этого процедура QS завершает свою работу.
Код:
dec(i); inc(j);
if (l < i) then QS(l, i);
if (j < r) then QS(j, r);
Так вот, второй рекурсивный вызов можно заменить (без потери работоспособности сортировки) на безусловный переход к началу процедуры. На ЯВУ это сделать затруднительно, на ассемблере - легко. Но если такое возможно, тогда и один оставшийся рекурсивный вызов можно оптимизировать. Надо делать рекурсивный вызов не для левой и не для правой, а для наименьшей (из них) последовательности (наиболее короткой из 2-х частей массива). Например, i - l = 5, r - j = 12, тогда сначала делаем рекурсивный вызов QS(l, r), а затем GoTo(j, r). Если же i- l = 34, а r - j = 18, то тогда делаем QS(j, r) и затем GoTo(l, i). К сожалению, проиллюстрировать этот трюк на Паскале невозможно, но если интересно, то могу привести листинг на ассемблере (он кстати не намного больше по количеству строк, чем приведённый алгоритм на Паскале).