Оглавление:
Определение - Что означает Bubble Sort?
Пузырьковая сортировка - это алгоритм сортировки, который работает, многократно просматривая списки, которые необходимо отсортировать, сравнивая каждую пару смежных элементов и меняя их местами, если они находятся в неправильном порядке. Эта процедура прохождения повторяется до тех пор, пока не требуется никаких перестановок, указывая на то, что список отсортирован. Пузырьковая сортировка получила свое название, потому что меньшие элементы всплывают в верхней части списка.
Пузырьковая сортировка также называется тонущей сортировкой или сравнительной сортировкой.
Техопедия объясняет Bubble Sort
Пузырьковая сортировка имеет наихудший случай и средняя сложность O (n2), где n - количество отсортированных элементов. В отличие от других алгоритмов сортировки, пузырьковая сортировка определяет, является ли отсортированный список эффективно встроенным в алгоритм. Производительность пузырьковой сортировки по уже отсортированному списку равна O (n).
Положение элементов в пузырьковой сортировке играет важную роль в определении производительности. Большие элементы в начале не представляют проблемы, так как их легко заменить. Мелкие элементы к концу движутся к началу медленно. Как таковые, эти элементы называются кроликами и черепахами.
Алгоритм сортировки пузырьков можно оптимизировать, поместив более крупные элементы в конечную позицию. После каждого прохода все элементы после последнего обмена сортируются и не требуют повторной проверки, тем самым пропуская отслеживание замененных переменных.
