Определение

Быстрая сортировка - алгоритм сортировки, который работает по принципу разделения.

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

Быстрая сортировка работает следующим образом:

1. Выбирается опорный элемент в некоторой последовательности чисел

2. Разделение: все элементы делятся на два подмассива: подмассив элементов > опорного и подмассив элементов < опорного

3. Рекурсивно применить первые два шага к двум полученным подмассивам. Если в массиве два или меньше элементов, рекурсия не применяется.

Первый шаг

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

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

Второй шаг

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

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

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

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

Третий шаг

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

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

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

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

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

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

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

Пятый шаг

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

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

В зависимости от выбора опорного элемента скорость работы алгоритма может меняться. Если наш алгоритм будет сортировать уже отсортированную последовательность и опорным элементом будет всё время выбираться последний, то сложность алгоритма будет $O(n^2)$. Если же выбрать опорным средний элемент, то сложность упадёт до $O(n * log (n))$. Следовательно, лучше выбирать опорным средний элемент.

Псевдокод

Функция быстрая_сортировка(массив):  
    Если длина(массив) < 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;  
}