My Little Blog Да, это блог

 
Пузырьковая сортировка

Ни разу не писал пузырьковую сортировку. Несколько странная сущность. Вроде бы известна вельми. И в то же время бесполезна чуть более чем полностью, ибо эффективность небольшая. Я не знал о ней, и не могу сказать, что мне чего-то не хватало. И все же (говорят) на собеседованиях порой просят ее написать. Непонятно, правда, зачем.


Штош, я тоже написал. Сначала через два цикла for. Потом решил, что пойдет и комбинация while + for. Затем все же сделал через do + for, ибо один-то раз придется пройтись точно. Конечно, мысль о том, что не следует мучить массив столько раз, сколько в нем элементов, пришла сразу. Смотреть в логическое значение или счетчик? Счетчик нагляднее и дает больше контроля, но логическое логичнее. Внедрил и то, и другое. Разумеется, перебирать все элементы массива тоже не обязательно. При первом проходе достаточно количество проходов на единицу меньшее, чем количество элементов. При следующем переборе также следует уменьшить количество перебираемых элементов на один - ведь самое жирное складывается в конец. Так можно делать до конца работы сортировки. Под конец заделал версию с использованием метода map.


Замерил время выполнения всех вариантов. В map всегда перебираются все элементы, потому я не удивился тому факту, что в данном случае этот новомодный метод сосет у старого доброго for. Два for оказались самыми шустрыми. Впрочем, с do или while скорость почти такая же.


JavaScript:


function get_random_array(size = 40, min = -0, max = 666) {
	return Array.from({length: size}, () => Math.floor(Math.random() * (max - min + 1)) + min);
} // конец get_random_array


function bubbles(array) {

console.time("bubbles");

console.log(`Длина массива: ${array.length}, исходный вид массива: ${array}`);

let length_i = array.length - 1;
let length_j = array.length - 1;
let counter;
let swap;

for (let i = 0; i < length_i; i++) {
	swap = false;
	counter = 0;
	for (let j = 0; j < length_j; j++) {
		if (array[j] > array[j + 1]) {
			[array[j], array[j + 1]] = [array[j + 1], array[j]];
			swap = true;
			counter++;
		}
	}
	length_j--;
	console.log(`В итерации ${i} сделано замен ${counter}; вид массива: ${array}`);
	if (!swap) {
		console.log(`Сортировка окончена на итерации ${i}, отсортированный массив: ${array}`);
		break;
	}
}

console.timeEnd("bubbles");

} // конец bubbles


bubbles(get_random_array(33, -94, 77));


Да, функцию для генерации массива со случайными числами (включая отрицательные) я тоже написал.