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

Быстрая сортировка (Quick Sort): Один из самых быстрых алгоритмов сортировки. Его можно применить на алгоритмическом собесе и произвести хорошее впечатление на интервьюеров.
Этот алгоритм относится к группе алгоритмов "разделяй и властвуй". Он выбирает опорный элемент из массива и разделяет массив на две части: элементы, меньшие опорного, и элементы, большие опорного. Затем он рекурсивно сортирует каждую из этих частей. Быстрая сортировка обладает хорошей производительностью и может быть ОЧЕНЬ эффективной на практике. Давайте разберем алгоритм поэтапно.

Всего у этого алгоритма 3 этапа:

1. берем не отсортированный массив [5,2,4,6,1,15]
2. выбираем ”опорный” элемент, от которого будем отталкиваться при разделении, пусть это будет “6”
3. размещаем меньшие значения слева от опорного элемента, а большие - справа, делаем это путем прохода каждого элемента

Итак, получаем [1,4,2,5] - 6 - [15]

Как видим у нас слева и справа от опорного элемента образовалось 2 массива, при том что правый массив сортировать больше не нужно! Так как там один элемент.

Итого у нас остается только левый массив, с которым мы повторяем шаги с 1 по 3.(так проявляется рекурсивность алгоритма, в коде функция вызывает сама себя, и мы по сути повторяем ранее описанные действия)

1. берем не отсортированный массив [1,4,2,5]
2. выбираем ”опорный” элемент, от которого будем отталкиваться при разделении, пусть это будет последний элемент “5”
3. размещаем меньшие значения слева от опорного элемента, а большие - справа, делаем это путем прохода каждого элемента

Итак, получаем [1,4,2] - 5 - []
Снова повторяем шаги 1-3 для оставшегося левого массива, опорный элемент в следующем проходе будет “4”

[1,2] - 4
Теперь обьединяем все полученные массивы воедино:
[1 ,2 ,4 ,5 ,6, 15]

PROFIT! Теперь вы знаете рекурсивный алгоритм быстрой сортировки. 

Реализация на C#:

using System;

class QuickSort
{
    // Метод для сортировки массива arr от left до right
    public static void Sort(int[] arr, int left, int right)
    {
        if (left < right)
        {
            int pivot = Partition(arr, left, right);
            Sort(arr, left, pivot - 1);
            Sort(arr, pivot + 1, right);
        }
    }

    // Метод для разделения массива и возврата индекса опорного элемента
    private static int Partition(int[] arr, int left, int right)
    {
        int pivot = arr[right];
        int i = left - 1;

        for (int j = left; j < right; j++)
        {
            if (arr[j] < pivot)
            {
                i++;
                Swap(ref arr[i], ref arr[j]);
            }
        }

        Swap(ref arr[i + 1], ref arr[right]);
        return i + 1;
    }

    // Метод для обмена значений двух элементов
    private static void Swap(ref int a, ref int b)
    {
        int temp = a;
        a = b;
        b = temp;
    }

    static void Main()
    {
        int[] arr = { 5, 2, 4, 6, 1, 15 };
        Sort(arr, 0, arr.Length - 1);

        Console.WriteLine("Sorted array:");
        foreach (var num in arr)
        {
            Console.Write(num + " ");
        }
    }
}

Источник - https://vk.com/feed?w=wall-218375169_13457