Сортировка массива без использования условных операторов

Сразу предупреждаю, что данная статья будет альтернативной версией вот этой. Да, я уж прям чую как все сразу ринуться меня критиковать, но, ребята, алгоритм представлений в решении не оптимален. В комментариях предлагали еще более простые алгоритмы, на питоне. На питоне достаточно написать:

array.sort()

И все. Кому нужен вообще какой-то алгоритм. В задании было установлено ограничение от 0 до 100, мы же не лентяи, сделаем в общем виде, для любых значений и с повторениями чисел. Немного подумав, пришел вот к такому решению:

Код
public class main {
	
	public static int max(int a, int b) {
		int i;
		for (i = 0; i < a - Math.abs(b);) {
			return a;
		}
		return Math.abs(b);
	}
	public static void main(String[] args) {
		int[] arrayForSort;
		int[] sortArray;
		int NUM_ELEMENT = 20, maxNum = -1000, i, j;
		arrayForSort = new int[NUM_ELEMENT];
		for (i = 0; i < NUM_ELEMENT; i++) {
		     arrayForSort[i] = (int) (Math.random() * 101) - 50;
		     maxNum = max(maxNum, arrayForSort[i]);
		     System.out.print(arrayForSort[i] + " ");
		}
		System.out.println();
		sortArray = new int[maxNum * 2 + 1];
		for (i = 0; i < NUM_ELEMENT; i++) {
			sortArray[arrayForSort[i] + maxNum]++;
		}
		for (i = 0; i <= maxNum * 2; i++) {
			for (j = 0; j < sortArray[i]; j++) {
				System.out.print(i - maxNum + " ");
			}
		}
	}
}


А теперь, разберем что я тут написал.

В общем-то, проблема состоит в нахождение минимума и максимума, так как сравнение мы не можем использовать, то:

public static int max(int a, int b) {
		int i;
		for (i = 0; i < a - Math.abs(b);) {
			return a;
		}
		return Math.abs(b);
	}

Если B по модулю будет больше чем А, то цикл попросту не выполнится и пойдет на возврат. Это довольно простое решение. Без «великих» математических формул. Просто и понятно. И еще: почему я беру по модулю? Это вызвано методом сортировки, который я использую.

В оригинальной статье используется сортировка «с флажком» (если я правильно понял). Выполнение такой сортировки при самом плохом случае О(N^2) (или близко к этому), что не есть хорошо.

Этот метод (не помню его название, искать не царское это дело лень), решит за О(N) даже при том что числа будут повторяться.

for (i = 0; i < NUM_ELEMENT; i++) {
	sortArray[arrayForSort[i] + maxNum]++;
}

Суть сортировки заключается в том что при заполнении массива он сам сортирует себя. Значение мы представляем в виде индекса и увеличиваем количество элементов в этом индексе.

Пример
Мы два раза встретили число 44, значит в отсортированном массиве по индексу 44 будет содержаться 2. Это просто!

Как оказалось (то ли я криворукий), массивы создаются от 0 до N и как я не старался сделать от -N до N, безуспешно. Поэтому делаем смещение, поэтому ищем максимум с модулем. Потом просто отражаем относительно 0 и получаем диапазон индексов в который точно влезут все элементы, кроме граничного, так что +1.

Пояснение
Мы получим минимум -48, а максимум 38. Так мы берем что минимум -48, а макс 48, для упрощение алгоритма. И смещаем так чтобы минимум был на 0 -48+48

sortArray = new int[maxNum * 2 + 1];
. . .
sortArray[arrayForSort[i] + maxNum]++;
. . .
System.out.print(i - maxNum + " ");

На этом у меня все. Поставленную задачу выполнил, при этом оптимизировав процесс и представив свое видение решения данной задачи.

Пример вывода
35 -29 26 17 -44 -10 31 -22 24 2 -28 17 2 -36 -30 35 39 -35 41 50
-44 -36 -35 -30 -29 -28 -22 -10 2 2 17 17 24 26 31 35 35 39 41 50
Share post

