Сортировка без if-ов
Доброго времени суток. Так сложилась жизнь что я от недавнего времени стал гордым студентом одного из лучших вузов своей страны. Хорошо или плохо это вопрос спорный, но это не суть. Самое забавное это то, что на лабораторных работах преподаватель то ли для развлечения, то ли для того, что бы в очередной раз напомнить мне что я весьма паскудно разбираюсь в алгоритмике, время от времени выдает задания отличные от того, что получает оставшаяся группа. Одно из последних, которое, как по мне, достойно вашего внимания является сортировка массива без использования условных операторов (if, switch и тому подобных).
Поскольку я до этого жил в теплом мире фреймворков и библиотек и перед мной никогда не стояло подобных задач я был слегка удивлен такой лабе. В общем не смотря на числительные попытки преподавателя натолкнуть меня на правильное решение фразами вроде “числа ограниченны диапазоном от 0 до 100” и “можно использовать больше одного массива” найти решения не удалось, по крайней мере за период пары. В общем говоря пара закончилась тем, что за 5 минут до ее окончания задания про сортировку было замененною каким-то пустяком вроде подсчета количество разных цифр в числе.
И как иногда случается, вместо того что бы счастливо забыть про эту лабараторку и продолжать радоваться жизни я время от времени возвращался к задачи сортировки, и все таки придумал ее решение. Собственно им и хочу с вами поделиться. Оно вышло на удивления простым и без использования дополнительных массивов(поэтому скорей всего у задачи существует еще одно решение, наверное).
Вот собственно говоря код программы:
#include <iostream>
using namespace std;
int myAbs(int a){
int oldByte = (a >> 31)& 0x1;
return -a*(1+oldByte-1)-a*(oldByte-1);
}
int getMax(int a, int b) {
return (a + b + myAbs(a - b)) / 2;
}
int getMin(int a, int b) {
return (a + b - myAbs(a - b)) / 2;
}
int main() {
int arr[] = {34, 12, 24, 65, 63, 22};
int arraySize = (sizeof(arr) / sizeof(*arr));
int maxPosition = 0;
int maxElement = arr[0];
int minValue= arr[0];
for (int k = 0; k < arraySize; k++) {
for (int i = k; i < arraySize; i++) {
int newMax = getMax(maxElement, arr[i]);
minValue = getMin(minValue, arr[i]);
maxPosition =getMin((myAbs(newMax ^ maxElement) + 1) * (maxPosition + 1), (myAbs(newMax ^ arr[i]) + 1) * (i + 1)) -1;
maxElement = newMax;
}
int buf = arr[k];
arr[k] = maxElement;
arr[maxPosition] = buf;
maxElement = minValue;
}
for(int a:arr){
cout<<a<<endl;
}
return 0;
}
P.S. В универе бывает даже интересно.
