Сортировка массивов:Изучаем алгоритмы

🫧 Пузырьковая сортировка: медленно, грустно, зато понятно​


Есть алгоритмы, от которых веет скоростью и изяществом (привет, 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
На двух языках: Python и C.

📥 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:
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:
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;
}

⚡ Очень быстрый на практике — особенно с рандомизацией pivot-а.
---

📎 Вывод​


Код: 
| Алгоритм           | Когда использовать                          |

|------------------  |----------------------------------------------|

| Insertion Sort     | маленькие массивы, почти отсортированные     |

| Merge Sort         | нужен гарантированный результат и стабильность |

| Quick Sort         | максимальная скорость при средних данных     |

💬 А ты какую сортировку используешь чаще всего? Или предпочитаешь встроенные методы? Делись опытом ниже!