Comments 27

    +3
    Угу. Так какая алгоритмическая сложность у вашего алгоритма? И какие требования по памяти?

      0
      Я могу ошибаться но o(N) что описано выше. Да по памяти сожрет много, но это зависит от диапазона значений и даже если будет большой диапазон то это не повлияет на сортировку а только затруднит вывод, но вывод не является ключевым здесь. Так что…
        0
        Вы ошибаетесь. По памяти — О(m), где m — максимальное значение в массиве. Так что слово «много» не описывает.
          –2
          Нет, сортировке не важно максимальное значение, играет роль только количество элементов
          for (i = 0; i < NUM_ELEMENT; i++) {
          	sortArray[arrayForSort[i] + maxNum]++;
          }
          

          NUM_ELEMENT=20…
          Вот весь метод сортировки.
          Максимальное повлияет только в выводе, так как нам нужно пройтись по всей длине массива, но это не входит в задачу.
            0
            Ох.

            Каков размер sortArray?
              0
              Максм*2 но мы обращаемся к нему только NUM_ELEMENT=20… раз
                0
                Максм*2

                Вот поэтому и получается O(m) по памяти.

                (а вы думаете, зря в качестве доминирующих алгоритмов сортировки используются comparison-based, у которых алгоритмическая стоимость в log(N) раз больше вашей?)
                  0
                  Простите, я очень не внимательный человек. Да по памяти будет o(m)… я подумаю над тем как оптимизировать, собственно это будет как другой метод сортировки.
                    0
                    … и в итоге вы вернетесь к тому, что уже обсуждено в комментариях к исходной статье.

                    Собственно, ваш вариант решения там тоже есть (только с ограничением на «только положительные», но это не имеет фундаментального значения)
          0
          > Я могу ошибаться но o(N) что описано выше.

          Если не ошибаюсь, то O(m^2), где m — максимальное число массива. Интересно, что от N он вообще не зависит, по сути.

          Всё дело в функции вывода, без которого такая сортировка бессмысленна.
        +8
        Ну и да, использование цикла с мгновенных выходом «вместо» сравнения — это жульничество.
          –2
          Простите что? Выход из цикла это жульничество? В любом языке можно реализовать такой выход. Так что, шансы равны.
            +3
            Ваш цикл с выходом — это то же самое сравнение, поэтому вы нарушили условие «без сравнений».
              –1
              Это не условный оператор, он содержит условие.В оригинальной статье циклы использовались, да и в любом цикле присутствует условие.
                0
                В оригинальной статье циклы использовались,

                В оригинальной статье циклы использовались только для обходов массива, и это допущение, на которое все были согласны. А в комментариях есть решение, которое и для этого не использует циклы.
            0
            P.S Даже на паскале есть кривой но все-же break
              +1
              Обычный break, не кривее других.
            +4
            После компиляции условие в цикле ничем не отличается от if.
              –3
              В этом и суть. Я же не использовал в своем коде условных операторов, то что это упроститься компилятором до условия меня не волнует.
                0
                Ниже верно заметили что > — условный оператор. Когда речь заходит о переписывании алгоритма без условных операторов — на самом деле разговор идёт об оптимизации. Об очень специфичной оптимизации, которая имеет смысл только в настоящих числодробилках, а именно — исключение возможности неправильного угадывания процессором ветки алгоритма исполняемой далее.
                В современных процессорах есть множество простаивающих блоков. В целях оптимизации на некоторых из них происходит дальнейшее выполнение программы ещё в тот момент когда исполняется проверка условия. Если предсказание ветки было верным, то полученный результат используется, иначе — выкидывается.
              +2
              Вы, наверное удивитесь, но < тоже условный оператор. Проверяет, истинно ли условие «левый операнд меньше правого». Так что незачет.
              Правильно делать так:
              var a = get();
              var b = get();
              var avg = (a + b) / 2.0;
              var diff = Math.Abs(a-b);
              var max = avg + dff / 2.0;
              var min = avg - diff / 2.0; 
              

              Вот в таком виде реально нету операторов сравнения.
                0
                Я и не спорю что я сжульничал с циклом ибо «дефакто» он выполняется как условие но он не является условным оператором. «Деюре» "<" -является «оператором сравнения». (как говорит гугл ). Тем не менее это гораздо упрощает задачу, не противоречит условию
                  +1
                  Тем не менее это гораздо упрощает задачу, не противоречит условию

                  Противоречит его духу.

                  Вам показать, как любая comparison-based сортировка переписывается с if на ваш for?
                +2
                Я так понимаю, произошло внезапное изобретение велосипеда под названием сортировка подсчетом.
                  0
                  Я и не говорю что придумал метод сортировки. Я даже указываю что такой метод существует но я не помню его названия.
                    0
                    Нет, тут велосипед более дикого типа. Было установлено на практике что гвозди можно забивать мясорубкой.
                    +1
                    Вот вам честная сортировка без условий, не ограниченная размером int'а.
                    Даже в байткоде ни одного условного оператора.

                    import java.util.Arrays;
                    import java.util.concurrent.ThreadLocalRandom;
                    import java.util.function.IntSupplier;
                    
                    public class Unconditional {
                    
                        static int ifLess(long a, long b, IntSupplier trueBranch, IntSupplier falseBranch) {
                            int cond = (int) ((a - b) >>> 63);
                            return new IntSupplier[]{falseBranch, trueBranch}[cond].getAsInt();
                        }
                    
                        static int inc(long[] array, int i, long pivot) {
                            return ifLess(array[i], pivot, () -> inc(array, i + 1, pivot), () -> i);
                        }
                    
                        static int dec(long[] array, int j, long pivot) {
                            return ifLess(pivot, array[j], () -> dec(array, j - 1, pivot), () -> j);
                        }
                    
                        static void swap(long[] array, int i, int j) {
                            long tmp = array[i];
                            array[i] = array[j];
                            array[j] = tmp;
                        }
                    
                        static int partition(long[] array, int lo, int hi, long pivot) {
                            int i = inc(array, lo, pivot);
                            int j = dec(array, hi, pivot);
                            return ifLess(i, j, () -> {
                                swap(array, i, j);
                                return partition(array, i + 1, j - 1, pivot);
                            }, () -> j);
                        }
                    
                        static int qsort(long[] array, int lo, int hi) {
                            return ifLess(lo, hi, () -> {
                                int p = partition(array, lo, hi, array[lo + (hi - lo) / 2]);
                                return qsort(array, lo, p) | qsort(array, p + 1, hi);
                            }, () -> 0);
                        }
                    
                        public static void main(String[] args) {
                            long[] array = ThreadLocalRandom.current().longs(100, 0, 1000).toArray();
                            qsort(array, 0, array.length - 1);
                            System.out.println(Arrays.toString(array));
                        }
                    }
                    

                    Only users with full accounts can post comments. Log in, please.