Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

Быстрая сортировка (QuickSort) — это алгоритм сортировки, основанный на методе "разделяй и властвуй". Главная идея быстрой сортировки — выбрать опорный элемент (pivot) и переставить элементы так, чтобы все меньшие элементы находились слева от него, а большие — справа.

---

Сферы применения

Быстрая сортировка используется в ситуациях, где важна высокая скорость сортировки, особенно когда объём данных велик. Сферы применения быстрой сортировки:

• Системы управления базами данных
• Операционные системы
• Научные расчеты и обработка больших данных

---

Принцип работы алгоритма

Быстрая сортировка относится к алгоритмам "разделяй и властвуй" (divide and conquer). Она разделяет массив на две части, сортирует каждую из них отдельно, а затем объединяет результаты.

Основные шаги алгоритма

1. Выбор опорного элемента

   • В начале выбирается опорный элемент (pivot), вокруг которого будет происходить сортировка. Элемент может быть выбран случайным образом, быть первым или последним элементом массива или, как часто используется, быть медианой.

2. Разделение массива:

   • Массив делится на две части: одна часть содержит элементы меньше опорного элемента, другая — больше или равные. Это называется "разделение массива" (partitioning).

3. Рекурсивная сортировка:

   • Затем алгоритм рекурсивно применяет ту же процедуру к двум подмассивам (левая и правая части). Этот процесс продолжается до тех пор, пока массивы не станут длиной 1 или 0, после чего они считаются отсортированными.

4. Объединение результата:

   • На каждом уровне рекурсии объединяются отсортированные части массива, в результате чего получаем полностью отсортированный массив.

---

Особенности

• Высокая производительность на средних данных, особенно по сравнению с другими алгоритмами сортировки.
• Подходит для больших массивов данных.
• Использует принцип рекурсии и метод "разделяй и властвуй", что делает алгоритм быстрым и эффективным.
• В худшем случае может иметь сложность $O(n²)$, если не удачно выбрать опорный элемент.
• Не является устойчивым алгоритмом (сохраняет ли порядок равных элементов в исходной последовательности).

---

Вычислительная сложность

Средний случай

Вычислительная сложность равна $O(n*log(n))$. Это достигается благодаря тому, что на каждом шаге массив делится на две части, а сортировка выполняется для каждой части.

Доказательство

Для доказательства среднего случая используется рекуррентное уравнение:

$\huge T(n) = 2T\left(\frac{n}{2}\right) + n$

• $2T\left(\frac{n}{2}\right)$— время для сортировки двух подмассивов,
• $n$ — затраты на разбиение массива.

Решение рекуррентного уравнения

Разложим несколько шагов:

$\huge T(n) = 2T\left(\frac{n}{2}\right) + n$

$\huge T\left(\frac{n}{2}\right) = 2T\left(\frac{n}{4}\right) + \left(\frac{n}{2}\right)$

Постепенно суммируя, получаем:

$\huge T(n) = n + \frac{n}{2} + \frac{n}{4} + ... = n \log n$

Таким образом, время работы в среднем составляет $O(n \log (n))$.

Худший случай

Вычислительная сложность равна $O(n²)$. Он возникает, когда каждый раз опорный элемент делит массив очень неравномерно (например, всегда на 1 элемент и оставшуюся часть).

Доказательство

Допустим, у нас есть отсортированный массив:

$\huge [1, 2, 3, 4, 5]$

Если при каждом вызове пивотом выбирается первый элемент, то на каждой итерации опорный элемент будет $1$, затем $2$, и так далее, оставляя только одну подзадачу для сортировки массива, длиной на один элемент меньше.

• На первом шаге требуется $n$ сравнений.
• На втором шаге $n - 1$ сравнений.
• На третьем шаге $n - 2$ сравнений и так далее.

Итого, время работы будет:

$\huge T(n) = n + (n - 1) + (n - 2) + ... + 1 = \frac{n(n + 1)}{2} = O(n^2)$

Таким образом, вычислительная сложность составляет $O(n^2)$.

---

Пространственная сложность

Средний случай

В среднем глубина рекурсии будет $O(\log n)$, так как массив делится на два равных подмассива на каждом шаге.

Худший случай

В худшем случаи пространственная сложность равна $O(n)$. В худшем случае массив делится на одну часть из $(n-1)$ элементов и один элемент, что приводит к глубине рекурсии $O(n)$, так как рекурсия должна пройти все $n$ уровней.

---

Схематическая работа алгоритма

Дан массив:

Первый шаг

1. Выберем опорным элементом число $4$:

2. Разделим массив чисел на два подмассива: подмассив элементов, которые больше опорного элемента и подмассив элементов, которые меньше опорного элемента, получим:

