Рубрика «пузырьковая сортировка»

Забавной находкой поделился сегодня пользователь fj333 с Reddit. Разбираясь в появившемся год назад проприетарном коде Qualcomm Technologies для Android, он обнаружил, что неизвестный программист решил в production-коде использовать сортировку пузырьком для того, чтобы найти… максимум в массиве.

Посмотреть исходный файл вы сможете по ссылке на Github или же под катом, а оценить его в работе может любой владелец устройства с Qualcomm Snapdragon 200 MSM8610 под управлением Android.

Как известно любому, кто знаком с алгоритмами сортировки, сортировка пузырьком — алгоритм учебный, и в промышленном коде не применяющийся в силу своей неэффективности; дело в том, что в наихудшем и среднем случаях он имеет сложность О(n2), к тому же его емкостная сложность в данном случае — O(n). Кого это не убедило — использовать сортировку пузырьком не рекомендует даже Барак Обама.

И это всё не учитывая того, что для поиска максимума хватило бы и простого перебора.
Читать полностью »

Глупая сортировка и некоторые другие, поумнее
В прошлой статье мы оттолкнулись от так называемой глупой сортировки и путём нехитрых метаморфоз получили всем известную пузырьковую сортировку. Трансформируя последнюю пришли к целому вороху обменных способов упорядочивания массивов. Один из которых, между прочим, на структурах до нескольких тысяч элементов, даже работает быстрее чем быстрая сортировка.

Сегодня мы снова возьмём за основу stupid sort и внесём в неё другое маленькое, но существенное изменение. В результате получим совершенного другой эволюционный ряд сортировочных алгоритмов.

image: эволюция

Читать полностью »

Имеем обычный «пузырек»:

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: Избавиться от временной переменной. Делается это вот таким макаром:Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js