Следующий алгоритм может сортировать три переменные x, y и z типа K, которые сопоставимы с помощью operator<:
void sort2(K& x, K& y) {
if(y < x)
swap(x, y);
}
void sort3(K& x, K& y, K& z) {
sort2(x, y);
sort2(y, z);
sort2(x, y);
}
Это требует трех свопов в "худшем случае". Однако основная математика говорит нам, что упорядочение трех значений может быть выполнено с использованием только двух свопов.
Пример: значения (c, b, a) будут отсортированы с использованием трех свопов: (c, b, a) → (b, c, a) → (b, a, c) → (a,До нашей эры). Однако одного свопа было бы достаточно: (c, b, a) → (a, b, c).
Какими будут самые простые алгоритмы, которые сортируют три переменные с не более чем двумя свопами во всех случаях?
Найти наименьшее, это займет 2 сравнения и поменять его на первую позицию. Затем сравните оставшиеся 2 и при необходимости замените.
if (x < y) {
if (z < x) swap(x,z);
} else {
if (y < z) swap(x,y);
else swap(x,z);
}
if(z<y) swap(y,z);
Это занимает 3 сравнения, но только два свопа.
void sort(int& a, int& b, int& c)
{
swap(a, min(a, min(b, c)));
swap(b, min(b, c));
}
2 свопа, 3 сравнения.
Найдите минимальное значение и замените его первым значением. Найдите второй минимум и замените его вторым значением. Два свопа не более.
В основном это сортировка выбора, которая будет выполнять не более n - 1 свопов.
Старый вопрос, новый ответ... Следующий алгоритм сортирует x, y и z с 2 по 3 сравнения в зависимости от их значений и от 0 до ~ 1.7 операций свопинга.
void sort3(K& x, K& y, K& z)
{
if (y < x) {
if (z < x) {
if (z < y) {
swap(x, z);
} else {
K tmp = std::move(x);
x = std::move(y);
y = std::move(z);
z = std::move(tmp);
}
} else {
swap(x, y);
}
} else {
if (z < y) {
if (z < x) {
K tmp = std::move(z);
z = std::move(y);
y = std::move(x);
x = std::move(tmp);
} else {
swap(y, z);
}
}
}
}
Итак, как это работает? Он basiccaly разворачивается сортировка вставки: если значения уже отсортированы (для проверки это требуется 2 сравнения), то алгоритм ничего не меняет. В противном случае он выполняет 1 или 2 операции свопинга. Однако, когда требуются 2 операции свопинга, алгоритм "вращает" значения вместо этого, так что выполняется 4 хоста вместо 6 (операция свопинга должна стоить 3 ходов, если оптимизировано).
Существует только 6 возможных перестановок из 3 значений. Этот алгоритм выполняет сравнения, чтобы знать, какую перестановку мы рассматриваем. Затем он обменивается и уходит. Следовательно, алгоритм имеет 6 возможных путей (включая тот, где он ничего не делает, потому что массив уже отсортирован). Хотя он все еще доступен для человека, эквивалентный оптимальный алгоритм для сортировки значений 4 будет иметь 24 разных пути и будет намного сложнее читать (для n значений возможны n! Возможные перестановки).
Поскольку мы уже в 2015 году, и вы, похоже, используете С++, я воспользовался свободой std::move, чтобы убедиться что swap-rotate thingy будет достаточно эффективным и будет работать даже для подвижных, но не копируемых типов.
Если вы не сделаете это на месте, вы можете выполнить его без каких-либо свопов.
Кодировать сортировочную сеть в таблице. Статья, связанная с Википедии, должна помочь вам со ссылками, если вам нужно выяснить, что положить в таблицу в других случаях (т.е. Больше массивов).
Я думаю, что вы хотите найти оптимальный своп на каждом шаге, а не только действительный своп. Для этого просто найдите наибольшую разницу между элементом и элементом позже в списке и замените их. В 3-кортеже есть три возможных свопа: 1-3, 1-2 и 2-3. На каждом шаге найдите максимальное различие между этими тремя свопами и сделайте это. Довольно уверен, что дает два свопа в худшем случае для 3 элементов. Только действительно имеет смысл, если обмен происходит относительно дорого по сравнению с сравнением элементов, иначе, вероятно, не стоит дополнительного анализа авансом.
Холодный вопрос:)
Если сборка доступна для вас и значения, вписываемые в регистр, то вы, вероятно, можете сделать это очень быстро, просто загрузив их в регистры и сделав несколько сравнений, перепрыгнув в нужный сценарий, чтобы вернуть значения. Возможно, ваш компилятор уже делает эту оптимизацию.
В любом случае, если производительность является вашей целью, взгляните на сгенерированный машинный код и оптимизируйте его. Для такого небольшого алгоритма, где вы можете выжать производительность из.
Недавно мне пришлось решить подобную проблему - эффективно сортировать три значения. Вы концентрируетесь на своп-операциях в своем вопросе. Если производительность - это то, что вы ищете, сосредоточьтесь на операциях сравнения и ветких! При сортировке такого "крошечного" массива с тремя значениями хорошей идеей является рассмотрение использования дополнительного хранилища, которое подходит для стольких значений. Я придумал нечто вроде специализированного "сортировки слияния" (см. Код ниже).
Точно так же, как tenfour, я посмотрел на сборку, а приведенный ниже код скомпилирован до компактного встроенного набора операций с регистром CPU и очень быстро. Дополнительная переменная "arr12" также сохраняется в регистрах CPU. Для сортировки требуются две или три операции сравнения. Функция может быть легко преобразована в шаблон (здесь не приводится для ясности).
inline void sort3_descending( double * arr )
{
double arr12[ 2 ];
// sort first two values
if( arr[ 0 ] > arr[ 1 ] )
{
arr12[ 0 ] = arr[ 0 ];
arr12[ 1 ] = arr[ 1 ];
} // if
else
{
arr12[ 0 ] = arr[ 1 ];
arr12[ 1 ] = arr[ 0 ];
} // else
// decide where to put arr12 and the third original value arr[ 3 ]
if( arr12[ 1 ] > arr[ 2 ] )
{
arr[ 0 ] = arr12[ 0 ];
arr[ 1 ] = arr12[ 1 ];
} // if
else if( arr[ 2 ] > arr12[ 0 ] )
{
arr[ 0 ] = arr [ 2 ];
arr[ 1 ] = arr12[ 0 ];
arr[ 2 ] = arr12[ 1 ];
} // if
else
{
arr[ 0 ] = arr12[ 0 ];
arr[ 1 ] = arr [ 2 ];
arr[ 2 ] = arr12[ 1 ];
} // else
}
Это может быть проиллюстрировано таблицей истинности, относящейся ко всей возможной комбинации сравнений, чтобы увидеть, как мы можем оптимально оптимизировать своп, который вы упомянули здесь.
Значения | x < y | y < z | x < г
x, y, z | y | y | у
x, z, y | y | n | у
y, x, z | n | y | у
y, z, x | n | y | п
z, x, y | y | n | п
z, y, x | n | n | п
Обращая вопрос таким образом, мы можем легко увидеть, что, сначала проверяя и заменяя 1-й и 3-й элементы, наименьшее значение, которое мы можем иметь в первом элементе после свопа, может быть либо x, либо y. Это упрощает проверку if, чтобы мы могли либо поменять 1-й и 2-й элементы при x > y, либо заменить 2-й и 3-й элементы при y > z.
if (x > z) {
swap(x,z);
}
if (x > y) {
swap(x,y);
} else if (y > z) {
swap(y,z);
}
Не требуется никаких вложенных условных выражений. Всего 2-3 простых сравнения для 2 свопов при макс.