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) (или близко к этому), что не есть хорошо.
Этот метод (не помню его название, искать
for (i = 0; i < NUM_ELEMENT; i++) {
sortArray[arrayForSort[i] + maxNum]++;
}
Суть сортировки заключается в том что при заполнении массива он сам сортирует себя. Значение мы представляем в виде индекса и увеличиваем количество элементов в этом индексе.
Как оказалось (то ли я криворукий), массивы создаются от 0 до N и как я не старался сделать от -N до N, безуспешно. Поэтому делаем смещение, поэтому ищем максимум с модулем. Потом просто отражаем относительно 0 и получаем диапазон индексов в который точно влезут все элементы, кроме граничного, так что +1.
sortArray = new int[maxNum * 2 + 1];
. . .
sortArray[arrayForSort[i] + maxNum]++;
. . .
System.out.print(i - maxNum + " ");
На этом у меня все. Поставленную задачу выполнил, при этом оптимизировав процесс и представив свое видение решения данной задачи.
-44 -36 -35 -30 -29 -28 -22 -10 2 2 17 17 24 26 31 35 35 39 41 50
Комментарии (27)
lair
03.11.2015 14:20+8Ну и да, использование цикла с мгновенных выходом «вместо» сравнения — это жульничество.
Prosto_Bro
03.11.2015 16:41-2Простите что? Выход из цикла это жульничество? В любом языке можно реализовать такой выход. Так что, шансы равны.
lair
03.11.2015 16:47+3Ваш цикл с выходом — это то же самое сравнение, поэтому вы нарушили условие «без сравнений».
Prosto_Bro
03.11.2015 16:52-1Это не условный оператор, он содержит условие.В оригинальной статье циклы использовались, да и в любом цикле присутствует условие.
lair
03.11.2015 16:53В оригинальной статье циклы использовались,
В оригинальной статье циклы использовались только для обходов массива, и это допущение, на которое все были согласны. А в комментариях есть решение, которое и для этого не использует циклы.
Zibx
03.11.2015 15:03+4После компиляции условие в цикле ничем не отличается от if.
Prosto_Bro
03.11.2015 16:44-3В этом и суть. Я же не использовал в своем коде условных операторов, то что это упроститься компилятором до условия меня не волнует.
Zibx
04.11.2015 04:52Ниже верно заметили что > — условный оператор. Когда речь заходит о переписывании алгоритма без условных операторов — на самом деле разговор идёт об оптимизации. Об очень специфичной оптимизации, которая имеет смысл только в настоящих числодробилках, а именно — исключение возможности неправильного угадывания процессором ветки алгоритма исполняемой далее.
В современных процессорах есть множество простаивающих блоков. В целях оптимизации на некоторых из них происходит дальнейшее выполнение программы ещё в тот момент когда исполняется проверка условия. Если предсказание ветки было верным, то полученный результат используется, иначе — выкидывается.
MaximChistov
03.11.2015 17:39+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;
Вот в таком виде реально нету операторов сравнения.Prosto_Bro
03.11.2015 18:08Я и не спорю что я сжульничал с циклом ибо «дефакто» он выполняется как условие но он не является условным оператором. «Деюре» "<" -является «оператором сравнения». (как говорит гугл ). Тем не менее это гораздо упрощает задачу, не противоречит условию
lair
03.11.2015 18:23+1Тем не менее это гораздо упрощает задачу, не противоречит условию
Противоречит его духу.
Вам показать, как любая comparison-based сортировка переписывается с if на ваш for?
Spetros
03.11.2015 19:02+2Я так понимаю, произошло внезапное изобретение велосипеда под названием сортировка подсчетом.
Prosto_Bro
03.11.2015 22:49Я и не говорю что придумал метод сортировки. Я даже указываю что такой метод существует но я не помню его названия.
Zibx
04.11.2015 04:46Нет, тут велосипед более дикого типа. Было установлено на практике что гвозди можно забивать мясорубкой.
apangin
04.11.2015 18:36+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)); } }
lair
Угу. Так какая алгоритмическая сложность у вашего алгоритма? И какие требования по памяти?
Prosto_Bro
Я могу ошибаться но o(N) что описано выше. Да по памяти сожрет много, но это зависит от диапазона значений и даже если будет большой диапазон то это не повлияет на сортировку а только затруднит вывод, но вывод не является ключевым здесь. Так что…
lair
Вы ошибаетесь. По памяти —
О(m), гдеm— максимальное значение в массиве. Так что слово «много» не описывает.Prosto_Bro
Нет, сортировке не важно максимальное значение, играет роль только количество элементов
NUM_ELEMENT=20…
Вот весь метод сортировки.
Максимальное повлияет только в выводе, так как нам нужно пройтись по всей длине массива, но это не входит в задачу.
lair
Ох.
Каков размер
sortArray?Prosto_Bro
Максм*2 но мы обращаемся к нему только NUM_ELEMENT=20… раз
lair
Вот поэтому и получается O(m) по памяти.
(а вы думаете, зря в качестве доминирующих алгоритмов сортировки используются comparison-based, у которых алгоритмическая стоимость в log(N) раз больше вашей?)
Prosto_Bro
Простите, я очень не внимательный человек. Да по памяти будет o(m)… я подумаю над тем как оптимизировать, собственно это будет как другой метод сортировки.
lair
… и в итоге вы вернетесь к тому, что уже обсуждено в комментариях к исходной статье.
Собственно, ваш вариант решения там тоже есть (только с ограничением на «только положительные», но это не имеет фундаментального значения)
Sing
> Я могу ошибаться но o(N) что описано выше.
Если не ошибаюсь, то O(m^2), где m — максимальное число массива. Интересно, что от N он вообще не зависит, по сути.
Всё дело в функции вывода, без которого такая сортировка бессмысленна.