📊 Алгоритмы сортировки в C#

Этот документ описывает основные алгоритмы сортировки в C#, начиная от простых до более эффективных. Каждый алгоритм включает:

• Название
• Описание (что делает и когда полезен)
• Сложность (по времени и памяти)
• Псевдокод
• Реализацию на C#
• Подробное объяснение, почему и как он работает

---

1. 🟢 Сортировка пузырьком (Bubble Sort)

Описание

Сравниваются попарно соседние элементы и меняются местами, если стоят не по порядку. Процесс повторяется до полной отсортированности.

Сложность

• Время (худший случай): O(n²)
• Время (лучший случай): O(n)
• Память: O(1)

Псевдокод

повторять
  swapped = false
  для i от 1 до n - 1
    если array[i-1] > array[i]
      поменять местами array[i-1] и array[i]
      swapped = true
пока swapped == true

Реализация (C#)

void BubbleSort(int[] array)
{
    bool swapped;
    do
    {
        swapped = false;
        for (int i = 1; i < array.Length; i++)
        {
            if (array[i - 1] > array[i])
            {
                (array[i - 1], array[i]) = (array[i], array[i - 1]);
                swapped = true;
            }
        }
    } while (swapped);
}

Объяснение

Сортировка простая, понятная, но неэффективная на больших массивах. Единственная оптимизация — досрочное завершение при отсутствии обменов.

---

2. 🟡 Сортировка вставками (Insertion Sort)

Описание

Каждый новый элемент вставляется в уже отсортированную часть массива на своё место.

Сложность

• Время: O(n²)
• Лучший случай (почти отсортирован): O(n)
• Память: O(1)

Псевдокод

для i от 1 до n - 1
  key = array[i]
  j = i - 1
  пока j >= 0 и array[j] > key
    array[j + 1] = array[j]
    j--
  array[j + 1] = key

Реализация (C#)

void InsertionSort(int[] array)
{
    for (int i = 1; i < array.Length; i++)
    {
        int key = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > key)
        {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}

Объяснение

Отлично работает на небольших или почти отсортированных массивах. Используется также как часть других алгоритмов.

---

3. 🔹 Гномья сортировка (Gnome Sort)

Описание

Похожа на вставками, но если текущий элемент меньше предыдущего — двигается назад, пока не найдёт подходящее место.

Сложность

• Время: O(n²)
• Память: O(1)

Псевдокод

i = 0
пока i < n
  если i == 0 или array[i - 1] <= array[i]
    i++
  иначе
    обмен array[i] и array[i - 1]
    i--

Реализация (C#)

void GnomeSort(int[] array)
{
    int i = 0;
    while (i < array.Length)
    {
        if (i == 0 || array[i] >= array[i - 1])
            i++;
        else
        {
            (array[i], array[i - 1]) = (array[i - 1], array[i]);
            i--;
        }
    }
}

Объяснение

Упрощённая версия вставками. Работает медленно, но наглядно демонстрирует принцип сортировки на месте.

---

4. 🟠 Сортировка выбором (Selection Sort)

Описание

Находит наименьший элемент в неотсортированной части массива и меняет его с текущим элементом.

Сложность

• Время: O(n²)
• Память: O(1)

Псевдокод

для i от 0 до n - 1
  minIndex = i
  для j от i+1 до n
    если array[j] < array[minIndex]
      minIndex = j
  обмен array[i] и array[minIndex]

Реализация (C#)

void SelectionSort(int[] array)
{
    for (int i = 0; i < array.Length - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < array.Length; j++)
        {
            if (array[j] < array[minIndex])
                minIndex = j;
        }
        (array[i], array[minIndex]) = (array[minIndex], array[i]);
    }
}

Объяснение

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

---

5. 🔵 Быстрая сортировка (Quick Sort)

Описание

Выбирает опорный элемент (pivot) и делит массив на два: меньше и больше него. Рекурсивно сортирует подмассивы.

Сложность

• Время (среднее): O(n log n)
• Худший случай: O(n²)
• Память: O(log n)

Псевдокод

если массив пуст или из одного элемента
  вернуть
выбрать pivot
левый = все < pivot
правый = все > pivot
рекурсивно отсортировать левый и правый

Реализация (C#)

void QuickSort(int[] array, int left, int right)
{
    if (left >= right) return;
    int pivot = array[(left + right) / 2];
    int i = left, j = right;
    while (i <= j)
    {
        while (array[i] < pivot) i++;
        while (array[j] > pivot) j--;
        if (i <= j)
        {
            (array[i], array[j]) = (array[j], array[i]);
            i++; j--;
        }
    }
    QuickSort(array, left, j);
    QuickSort(array, i, right);
}

Объяснение

Очень быстрая сортировка на практике. Эффективна, если правильно выбрать pivot. Используется в стандартной Array.Sort() в .NET.

---

6. 🔷 Сортировка слиянием (Merge Sort)

Описание

Рекурсивно делит массив пополам, сортирует каждую половину и сливает их в один отсортированный массив.

Сложность

• Время: O(n log n)
• Память: O(n)

Псевдокод

если длина массива <= 1
  вернуть массив
разделить массив на две части
отсортировать обе части рекурсивно
объединить в один отсортированный массив

Реализация (C#)

int[] MergeSort(int[] array)
{
    if (array.Length <= 1)
        return array;

    int mid = array.Length / 2;
    int[] left = MergeSort(array[..mid]);
    int[] right = MergeSort(array[mid..]);

    return Merge(left, right);
}

int[] Merge(int[] left, int[] right)
{
    int[] result = new int[left.Length + right.Length];
    int i = 0, j = 0, k = 0;

    while (i < left.Length && j < right.Length)
        result[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];

    while (i < left.Length) result[k++] = left[i++];
    while (j < right.Length) result[k++] = right[j++];

    return result;
}

Объяснение

Гарантированная сложность O(n log n), стабилен и предсказуем. Используется в случае, если важна стабильность сортировки.

---

📊 Таблица сравнения алгоритмов

Алгоритм	Время (ср.)	Память	Стабильность	Особенности
Bubble Sort	O(n²)	O(1)	✅	Простой, но неэффективный
Insertion Sort	O(n²)	O(1)	✅	Эффективен на почти отсортированных
Gnome Sort	O(n²)	O(1)	✅	Визуально прост для понимания
Selection Sort	O(n²)	O(1)	❌	Предсказуем, но медленный
Quick Sort	O(n log n)	O(log n)	❌	Очень быстрый, но нестабильный
Merge Sort	O(n log n)	O(n)	✅	Предсказуем, стабильный

---