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

Материал из Algocode wiki
Версия от 20:02, 14 августа 2019; Grphil (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Алгоритм

Это самый популярный алгоритм сортировки, хоть он и не самый очевидный. Пусть $N$ - длина массива. Сортировка пузырьком заключается в том, что мы просто $N$ раз пройдемся по массиву и будем менять два соседних элемента, если первый больше второго. Можно посмотреть тут красивую визуализацию (вкладка MER). Заметьте, как каждую итерацию максимальный элемент "всплывает как пузырек" к концу массива.

Реализация

 1 void bubbleSort(vector<int>& array) {
 2     int n = (int)array.size(); // n - длина массива
 3     for (int i = 0; i < n; i++) { // n раз выполняем внутренний цикл
 4         for (int j = 0; j < n - 1; j++) { // сравниваем элемент со следующим
 5             if (array[j] > arr[j + 1]) { // меняем местами, если следующий меньше
 6                 swap(array[j], array[j + 1]);
 7             }
 8         }     
 9     }
10 }
11 
12 vector<int> a = {1, -3, 7, 88, 7};
13 bubbleSort(a);
14 for (auto elem : a) {
15     cout << elem << " ";
16 }
17 // результат: -3 1 7 7 88

Оценка времени работы

Утверждение: (Инвариант пузырька)
После $i$ шагов алгоритма сортировки пузырьком последние $i + 1$ чисел всегда отсортированы.

Доказательство остаётся читателю в качестве упражнения

Подумайте, какие лишние элементы просматриваются в данном алгоритме и как его можно оптимизировать.



Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko