Ответ
Временная сложность пузырьковой сортировки — O(n²) в худшем и среднем случае, и O(n) в лучшем случае (если массив уже отсортирован).
Почему O(n²):
- В худшем случае для каждого из
nэлементов делаетсяnсравнений - Даже с оптимизацией (флагом
swapped) сложность остаётся квадратичной
Пример кода:
function bubbleSort(arr) {
let swapped;
do {
swapped = false;
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
swapped = true;
}
}
} while (swapped);
return arr;
}Ответ 18+ 🔞
Так, слушай, про эту вашу пузырьковую сортировку. Ну, классика жанра, блядь, как борщ со сметаной. Сложность у неё — O(n²), и это, на минуточку, в самом поганом раскладе и в среднем тоже. А в лучшем, если массив уже красивый, отсортированный, то O(n), но это как выиграть в лотерею, ёпта — бывает, но не надейся.
А почему, блядь, квадрат? Да потому что она тупая, как пробка! Представь: для каждого из n элементов она тупо пробегает по всему массиву и сравнивает. Это как если бы ты в тёмной комнате искал ключи, перебирая каждый раз все углы, даже те, где уже искал. Ну, овердохуища операций, короче.
Даже если воткнуть флаг swapped (типа "а менял ли я что-то?"), чтобы не долбиться в уже отсортированное, всё равно в среднем выходит эта самая квадратичная хуйня. Не отмажешься.
Вот, смотри, как она выглядит в коде, этот древний артефакт:
function bubbleSort(arr) {
let swapped;
do {
swapped = false;
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
swapped = true;
}
}
} while (swapped);
return arr;
}Смотрит на два соседних элемента, и если левый больше правого — бац, меняет их местами, как двух пьяных мужиков в очереди. И так по кругу, пока все не встанут по росту. Эффективность — хуй с горы, но для обучения сойдёт, чтобы понять, как не надо делать, если данных больше десяти.