Pull to refresh

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

Reading time1 min
Views2.4K
Имеем обычный «пузырек»:
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, идем на следующую итерацию
			);


Исходник
Tags:
Hubs:
If this publication inspired you and you want to support the author, do not hesitate to click on the button
Total votes 61: ↑27 and ↓34-7
Comments60

Articles