🖥Быстрая сортировка (QuickSort) с использованием рекурсии

Проблема: cортировка больших массивов может быть неэффективной при использовании простых алгоритмов, таких как сортировка пузырьком или вставками.

Решение: Автор в книге Algorithms and Data Structures for OOP With C# демонстрирует реализацию QuickSort — одного из самых эффективных алгоритмов сортировки на практике, с рекурсивным разбиением массива.

Пример кода:

public class QuickSortExample
{
    public void QuickSort(int[] arr, int low, int high)
    {
        if (low < high)
        {
            int pi = Partition(arr, low, high);

            QuickSort(arr, low, pi - 1);
            QuickSort(arr, pi + 1, high);
        }
    }

    private int Partition(int[] arr, int low, int high)
    {
        int pivot = arr[high];
        int i = (low - 1);

        for (int j = low; j < high; j++)
        {
            if (arr[j] < pivot)
            {
                i++;
                (arr[i], arr[j]) = (arr[j], arr[i]);
            }
        }

        (arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
        return i + 1;
    }
}

Преимущества:
— Быстрая сортировка даже больших наборов данных
— Средняя сложность O(n log n)
— Эффективное использование памяти за счет рекурсии