Привет, в этом блоге мы рассмотрим теоретические основы, а также практическую реализацию алгоритма пузырьковой сортировки. Прочтите до конца, потому что в середине * сообщения вы найдете что-то интересное. Я дам полное подробное объяснение алгоритма пузырьковой сортировки вместе с реализацией кодирования на python. Я обещаю, что вы получите то, что хотите. Итак, без промедления, давайте сразу же приступим к делу и приступим.
Оглавление
- Что это за пузырьковая сортировка?
- Приложения
- Алгоритм
- Объяснение*
- Реализация кодирования
Что это за пузырьковая сортировка?
- В алгоритме пузырьковой сортировки мы будем многократно проходить по списку для сортировки, сравнивать каждую пару соседних элементов и менять их местами, если они расположены в неправильном порядке.
- Наихудшая и средняя сложность алгоритма пузырьковой сортировки составляет O (N²). Таким образом, пузырьковая сортировка - это типичный алгоритм квадратичного времени выполнения, и мы также можем добиться большего с другими алгоритмами сортировки.
- Мы можем достичь временной сложности O (N log N) с помощью других алгоритмов, основанных на сравнении, и даже O (N) с помощью алгоритмов сортировки, не основанных на сравнении. Вот почему мы вообще не используем пузырьковую сортировку.
- Это слишком медленно и непрактично для большинства задач реального времени даже по сравнению с сортировкой вставкой.
- Пузырьковая сортировка - еще один практический алгоритм сортировки. Он не будет эффективен в случае коллекции с обратным порядком, но, с другой стороны, это стабильный алгоритм сортировки, и он присутствует, что означает, что ему не нужна дополнительная память.
Круто… Давайте посмотрим на применение этого алгоритма.
Приложения
- Мы уже говорили о том, что пузырьковая сортировка не является эффективным алгоритмом, но в компьютерной графике она популярна благодаря своей способности обнаруживать очень маленькие ошибки (например, замена всего двух элементов) в почти отсортированном массиве. и исправит это с линейной сложностью O (N).
- Он также используется в алгоритме заполнения многоугольника, где ограничивающие линии сортируются по их координатам x в определенной строке сканирования (линия, параллельная оси x) и с при увеличении y их порядок меняется (два элемента меняются местами) только на пересечении двух линий.
Как видите, это непрактичный алгоритм, но у него также есть конкретное приложение, в котором он может работать лучше, чем другие.
Например, если у нас есть одномерный массив [7, 2, 5, 9, 3]. Нам нужно перебрать все элементы в массиве, и да, мы должны все рассмотреть. И на каждой итерации мы продолжаем рассматривать все меньше и меньше элементов, потому что на каждой итерации мы считаем, что еще один элемент будет отсортирован.
И при необходимости мы поменяем местами два элемента, потому что массив с индексом j больше, чем массив с индексом j + 1. Это означает, что он не в порядке возрастания, поэтому мы должны поменять местами два элемента.
Алгоритм
Алгоритм пузырьковой сортировки очень прост.
ШАГ 1: итерации i от 0 до len (массив) -2.
ШАГ 2. Для каждой итерации i выполните итерацию j от 0 до len (array) -i-2.
ШАГ 3: для каждой итерации j проверьте, не выполняется ли array [j] ‹array [j + 1], если это не так, поменяйте местами значения в позиции индекса j. и j + 1.
Объяснение
Прохладный. Давайте начнем с начала массива и продолжаем сравнивать два соседних элемента.
Если длина массива равна N, то мы должны сделать N-1 итераций.
В нашем массиве 5 элементов, поэтому нам нужно сделать 4 итерации.
Посмотрим, что происходит с каждой итерацией.
Первая итерация
Первоначально массив будет [7, 2, 5, 9, 3]. Значения j будут 0 ‹= j‹ = 3.
- Когда j = 0, первая смежная пара - это 7 и 2. Здесь 7 больше 2 и находится в неправильном порядке. Поэтому мы должны их поменять местами. Тогда массив станет [2, 7, 5, 9, 3].
- Увеличивая j, теперь j = 1. Таким образом, соседняя пара равна 7 и 5. Здесь 7 больше 5 и находится в неправильном порядке. Поэтому мы должны их поменять местами. Тогда массив станет [2, 5, 7, 9, 3].
- Увеличивая j, теперь j = 2. Таким образом, соседняя пара - это 7 и 9. Здесь 7 меньше 9 и находится в правильном порядке. Так что не нужно их менять местами. Тогда массив будет [2, 5, 7, 9, 3].
- Увеличивая j, теперь j = 3. Таким образом, соседняя пара - это 9 и 3. Здесь 9 больше 3 и находится в неправильном порядке. Поэтому мы должны их поменять местами. Тогда массив станет [2, 5, 7, 3, 9].
Смотрите, что самый большой элемент массива, который равен 9, идет в последнюю позицию массива. Таким образом, наша первая итерация завершена.
Вторая итерация
Перед входом во вторую итерацию массив будет [2, 5, 7, 3, 9]. Значения j будут 0 ‹= j‹ = 2.
- Теперь j = 0. Таким образом, соседняя пара - это 2 и 5. Здесь 2 меньше 5, и это в правильном порядке. Так что не нужно их менять местами. Тогда массив будет [2, 5, 7, 3, 9].
- Увеличивая j, теперь j = 1. Таким образом, соседняя пара равна 5 и 7. Здесь 5 меньше 7 и находится в правильном порядке. Так что не нужно их менять местами. Тогда массив будет [2, 5, 7, 3, 9].
- Увеличивая j, теперь j = 2. Таким образом, соседняя пара равна 7 и 3. Здесь 7 больше 3 и находится в неправильном порядке. Поэтому мы должны их поменять местами. Тогда массив станет [2, 5, 3, 7, 9].
См. Второй по величине элемент массива, равный 7, идет ко второй последней позиции массива. Таким образом, наша вторая итерация завершена.
Третья итерация
Перед переходом к третьей итерации массив будет [2, 5, 3, 7, 9]. Значения j будут 0 ‹= j‹ = 1.
- Теперь j = 0. Таким образом, соседняя пара - это 2 и 5. Здесь 2 меньше 5, и это в правильном порядке. Так что не нужно их менять местами. Тогда массив будет [2, 5, 3, 7, 9].
- Увеличивая j, теперь j = 1. Таким образом, соседняя пара равна 5 и 3. Здесь 5 больше 3 и находится в неправильном порядке. Поэтому мы должны их поменять местами. Тогда массив станет [2, 3, 5, 7, 9].
См. Третий по величине элемент массива, который равен 7, идет в третью последнюю позицию массива. Таким образом, наша третья итерация завершена.
Четвертая итерация
Перед входом в четвертую итерацию массив будет [2, 3, 5, 7, 9]. Значение j = 0, поэтому это наша последняя итерация.
Соседняя пара - 2 и 3. Здесь 2 меньше 3, и это в правильном порядке. Так что не нужно их менять местами. Тогда массив будет [2, 3, 5, 7, 9].
Прохладный. Мы завершили сортировку.
Итак, вот как мы можем реализовать пузырьковую сортировку и получить отсортированный порядок [2, 3, 5, 7, 9].
Реализация кодирования
См. Мою реализацию кодирования алгоритма пузырьковой сортировки с помощью Python ниже.
Спасибо за прочтение. Надеюсь, вам понравилось.
Хлопайте, если вам это нравится. Поделитесь им с каждым, если вам это нравится.
Подпишитесь на меня, чтобы узнать больше о структурах данных и алгоритмах, науке о данных, машинном обучении и глубоком обучении.
Я буду писать все больше и больше о машинном обучении. Подпишитесь, чтобы получать немедленные уведомления всякий раз, когда я публикую. Еще раз Большое спасибо за то, что потратили свое драгоценное время. До встречи в следующем блоге.
Если есть вопросы, опубликуйте их в поле ответа.
Следуй за мной на GitHub,
