Сортировка массива алгоритмом QuickSort в С++

Не так давно я рассматривал наиболее просто реализуемый алгоритм сортировки пузырьком. Но, как вы поняли он не самый быстрый! Алгоритм QuickSort был разработан C.A.R. Hoare и считается лучшим изобретённым алгоритмом сортировки. Он основан на идее разделений. Процедура состоит в выборе значения компарада (операнда в операции сравнения) с последующим разделением массива на две части. Элементы которые больше или равны ему перемещаются в одну часть, остальные — в другую. Этот процесс повторяется для каждой части массива до тех пор пока тот не станет полностью отсортированным.

К примеру возьмём массив fedacb и будем использовать в качестве компарада — d. После первого прохода массив преобразуется в такой — bcadef. После чего процесс повторится для bca и def.

Значение компарада выбирают двумя способами: либо случайным образом, либо выбирают значение из середины массива (я склоняюсь к использованию этого метода).

Вот текст алгоритма на С++ целиком:
 

#include <iostream>
#include <cstring>
using namespace std;

void quicksort(char *items, int len);
void qs(char *items, int left, int right);

int main() {
    char str[] = "984656131235484165";
    cout << "Массив в исходном порядке: " << str << "\n";
    quicksort(str, strlen(str));
    cout << "Отсортированный массив: " << str << "\n";
    return 0;
}

void quicksort (char *items, int len){
    /* при первом вызове предлагаем к сортировке весь массив. */
    qs(items, 0, len-1);
}

void qs(char *items, int left, int right){
    int i, j ;
    char x, y;
    i = left; j = right;

/* находим середину. для компаранда */
    x = items[( left+right) / 2 ];

/* переносим элементы в разделённые области */
    do {
        while((items[i] < x) && (i < right)) i++;
        while((x < items[j]) && (j > left)) j--;

        if(i <= j) {
            y = items[i];
            items[i] = items[j];
            items[j] = y;
            i++; j-- ;
        }
    } while(i <= j );

/* если массив не отсортирован вызываем функцию рекурсивно */
    if(left < j) qs(items, left, j ) ;
    if(i < right) qs(items, i, right);
}

Этот алгоритм отсортирует заданный массив по возвростанию.
После компиляции у меня получился вот такой вывод:

Массив в исходном порядке: 984656131235484165
Отсортированный массив: 111233444555666889

Как видите алгоритм сработал безупречно.
Стоит отметить, что в стандартной библиотеке С++ уже есть функция для сортировки, которая основана на этом алгоритме, — qsort()

Мы использовали две функции для удобства использования. В функции quicksort параметр items указывает на массив с данными для сортировки, а len — его длина. Функция qs() принимает область массива предлагаемую ей для сортировки.