How to sort an array without using comparisons?

Question

You can use another array. I know how to implement bubble sorting:

public static void main(String[] args) { Scanner s = new Scanner(System.in); System.out.println("введите количество элементов"); int num = s.nextInt(); int a[] = new int[num]; System.out.println("введите элементы"); for (int i = 0; i < num; i++) { a[i] = s.nextInt(); } int c; for (int x = 0; x < num - 1; x++) { for (int i = 0; i < num - 1 - x; i++) { if (a[i] > a[i + 1]) { c = a[i];//c=a a[i] = a[i + 1];//a=b a[i + 1] = c;//b=c } } } for (int i = 0; i < num; i++) { System.out.print(a[i] + " "); } }

But how to sort an array without using comparisons?

The essence of the problem is that you yourself guess how to avoid comparisons.
Something I do not realize why this question should be minus.
If the author does not know the algorithm, then in my opinion, it’s not so easy to guess.
You can, for example, organize a sieve with brute force bitmask 1000, 0100, 0010, 0001
The truth was supposed to be sorted by the calculation and not one by one, but these are already nuances.
@pavel, by the way, I don’t remember that the university is aware of combinatorial algorithms that pass these algorithms.
I did not write the sorting by counting, because there I would have to calculate the mines.
elements, but I don’t know how to calculate them without using a comparison.

Accepted Answer · 2017-02-22T17:50:41

There is bitwise sorting ( radix sort ), which is used for non-negative numbers. Her idea is to sort the numbers gradually, by digits, using baskets (buckets) for each digit (from 0 to 9 ).

We iterate over all the positions of the digits in the number (there are 10 pieces in the Integer ).
For each position we go through all the numbers in the array and add the digit of the number corresponding to this position to the basket corresponding to this digit.
After going through all the numbers, we "collect" the array back from the numbers stored in the baskets, in the order in which they are in the baskets.

Implementation:

 private static final int RADIX = 10; public static void sort(int[] array) { List<Integer>[] buckets = new ArrayList[RADIX]; for (int i = 0; i < buckets.length; i++) { buckets[i] = new ArrayList<>(); } for (int placement = 1; placement <= 1000 * 1000 * 1000; placement *= RADIX) { for (int value : array) { int digit = (value / placement) % RADIX; buckets[digit].add(value); } int index = 0; for (List<Integer> bucket : buckets) { for (int value : bucket) { array[index++] = value; } bucket.clear(); } } }

In this case, an array of lists ( buckets ) is used as an additional structure. As part of the code optimization, you can use only those positions that are really in the sorted numbers, but this assumes the presence of a comparison, so I did not add it to the code.

There is an implementation in which as an add. structures are simply used as an array of integers ( count ):

 private static final int RADIX = 10; public static int[] sort(int[] array) { for (int placement = 1; placement <= 1000 * 1000 * 1000; placement *= RADIX) { array = sortPlace(array, placement); } return array; } private static int[] sortPlace(int[] array, int placement) { int[] result = new int[array.length]; int[] count = new int[RADIX]; for (int value : array) { int digit = getDigit(value, placement); count[digit]++; } for (int i = 1; i < count.length; i++) { count[i] += count[i - 1]; } for (int i = array.length - 1; i >= 0; i--) { int digit = getDigit(array[i], placement); count[digit]--; result[count[digit]] = array[i]; } return result; } private static int getDigit(int value, int placement) { return ((value / placement) % RADIX); }

The original code can be viewed here .

Answer 2 · 2017-02-22T18:10:50

But how to sort an array without using comparisons?

In this formulation of the problem, you can not change the code much at all.

Consider a fragment

 if (a[i] > a[i + 1]) { c = a[i]; a[i] = a[i + 1]; a[i + 1] = c; }

After its execution, a[i] <= a[i+1] , if necessary, they are swapped. The same can be done

  c = a[i] + ((a[i+1] - a[i]) & ((a[i+1] - a[i]) >> 31)); a[i+1] = a[i+1] + a[i] - c; a[i] = c;

As you can see if there is no.

I think that not only will I have problems with understanding how it works.
Ordinary bit operations) I do not even know what to describe.

How to sort an array without using comparisons?

2 answers 2

More articles: