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

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

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]++; } 

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

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

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

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

ссылка на оригинал статьи http://habrahabr.ru/post/270071/