Участник:Alexeyshekhanov/Сортировка пузырьком

Сортировка пузырьком

Свойства и структура алгоритма

Общее описание алгоритма

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

Математическое описание алгоритма

Давайте представим список из n элементов, обозначим его как [math]\displaystyle{ A[0], A[1], ..., A[n-1] }[/math]. Сортировка пузырьком выполняет следующие шаги:

• Начнем с индекса [math]\displaystyle{ i = 0 }[/math].
• Для каждого [math]\displaystyle{ i }[/math] от [math]\displaystyle{ 0 }[/math] до [math]\displaystyle{ n - 1 }[/math], сравниваем [math]\displaystyle{ A[i] }[/math] и [math]\displaystyle{ A[i+1] }[/math]. Если [math]\displaystyle{ A[i] \gt  A[i+1] }[/math], меняем их местами.
• После первого прохода самый большой элемент окажется в конце списка.
• Уменьшаем n на 1 и повторяем шаги 1 и 2 для оставшихся элементов.
• Продолжаем выполнять проходы до тех пор, пока список не станет отсортированным.

Вычислительное ядро алгоритма

Вычислительное ядро последовательной версии сортировки пузырьком можно составить из, в худшем случае, [math]\displaystyle{ \frac{n (n - 1)}{2} }[/math] сравнений и обменов.

Макроструктура алгоритма

Как и было сказано выше, основную часть метода занимают сравнения и перестановки.

Схема реализации последовательного алгоритма

Реализация последовательного алгоритма на языке c++:

void bubbleSort(int arr[], int n) 
{ 
    int i, j; 
    for (i = 0; i < n - 1; i++)  
        for (j = 0; j < n - i - 1; j++) 
            if (arr[j] > arr[j + 1]) 
                swap(arr[j], arr[j + 1]); 
}

Последовательная сложность алгоритма

Относится к алгоритмам с квадратичной сложностью - o(n²)

Входные и выходные данные алгоритма

Входные данные: Произвольный массив размера n
Выходные данные: Тот же самый массив, но уже отсортированный

Литература

• Левитин А. В. Глава 3. Метод грубой силы: Пузырьковая сортировка // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 144—146. — 576 с. — ISBN 978-5-8459-0987-9
• Абрамов С. А., Лекции о сложности алгоритмов. — М.: МЦНМО, 2009. - 256 с. - ISBN 978-5-94057-433-0