Abnormal programming
25 May 2012

Сортировка в одну строку

Имеем обычный «пузырек»:
for(int i = 0; i < n - 1; i++ )
	  for(int j = i + 1; j < n; j++)
	   if(ar[i] > ar[j])
	   {
		 int temp = ar[i];
		 ar[i] = ar[j];
		 ar[j] = temp; 
	   }


Задача №1: Избавиться от временной переменной. Делается это вот таким макаром:

ar[i] ^= ar[j] ^= ar[i] ^= ar[j];


Задача №2: Избавиться от if.
Делается еще проще:
(ar[i] > ar[j]) ? ar[i] ^= ar[j] ^= ar[i] ^= ar[j] : 0;


Задача №3: Основная. Избавиться от внутреннего цикла for по j.
Для этого следует: 1) Итерировать от j до n, при этом в условии всегда возвращать true 2) Проверять условие конца алгоритма, только когда вся итерация по j прошла
3) При проверке условия, делать j = i + 1, i = i + 1.
Результат таков:
for(int i = 0, j = 0;		
		j < n ? 1 : i < n - 1;	
		  j = j < n ?	
		   ((ar[i] > ar[j] ? ar[i] ^= ar[j] ^= ar[i] ^= ar[j] : 0),		
	        ( j + 1 ))		  
		     : ++i	// иначе j=n, идем на следующую итерацию
			);


Исходник

-7
1.8k 34
Comments 60