Просмотр исходного текста страницы Сортировка пузырьком (Bubble Sort)

Конечно, вот описание сортировки пузырьком, переделанное в вики-разметку:

= Описание =
Сортировка пузырьком — это простой алгоритм сортировки, который многократно проходит по списку, сравнивая соседние элементы и меняя их местами, если они находятся в неправильном порядке. Элементы с большими значениями постепенно "всплывают" к концу списка, как пузырьки в воде, отсюда и название алгоритма.

= Принцип работы =
# '''Сравнение соседних элементов:''' Алгоритм начинает с первого элемента списка и сравнивает его со вторым элементом.
# '''Обмен элементов:''' Если первый элемент больше второго, они меняются местами.
# '''Проход по списку:''' Этот процесс повторяется для каждой пары соседних элементов до конца списка. В результате самого большого элемента "всплывает" в конец списка.
# '''Повторение процесса:''' Шаги 1-3 повторяются для оставшейся части списка (исключая последний элемент, который уже отсортирован).
# '''Завершение:''' Процесс повторяется до тех пор, пока не будут отсортированы все элементы списка.

; Сравнение соседних элементов:
: Алгоритм начинает с первого элемента списка и сравнивает его со вторым элементом.
; Обмен элементов:
: Если первый элемент больше второго, они меняются местами.
; Проход по списку:
: Этот процесс повторяется для каждой пары соседних элементов до конца списка. В результате самого большого элемента "всплывает" в конец списка.
; Повторение процесса:
: Шаги 1-3 повторяются для оставшейся части списка (исключая последний элемент, который уже отсортирован).
; Завершение:
: Процесс повторяется до тех пор, пока не будут отсортированы все элементы списка.

= Пример =
Пусть у нас есть следующий список: <code>[5, 1, 4, 2, 8]</code>

# '''Первый проход:'''
## <code>(5, 1, 4, 2, 8)</code> → <code>(1, 5, 4, 2, 8)</code> (5 и 1 меняются местами)
## <code>(1, 5, 4, 2, 8)</code> → <code>(1, 4, 5, 2, 8)</code> (5 и 4 меняются местами)
## <code>(1, 4, 5, 2, 8)</code> → <code>(1, 4, 2, 5, 8)</code> (5 и 2 меняются местами)
## <code>(1, 4, 2, 5, 8)</code> → <code>(1, 4, 2, 5, 8)</code> (5 и 8 не меняются местами)
: После первого прохода наибольший элемент (8) находится в конце списка.
# '''Второй проход:'''
## <code>(1, 4, 2, 5, 8)</code> → <code>(1, 4, 2, 5, 8)</code>
## <code>(1, 4, 2, 5, 8)</code> → <code>(1, 2, 4, 5, 8)</code> (4 и 2 меняются местами)
## <code>(1, 2, 4, 5, 8)</code> → <code>(1, 2, 4, 5, 8)</code>
: После второго прохода второй наибольший элемент (5) находится на своем месте.
# '''Третий проход:'''
## <code>(1, 2, 4, 5, 8)</code> → <code>(1, 2, 4, 5, 8)</code>
## <code>(1, 2, 4, 5, 8)</code> → <code>(1, 2, 4, 5, 8)</code>
: После третьего прохода третий наибольший элемент (4) находится на своем месте.
# '''Четвертый проход:'''
## <code>(1, 2, 4, 5, 8)</code> → <code>(1, 2, 4, 5, 8)</code>

В результате список отсортирован: <code>[1, 2, 4, 5, 8]</code>

= Реализация на Python =
<syntaxhighlight lang="python">
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# Пример использования
arr = [5, 1, 4, 2, 8]
sorted_arr = bubble_sort(arr)
print(sorted_arr)  # Вывод: [1, 2, 4, 5, 8]
</syntaxhighlight>

= Характеристики =
* '''Простота:''' Легко понять и реализовать.
* '''Сложность:'''
** Временная сложность:
*** Лучший случай: O(n) (если список уже отсортирован)
*** Средний случай: O(n^2)
*** Худший случай: O(n^2)
** Пространственная сложность: O(1) (не требует дополнительной памяти)
* '''Устойчивость:''' Сортировка пузырьком является устойчивым алгоритмом, то есть элементы с одинаковыми значениями сохраняют свой относительный порядок после сортировки.

= Оптимизация =
Алгоритм можно немного оптимизировать, чтобы избежать ненужных проходов, если на предыдущем проходе не было выполнено ни одного обмена. Это означает, что список уже отсортирован.

<syntaxhighlight lang="python">
def optimized_bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break  # Если не было обменов, список отсортирован
    return arr

# Пример использования
arr = [5, 1, 4, 2, 8]
sorted_arr = optimized_bubble_sort(arr)
print(sorted_arr)  # Вывод: [1, 2, 4, 5, 8]
</syntaxhighlight>

= Когда использовать =
Сортировка пузырьком обычно не используется для больших объемов данных из-за своей квадратичной временной сложности. Она может быть полезна для небольших списков или в учебных целях из-за своей простоты.