Изображение обложки от: Unsplash – Кай Дамс
вступление
Это будет серия о различных алгоритмах сортировки, некоторых объяснениях и быстрой демонстрации с решением в JavaScript.
Пузырьковые сортировки
Прежде всего, давайте начнем с самой основной – пузырьковой сортировки. Логика, стоящая за сортировкой пузырьков, следующая:
- Начиная с самого начала, сравните два соседних элемента
- Если предыдущий больше, чем следующий, поменяйте эти два
- Повторите, пока в массиве не останется элемента
Это только одна итерация, которая гарантирует, что самый большой элемент находится в конце массива.
- Повторите этот процесс для каждого элемента в массиве
Сложность
Как вы можете увидеть, существует несколько различных результатов, и, основываясь на количестве элементов для сравнения, все может быстро выйти из -под контроля.
Лучший сценарий : Элементы заказаны> мы будем делать O (n) сравнения.
Худший сценарий : Элементы заказаны обратно> мы будем делать O (n 2 ) сравнение. Это не похоже на проблему для 10 элементов, но для 1000 после этого будет много нуля.:)
Средний сценарий : К сожалению, средний сценарий имеет такую же сложность, что и худший, который все еще будет O (n 2 ) .
Применение
Я думаю, что пузырьковая сортировка не так проблематична из -за его простоты для понимания. Используйте его с умом и используйте его для небольшого количества элементов. В этом нет ничего плохого – до минимального количества элементов.
Реализация
Конечно, есть много способов реализовать это, но я оставлю свой здесь для всех, кто заинтересован. Я также свяжу репо Github для этого.
function bubbleSort(_array) {
const array = _array;
for (let i = 0; i < array.length - 1; i++)
for (let j = 0; j < array.length - i; j++)
if (array[j] > array[j + 1]) [array[j], array[j + 1]] = [array[j + 1], array[j]];
return array;
}
Какой -то пик проникновения:
- Самый простой способ поменять две переменные – [a, b] = [b, a]> вам не нужен
TMPодин тогда - Вам не нужно зацикливаться на массиве до конца каждую итерацию>, если величайшая уже в конце (и N -nth Greate … так далее) оставьте это в покое
Ссылка
Репо
Оригинал: “https://dev.to/vazsonyidl/bubble-sort-4g51”