В чем разница между алгоритмом быстрой сортировки и алгоритмом быстрого выбора?

Question

Помимо поиска только одной стороны массива, есть ли различия между быстрой сортировкой и быстрым выбором?

Answer 1

Одно отличие состоит в том, что поскольку на каждом уровне выполняется поиск только одного раздела, то вместо рекурсии можно использовать итерацию. Пример кода с использованием схемы разбиения Lomuto. В зависимости от шаблона данных может помочь более точный выбор (вместо [hi]).

int QuickSelect(int a[], int sz, int k)
{
    int lo = 0;
    int hi = sz-1;              // (no check for empty array)
    while (lo < hi){
        int p = a[hi];          // Lomuto partition
        int i = lo;
        for (int j = lo; j < hi; ++j){
            if (a[j] < p){
                std::swap(a[j], a[i]);
                ++i;
            }
        }
        std::swap(a[i], a[hi]);
        if (k == i)             // if pivot == kth element, return it
            return a[k];
        if (k < i)              // loop on partition with kth element
            hi = i - 1;
        else
            lo = i + 1;
    }
    return a[k];                // sorted to kth elemement, return it
}