Можете объяснить мне в чем суть алгоритма сортировки пузырьком?
ПрограммированиеData science+2
Анонимный вопросData Science
· 9,3 K
Суть сортировки — упорядочивание последовательности неких сравнимых друг с другом элементов. Сортировка пузырьком (т.н. bubble sort) — это алгоритм сортировки, интуитивно понятный для большинства людей.
Например, нам надо упорядочить книги на полке по алфавиту. Как мы это делаем? Ищем книгу на "А", ставим в начало полки. Потом в оставшемся ряду ищем книгу на "Б", ставим рядом с первой. Среди оставшихся ищем "В" и так далее, повторяем до тех пор, пока не дойдём до конца полки.
Каждый раз происходит одно и то же — "наименьшая" книга перемещается влево из общей массы остальных книг, как бы "всплывает" из них. По сути это и есть пузырьковая сортировка. Сам алгоритм детально описан в Википедии.
Кстати, другое название сортировки пузырьком — "sinking sort", то есть "сортировка утоплением". Звучит не очень оптимистично, поэтому в русскоязычных книгах не прижилось.
Чтобы окончательно понять, что это такое, попробуйте решить следующую задачку. У вас есть ряд разных по весу, но одинаковых на вид гирек. Вес нигде не написан, но на руках у вас есть весы, позволяющие сравнить вес двух соседних гирек. Какие действия нужно совершить, чтобы гарантированно расставить гирьки в порядке возрастания их веса?
3 эксперта согласныи1 эксперт не согласен
Андрей Бахматов
24 марта 2022возражает
Принцип описанного алгоритма не имеет ничего общего с сортировкой "пузырьком"
Марк Сафронов
28 января 2022подтверждает
Отличный ответ, всё так и есть.
Ваш алгоритм работать будет криво и нерационально. Во-первых, вы должны будете задать все элементы множества явно, иначе при отсутствии книги на А ваша программа зависнет. Во-вторых, поиск по всему списку займет уйму времени. Теперь понятно, почему программы на джава такие глючные :)
@Timur Sapolnov, что во фразе "наименьшая книга перемещается влево" вам непонятно?
Специалист в области управления и информатики в технических системах.
Data Engeneer, IT... · 27 янв 2022
В том, что числа в правильном порядке продвигаются по списку чисел подобно пузырьку воздуха в воде. В конце его работы вы получаете отсортированный в нужном порядке список.
6 экспертов согласны
Марк Сафронов
28 января 2022подтверждает
Не думаю, что можно что-то ещё добавить. Оригинальное название этого метода сортировки Bubble sort, что не... Читать дальше
Сортируем список а,в,с...n по возрастанию:
Сравниваем два соседних элемента а,в, если а>в, меняем их местами, если нет - ничего не делаем. Смещаемся вправо на 1 элемент, повторяем процедуру. По окончании списка повторяем цикл сначала, пока список не будет пройден без замен.
5 экспертов согласны
Марк Сафронов
31 января 2022подтверждает
Описание алгоритма слово в слово, как оно есть. Не к чему да и незачем придраться.
Ответы на похожие вопросы
Можете объяснить мне в чем суть алгоритма сортировки пузырьком? — 1 ответ, задан
Первый
Давайте проведем визуализацию: наш массив значений представим в виде пузырьков воздуха в воде, объём пузырька в прямой зависимости от значения элемента массива, и расположим все элементы по порядку вертикально.
Логично, что большой пузырь всплывёт наверх быстрее маленького. Основываясь на этом, делаем цикл сравнений двух соседних элементов, начиная с верхнего : если внизу пузырь больше, то они меняются местами - большой всплывает наверх.
После первого цикла сравнений самый маленький пузырь оказывается внизу, и этот последний элемент уже можно исключить из следующих циклов. Даже если самый большой пузырь был внизу, после окончания сортировки он "всплывёт " на первую позицию массива.
Логично, что большой пузырь всплывёт наверх быстрее маленького. Основываясь на этом, делаем цикл сравнений двух соседних элементов, начиная с верхнего : если внизу пузырь больше, то они меняются местами - большой всплывает наверх.
После первого цикла сравнений самый маленький пузырь оказывается внизу, и этот последний элемент уже можно исключить из следующих циклов. Даже если самый большой пузырь был внизу, после окончания сортировки он "всплывёт " на первую позицию массива.
1 эксперт согласен