Сортировка пузырьком: различия между версиями
Grphil (обсуждение | вклад) (Новая страница: «==Алгоритм== Это самый популярный алгоритм сортировки, хоть он и не самый очевидный. Пуст...») |
Grphil (обсуждение | вклад) |
||
Строка 28: | Строка 28: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | ==Оценка работы== | + | ==Оценка времени работы== |
{{ | {{ |
Текущая версия на 20:02, 14 августа 2019
Алгоритм
Это самый популярный алгоритм сортировки, хоть он и не самый очевидный. Пусть $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