Prosto_Bro November 3, 2015 at 13:49

Sort an array without using conditional statements

From the sandbox

I immediately warn that this article will be an alternative version of this one . Yes, I really can tell you how to rush to criticize me all at once, but guys, the presentation algorithm in the solution is not optimal. The comments suggested even simpler algorithms, in python. On python it is enough to write:

array.sort()

And that’s all. Who needs any algorithm at all. In the task, a restriction from 0 to 100 was established, but we are not lazy, we will do it in general form, for any values and with repetition of numbers. After a little thought, I came to this decision:

The code

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 + " ");
			}
		}
	}
}

And now, let's look at what I wrote here.

In general, the problem is to find the minimum and maximum, since we cannot use the comparison, then:

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

If B modulo be greater than A, then the cycle simply will not be executed and will go back. This is a fairly simple solution. Without the "great" mathematical formulas. Simple and clear. And one more thing: why do I take modulo? This is caused by the sorting method that I use.

In the original article, the “with flag” sorting is used (if I understood correctly). Performing such sorting in the worst case O (N ^ 2) (or close to it), which is not good.

This method (I don’t remember its name, it’s ~~not~~ laziness to look for a ~~royal thing~~ ) will decide for O (N) even though the numbers will be repeated.

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

The essence of sorting is that when filling the array, it sorts itself. We represent the value as an index and increase the number of elements in this index.

Example

We met the number 44 twice, which means that the sorted array at index 44 will contain 2. It's easy!

As it turned out (either I’m curved), arrays are created from 0 to N, and as I did not try to do from -N to N, to no avail. Therefore, we do the offset, therefore, we are looking for a maximum with the module. Then we simply reflect relative to 0 and get the range of indices into which all elements except the boundary will fit exactly, so +1.

Explanation

We get a minimum of -48, and a maximum of 38. So we take that a minimum of -48, and a maximum of 48, to simplify the algorithm. And we shift so that the minimum is at 0 -48 + 48

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

That’s all for me. Completed the task, while optimizing the process and presenting his vision of solving this problem.

Output example

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

Tags:

Sort an array without using conditional statements

Also popular now: