Сортировка массивов:Изучаем алгоритмы
Пузырьковая сортировка: медленно, грустно, зато понятно
Есть алгоритмы, от которых веет скоростью и изяществом (привет,
quick sort).А есть bubble sort — максимально наглядный, максимально неторопливый.
Но даже у него есть своё предназначение. И в этой статье:
- Покажем, как он работает
- Напишем реализацию на C и Python
- Разберём сложность и когда всё же можно применять
Как работает пузырёк?
Представь, что у тебя есть массив чисел. И ты идёшь по нему, сравниваешь пары соседей и меняешь их местами, если они стоят "неправильно". И так — снова, и снова, пока всё не станет отсортировано.
Вот так числа как бы «всплывают» вверх — отсюда и название.
Реализация на C
C:
void bubble_sort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}🛠 Тут два вложенных цикла:
- внешний контролирует количество «проходов»,
- внутренний — сравнивает пары и «всплывает» большие числа вправо.
Реализация на Python
Python:
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]Python-версия выглядит проще, но делает те же самые действия.
Можно улучшить алгоритм флагом swapped — чтобы закончить раньше, если всё уже отсортировано.
Сложность алгоритма
| Сценарий | Сложность |
|------------------------- |--------------|
| Лучший случай | O ( n ) |
| Средний и худший | O(n²) |
| Память | O(1) |
Если массив почти отсортирован — пузырёк может сработать неплохо.Но при большом
n — всё, привет тормоза.
Почему пузырёк проигрывает другим сортировкам- Каждый элемент участвует в многочисленных сравнениях
- Неэффективен при больших объёмах
- Сильно уступает
merge sortиquick sort
Вывод
Пузырёк — не самый быстрый, но:- понятный,
- легко реализуемый,
- полезен в олимпиадной практике и тестах.
Если нужно быстро что-то отсортировать на 10–15 элементах — он сойдёт.
Другие алгоритмы сортировки: сравнение на Python и C
Пузырёк — самый первый алгоритм сортировки, который изучают.
Но что дальше? Где скорость? Где надёжность?
Давайте изучем и сравним:
- Insertion Sort
- Merge Sort
- Quick Sort
Insertion Sort — вставками
Представь, что ты сортируешь карты в руке: берёшь новую карту и вставляешь её в нужное место. Это и есть принцип вставок.
Перебираем элементы один за другим- ⬅ Сдвигаем все большие элементы вправо
- Вставляем текущий на своё место
Python:
Python:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
C:
void insertion_sort(int arr[], int size) {
for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
Отлично работает на маленьких или почти отсортированных массивах.---
Merge Sort — сортировка слиянием
Merge Sort — это рекурсивный алгоритм, основанный на принципе «разделяй и властвуй».Он разбивает массив на две части, сортирует каждую из них и затем сливает обратно в один отсортированный массив.
Суть работы:- Разделить массив пополам
- Рекурсивно отсортировать каждую часть
- Аккуратно объединить их в один отсортированный результат
---
Python: понятная реализация
Python:
def merge_sort(arr):
# База рекурсии
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
# Сливаем два отсортированных массива
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Добавляем оставшиеся элементы
result.extend(left[i:])
result.extend(right[j:])
return result---
C: простая и эффективная версия
C:
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Временные массивы
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
// Сливаем L[] и R[] обратно в arr[]
while (i < n1 && j < n2) {
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
// Добавляем оставшиеся элементы
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void merge_sort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}Пример использования:
C:
int main() {
int arr[] = {42, 15, 3, 23, 8, 5};
int n = sizeof(arr) / sizeof(arr[0]);
merge_sort(arr, 0, n - 1);
printf("Отсортированный массив: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}Пример итерационного подхода, без рекурсии:
C:
#include <stdio.h>
/* ――― вспомогательная функция слияния двух отсортированных отрезков ――― */
void merge(int a[], int left_start, int left_end,
int right_start, int right_end)
{
int n_left = left_end - left_start + 1;
int n_right = right_end - right_start + 1;
/* временные массивы для копирования левой и правой частей */
int L[n_left], R[n_right];
for (int i = 0; i < n_left; ++i) L[i] = a[left_start + i];
for (int j = 0; j < n_right; ++j) R[j] = a[right_start + j];
/* сливаем обратно в a[left_start … right_end] */
int i = 0, j = 0, k = left_start;
while (i < n_left && j < n_right) {
if (L[i] <= R[j])
a[k++] = L[i++];
else
a[k++] = R[j++];
}
/* дописываем «хвосты», если остались */
while (i < n_left) a[k++] = L[i++];
while (j < n_right) a[k++] = R[j++];
}
/* ――― итеративная (без рекурсии) сортировка слиянием ――― */
void merge_sort(int a[], int n)
{
/* длина сливаемых блоков: 1, 2, 4, 8, … */
for (int block = 1; block < n; block *= 2) {
/* перебираем пары блоков по всему массиву */
for (int left_start = 0; left_start < n; left_start += 2 * block) {
int left_end = left_start + block - 1;
int right_start = left_end + 1;
int right_end = right_start + block - 1;
/* корректируем правую границу, чтобы не выйти за массив */
if (right_start >= n) continue; /* второй блока нет */
if (right_end >= n) right_end = n - 1;
/* объединяем два соседних блока */
merge(a,
left_start, left_end,
right_start, right_end);
}
}
}
/* ――― демонстрация ――― */
int main(void)
{
int data[] = {42, 15, 3, 23, 8, 5};
int n = sizeof data / sizeof data[0];
printf("До : ");
for (int i = 0; i < n; ++i) printf("%d ", data[i]);
puts("");
merge_sort(data, n);
printf("После: ");
for (int i = 0; i < n; ++i) printf("%d ", data[i]);
puts("");
return 0;
}---
Сложность Merge Sort: O(n log n) Даже в худшем случае Merge Sort не деградирует до квадратичного времени (в отличие от Quick Sort).---
🛠 Когда использовать Merge Sort:
- Когда важна стабильность сортировки (сохраняет порядок равных элементов)
- Когда нужно предсказуемое время выполнения, независимо от входа
- Когда работаешь с связанными структурами (может быть реализован без выделения дополнительной памяти)
---
Quick Sort — быстрая сортировка
Разделяй и властвуй! Выбираем опорный элемент, разделяем массив на части, сортируем рекурсивно.- Рекурсивное разбиение массива
В среднем O(n log n), в худшем —O(n²)- ⏱ Часто используется как дефолтная сортировка в стандартных библиотеках
Python:
Python:
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + mid + quick_sort(right)
C:
void quick_sort(int arr[], int left, int right) {
if (left >= right) return;
int pivot = arr[(left + right) / 2];
int i = left, j = right;
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++; j--;
}
}
quick_sort(arr, left, j);
quick_sort(arr, i, right);
}Пример итерационного подхода, без рекурсии:
C:
#include <stdio.h>
/* свап без temp-макросов для простоты */
static inline void swap(int *a, int *b)
{
int t = *a; *a = *b; *b = t;
}
/* итеративный quick sort */
void quick_sort_iter(int a[], int n)
{
/* стек хранит пары [left, right] */
int stack[n];
int top = -1;
/* помещаем первый диапазон (весь массив) */
stack[++top] = 0;
stack[++top] = n - 1;
while (top >= 0)
{
/* извлекаем правую и левую границу */
int right = stack[top--];
int left = stack[top--];
if (left >= right) continue;
/* стандартное разбиение */
int pivot = a[(left + right) / 2];
int i = left, j = right;
while (i <= j)
{
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i <= j)
{
swap(&a[i], &a[j]);
i++; j--;
}
}
/* класть в стек сначала большую половину — экономнее по памяти */
if (i < right) { /* правая часть */
stack[++top] = i;
stack[++top] = right;
}
if (left < j) { /* левая часть */
stack[++top] = left;
stack[++top] = j;
}
}
}
/* демонстрация */
int main(void)
{
int data[] = {42, 15, 7, 23, 3, 9, 31};
int n = sizeof data / sizeof data[0];
printf("До : ");
for (int k = 0; k < n; ++k) printf("%d ", data[k]);
puts("");
quick_sort_iter(data, n);
printf("После: ");
for (int k = 0; k < n; ++k) printf("%d ", data[k]);
puts("");
return 0;
}---
Вывод
Код:
| Алгоритм | Когда использовать |
|------------------ |----------------------------------------------|
| Insertion Sort | маленькие массивы, почти отсортированные |
| Merge Sort | нужен гарантированный результат и стабильность |
| Quick Sort | максимальная скорость при средних данных |
А ты какую сортировку используешь чаще всего? Или предпочитаешь встроенные методы? Делись опытом ниже!- Следующая страница цикла: Стек и очередь: фундаментальные структуры данных
- Предыдущая статья цикла: Сложность алгоритмов: O(n), O(log n), O(n²) на пальцах