Второй шаг

1. Выберем опорный элементы в массиве, в котором находятся числа большие числа $4$, пусть опороным элементом будет число $20$:

2. Разделим массив на два подмассива; подмассив с элементами, которые больше опорного элемента и подмассив с элементами, которые меньше опорного элемента, получим:

4. Выберем опорный элементы в массиве, в котором находятся числа меньшее числа $4$, пусть опороным элементом будет число $3$:

4. Разделим массив на два подмассива; подмассив с элементами, которые больше опорного элемента и подмассив с элементами, которые меньше опорного элемента, получим:

Третий шаг

1. Во втором подмассиве выберем опорным элементом число $6$:

2. Разделим массив на два подмассива; подмассив с элементами, которые больше опорного элемента и подмассив с элементами, которые меньше опорного элемента, получим:

Четвёртый шаг

1. После разбиения на массивы имеем подмассивы $[30]$, [ ], $[8, 6]$ и $[0, 1]$

2. Первый подмассив $[30]$, в нём всего один элемент, поэтому сортировка не применяется

3. Второй подмассив [ ], он пуст, поэтому сортировка не применяется

4. Третий подмассив имеет всего два элемента, сортировку применять не надо, их можно просто сравнить

5. Четвертый подмассив такой же, как и третий, следовательно, можно тоже их просто сравнить

Пятый шаг

Соединив получившиеся подмассивы и опорные элементы, получим отсортированный исходный массив:

---

Псевдокод

Функция быстрая_сортировка(массив):
    Если длина(массив) < 2:
        Вернуть массив

    индекс_опорного_элемента = длина(массив) // 2
    опорный_элемент = массив[индекс_опорного_элемента]
    Удалить элемент по индексу индекс_опорного_элемента из массива

    больше = пустой список
    меньше = пустой список

    Для каждого элемента i в массиве:
        Если i > опорный_элемент:
            Добавить i в список больше
        Иначе:
            Добавить i в список меньше

    Вернуть быстрая_сортировка(меньше) + [опорный_элемент] + быстрая_сортировка(больше)

---

Реализация на Python

Аннотация:
quick_sort - функция быстрой сортировки
array - сортируемый массив
pivot_index - индекс опорного элемента
pivot - опорный элемент
bigger - массив с элементами, которые большого опорного
smaller - массив с элементами, которые меньше опорного

def quick_sort(array):  
    if len(array) < 2:  
        return array  
        
    pivot_index = len(array) // 2  
    pivot = array[pivot_index]  
    array.pop(pivot_index)  
    bigger, smaller = list(), list()
      
    for i in array:
        if i > pivot:
            bigger.append(i)
            
        else:
            smaller.append(i)  
    
    return quick_sort(smaller) + [pivot] + quick_sort(bigger)

---

Олимпиадная реализация на C++

Аннотация:
typedef - переопределение имени типа данных
part - функция разбиения исходного массива на подмассивы
arr - сортируемый массив
begin - индекс массива с которого начинается сортировка
end - индекс массива на котором заканчивается сортировка
pivot - опорный элемент
quick_sort - функция быстрой сортировки

typedef vector<int> vi;
int part(vi &arr, int begin, int end) {
  int pivot = array[(begin + end) / 2];
  int i = begin;
  int j = end;
  while (true) {
    while (arr[i] < pivot) i++;
    while (arr[j] > pivot) j--;
    if (i >= j) return j;
    swap(arr[i++], arr[j--]);
  }
}

void quick_sort(vi &arr, int begin, int end) {
  if (begin < end) {
    int pi = part(arr, begin, end);
    quick_sort(arr, begin, pi);
    quick_sort(arr, pi + 1, end);
  }
  return;
}

---

Продуктовая реализация на C++

Аннотация:
template - шаблон функции
typename T - шаблонный тип данных параметра
partition - функция разбиения исходного массива на подмассивы
array - сортируемый массив
begin - индекс массива с которого начинается сортировка
end - индекс массива на котором заканчивается сортировка
pivot - опорный элемент
quick_sort - функция быстрой сортировки

template <typename T>
int partition(std::vector<T> &array, int begin, int end) {
  T pivot = array[(begin + end) / 2];
  int i = begin;
  int j = end;

  while (true) {
    while (array[i] < pivot) i++;

    while (array[j] > pivot) j--;

    if (i >= j) return j;

    std::swap(array[i++], array[j--]);
  }
}

template <typename T>
void quick_sort(std::vector<T> &array, int begin, int end) {
  if (begin < end) {
    int pivot_index = partition(array, begin, end);
    quick_sort(array, begin, pivot_index);
    quick_sort(array, pivot_index + 1, end);
  }
  return;
}