Как отсортировать три переменные, используя не более двух перестановок?
Следующий алгоритм может сортировать три переменные 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,b, с). Однако одного обмена было бы достаточно: (c,b,a) -> (a,b,c).
Каковы будут простейшие алгоритмы, которые сортируют три переменные с максимум двумя перестановками во всех случаях?
10 ответов
Найдите самое маленькое, для этого нужно 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 сравнения.
От 2 до 3 сравнений, от 0 до ~1,7 свопов
Старый вопрос, новый ответ... Следующий алгоритм сортирует 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);
}
}
}
}
Итак, как это работает? Это просто развернутая сортировка вставок: если значения уже отсортированы (для проверки требуется 2 сравнения), то алгоритм ничего не меняет. В противном случае он выполняет 1 или 2 операции обмена. Однако, когда требуются 2 операции свопинга, алгоритм "вращает" значения вместо этого, так что вместо 6 выполняется 4 хода (операция свопа должна стоить 3 хода, если не оптимизирована).
Есть только 6 возможных перестановок из 3 значений. Этот алгоритм выполняет сравнения, необходимые для того, чтобы узнать, какую перестановку мы обрабатываем. Затем он делает обмен и уходит. Следовательно, алгоритм имеет 6 возможных путей (включая тот, где он ничего не делает, потому что массив уже отсортирован). Несмотря на то, что он по-прежнему удобочитаем для человека, эквивалентно оптимальный алгоритм для сортировки 4 значений будет иметь 24 различных пути и будет намного сложнее для чтения (для n значений существует n! Возможных перестановок).
Поскольку мы уже находимся в 2015 году, и вы, похоже, используете C++, я взял на себя смелость std::move поэтому, чтобы быть уверенным, что вещь со своп-вращением будет достаточно эффективной и будет работать даже для перемещаемых, но не копируемых типов.
Найдите минимальное значение и поменяйте его на первое. Найдите второй минимум и поменяйте его на второе значение. Максимум два обмена.
В основном это сортировка выбора, которая будет выполнять максимально n - 1 свопы.
Если вы не сделаете это на месте, вы можете выполнить это без каких-либо перестановок.
Классный вопрос:)
Если вам доступна сборка и значения помещаются в регистр, то вы, вероятно, сможете сделать это очень быстро, просто загрузив их в регистры и выполнив несколько сравнений, перейдя к правильному сценарию, чтобы вернуть значения обратно. Может быть, ваш компилятор уже делает эту оптимизацию.
В любом случае, если ваша цель - производительность, посмотрите на сгенерированный машинный код и оптимизируйте его. Для такого маленького алгоритма вы можете выжать производительность.
Кодировать сортировочную сеть в таблице. Статья в Википедии, на которую я ссылаюсь, должна помочь вам со ссылками на тот случай, если вам нужно выяснить, что поместить в таблицу в других случаях (например, в больших массивах).
Недавно мне пришлось решить аналогичную проблему - эффективно отсортировать три значения. Вы концентрируетесь на swap-операциях в своем вопросе. Если вам нужна производительность, сконцентрируйтесь на операциях сравнения и ветвях! При сортировке такого "крошечного" массива всего с тремя значениями хорошей идеей будет рассмотреть вопрос об использовании дополнительного хранилища, которое подходит для стольких значений. Я придумал что-то вроде специализированной "сортировки слиянием" (см. Код ниже).
Как и предположил Тенфур, я посмотрел на сборку, и приведенный ниже код компилируется в компактный встроенный набор операций регистрации ЦП и работает очень быстро. Дополнительная переменная "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
}
Я думаю, что вы хотите найти оптимальный своп на каждом шаге, а не просто действительный своп. Чтобы сделать это, просто найдите наибольшую разницу между элементом и элементом позже в списке и поменяйте их местами. В кортеже 3 есть три возможных перестановки: 1-3, 1-2 и 2-3. На каждом шаге найдите максимальную разницу между этими тремя перестановками и сделайте это. Уверен, что дает два обмена в худшем случае на 3 элемента. Это действительно имеет смысл, только если обмен сравнительно дорог по сравнению со сравнением элементов, в противном случае, вероятно, не стоит дополнительного анализа заранее.
Это можно проиллюстрировать таблицей истинности, относящейся к каждой возможной комбинации сравнений, чтобы увидеть, как мы можем наилучшим образом оптимизировать своп, который вы упомянули здесь.
Ценности | х <у | y х, у, г | у | у | Y х, г, у | у | п | Y у, х, г | п | у | Y у, г, х | п | у | N z, x, y | у | п | N z, y, x | п | п | N Если сформулировать вопрос таким образом, мы легко увидим, что при первоначальной проверке и замене 1-го и 3-го элемента наименьшее значение, которое мы можем иметь в первом элементе после перестановки, может быть либо x, либо y. Это упрощает проверку if после этого, так что мы можем либо поменять 1-й и 2-й элемент, когда x> y, либо поменять местами 2-й и 3-й элемент, когда y> z. Нет необходимости во вложенных условных выражениях. Всего 2-3 простых сравнения для 2 свопов при макс.if (x > z) {
swap(x,z);
}
if (x > y) {
swap(x,y);
} else if (y > z) {
swap(y,z);
}