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

[lair]

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

[Prosto_Bro]

Я могу ошибаться но o(N) что описано выше. Да по памяти сожрет много, но это зависит от диапазона значений и даже если будет большой диапазон то это не повлияет на сортировку а только затруднит вывод, но вывод не является ключевым здесь. Так что…

[lair]

Вы ошибаетесь. По памяти — О(m), где m — максимальное значение в массиве. Так что слово «много» не описывает.

[Prosto_Bro]

Нет, сортировке не важно максимальное значение, играет роль только количество элементов

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

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

[lair]

Ох.

Каков размер sortArray?

[Prosto_Bro]

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

[lair]

Максм*2

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

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

[Prosto_Bro]

Простите, я очень не внимательный человек. Да по памяти будет o(m)… я подумаю над тем как оптимизировать, собственно это будет как другой метод сортировки.

[lair]

… и в итоге вы вернетесь к тому, что уже обсуждено в комментариях к исходной статье.

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

[Sing]

> Я могу ошибаться но o(N) что описано выше.

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

Всё дело в функции вывода, без которого такая сортировка бессмысленна.

[lair]

Ну и да, использование цикла с мгновенных выходом «вместо» сравнения — это жульничество.

[Prosto_Bro]

Простите что? Выход из цикла это жульничество? В любом языке можно реализовать такой выход. Так что, шансы равны.

[lair]

Ваш цикл с выходом — это то же самое сравнение, поэтому вы нарушили условие «без сравнений».

[Prosto_Bro]

Это не условный оператор, он содержит условие.В оригинальной статье циклы использовались, да и в любом цикле присутствует условие.

[lair]

В оригинальной статье циклы использовались,

В оригинальной статье циклы использовались только для обходов массива, и это допущение, на которое все были согласны. А в комментариях есть решение, которое и для этого не использует циклы.

[Prosto_Bro]

P.S Даже на паскале есть кривой но все-же break

[Maccimo]

Обычный break, не кривее других.

[Zibx]

После компиляции условие в цикле ничем не отличается от if.

[Prosto_Bro]

В этом и суть. Я же не использовал в своем коде условных операторов, то что это упроститься компилятором до условия меня не волнует.

[Zibx]

Ниже верно заметили что > — условный оператор. Когда речь заходит о переписывании алгоритма без условных операторов — на самом деле разговор идёт об оптимизации. Об очень специфичной оптимизации, которая имеет смысл только в настоящих числодробилках, а именно — исключение возможности неправильного угадывания процессором ветки алгоритма исполняемой далее.
В современных процессорах есть множество простаивающих блоков. В целях оптимизации на некоторых из них происходит дальнейшее выполнение программы ещё в тот момент когда исполняется проверка условия. Если предсказание ветки было верным, то полученный результат используется, иначе — выкидывается.

[MaximChistov]

Вы, наверное удивитесь, но < тоже условный оператор. Проверяет, истинно ли условие «левый операнд меньше правого». Так что незачет.
Правильно делать так:

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; 

Вот в таком виде реально нету операторов сравнения.

[Prosto_Bro]

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

[lair]

Тем не менее это гораздо упрощает задачу, не противоречит условию

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

Вам показать, как любая comparison-based сортировка переписывается с if на ваш for?

[Spetros]

Я так понимаю, произошло внезапное изобретение велосипеда под названием сортировка подсчетом.

[Prosto_Bro]

Я и не говорю что придумал метод сортировки. Я даже указываю что такой метод существует но я не помню его названия.

[Zibx]

Нет, тут велосипед более дикого типа. Было установлено на практике что гвозди можно забивать мясорубкой.

[apangin]

Вот вам честная сортировка без условий, не ограниченная размером 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));
    }
}