В данном блоге я рассмотрю самою простую сортировку, которая поможет вам понять как работают сортировки.
- Почему метод называется методом пузырьком?
- Потому что легкие элементы (наименьшие) как-бы всплывают (прижимаются к левому краю списка), а тяжелые (самые большие) как-бы оседают на дно (прижимаются к правому краю списка). Таким способ массив и сортируется, так как самые элементы будут сортироваться в порядке возрастания: от самых легких, до самых тяжелых.
Что нам понадобиться для написания сортировки пузырьком:
- Умение писать циклы
- умение свопать (переставлять местами) элементы
- Массив
Код на 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])
- и так далее...