В данном блоге я рассмотрю самою простую сортировку, которая поможет вам понять как работают сортировки.

- Почему метод называется методом пузырьком?

- Потому что легкие элементы (наименьшие) как-бы всплывают (прижимаются к левому краю списка), а тяжелые (самые большие) как-бы оседают на дно (прижимаются к правому краю списка). Таким способ массив и сортируется, так как самые элементы будут сортироваться в порядке возрастания: от самых легких, до самых тяжелых.

Что нам понадобиться для написания сортировки пузырьком:

• Умение писать циклы
• умение свопать (переставлять местами) элементы
• Массив

Код на C++:

#include <bits/stdc++.h>

#define int long long
#define forn(i, n) for(int (i) = 0; (i) < (n); (i)++)
using namespace std;
const int N = 6;
signed main() {
    int arr[N] = {5, 2, 8, 1, 9, 3};
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N - i - 1; ++j) {
            if (arr[j] > arr[j + 1]){ // сортируем массив по возрастанию
                swap(arr[j], arr[j + 1]); // переставляем элемент arr[j] и arr[j + 1]
            }
        }
    }
    // выводим элементы массива
    for(auto c: arr){
        cout << c << " ";
    }
    return 0;
}

Код на Python:

arr = [5, 2, 8, 1, 9, 3]
for i in range(len(arr)):
    for j in range(len(arr) - i - 1):
        if arr[j] > arr[j + 1]: # сортируем массив по возрастанию
            arr[j], arr[j + 1] = arr[j + 1], arr[j] # переставляем элемент arr[j] и arr[j + 1]
print(*arr) # выводим элементы массива

У вас может возникнуть логичный вопрос: А почему второй for идет от i до N — i — 1?

А потому что мы за каждую итерацию вложенного фора прижимаем наибольший элемент в массиве [0, N — i — 1], сейчас поясню: В первой итерации мы рассматриваем весь массив, от 0 до N — 1. До N — 1, потому что массив нумеруется с 0 и до N — 1.

Так вот:

• Первая итерация: прижимаем к правому краю max(arr[0, N — 1])
• Вторая итерация: прижимаем к правому краю max(arr[0, N — 2])
• Третья итерация: прижимаем к правому краю max(arr[0, N — 3])
• Четвертая итерация: прижимаем к правому краю max(arr[0, N — 4])
• и так далее...

В завершении блога хочу сказать, что этот алгоритм работает за квадрат O(n * n) — это медленно, так что в следующих блогах я рассмотрю более быстрые алгоритмы для сортировки

видео про пузырьковую сортировку: https://youtu.be/g6AAWruaSA8