Валерий Лаптев писал(а):
alexus писал(а):
В самом обмене нет никакой необходимости... если переформулировать (не меняя сути!) исходную для цикла задачу.
Исходная задача цикла: переставить удаленные элементы поближе к нужному месту.
... переставить элементы в порядке возрастания/убывания их значений.
Валерий Лаптев писал(а):
Делается это относительно некоего "разделяющего" элемента х.
... этот элемент иногда называют медианой...
Вопрос, который меня интересовал... почему медиану предпочитают выбирать из середины последовательности/массива. С точки зрения логики, любой элемент можно выбрать в качестве медианы, если исходить из того, что значения элементов распределены случайным образом. Таким образом, определять середину последовательности не обязательно, можно в качестве медианы использовать первый элемент последовательности, например.
Выбор медианы из середины последовательности, позволяет написать два цикла, первый будет просматривать элементы до медианы, второй, после медианы:
Код:
m := (left + right) div 2; // выбираем медианный элемент
x := a[m]; // получаем медиану
i := left;
j := right;
while (a[i] < x) do inc(i); // просматриваем левую часть
while (a[j] > x) do dec(j); // просматриваем правую часть
Можно легко убедиться, что оба этих цикля являются подмножествами более общего цикла, когда мы просматриваем обе части последовательности, поочередно, то слева, то справа... пока не найдём "нужное место" для медианного элемента. "Нужное место" - это то место, где слева будут находиться элементы со значениями не больше медианного значения, а справа, соответственно, будут находиться все элементы со значениями не меньше медианного значения. Таким образом, задача свелась к тому, что надо найти "нужное место", попутно перенося меньшие элементы влево, а большие элементы вправо. Но операция переноса, не тождественна операции обмена, это всего одно присваивание, а не три...