Ни разу не писал пузырьковую сортировку. Несколько странная сущность. Вроде бы известна вельми. И в то же время бесполезна чуть более чем полностью, ибо эффективность небольшая. Я не знал о ней, и не могу сказать, что мне чего-то не хватало. И все же (говорят) на собеседованиях порой просят ее написать. Непонятно, правда, зачем.
Штош, я тоже написал. Сначала через два цикла 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));
Да, функцию для генерации массива со случайными числами (включая отрицательные) я тоже написал.