Алгоритм QuickSelect

Я занимаюсь различными учебными материалами и статьями, которые обсуждают quicksort и quickselect, однако мое понимание их по-прежнему шаткое.

Учитывая эту структуру кода, мне нужно уметь понять и объяснить, как работает quickselect.

// return the kth smallest item
int quickSelect(int items[], int first, int last, int k) {
    int pivot = partition(items, first, last);
    if (k < pivot-first) {
        return quickSelect(items, first, pivot, k);
    } else if (k > pivot) {
        return quickSelect(items, pivot+1, last, k-pivot);
    } else {
        return items[k];
    }
}

Мне нужно немного помочь с разбивкой на псевдокод, и пока мне не предоставлен код функции раздела, я хотел бы понять, что он будет делать, если предоставлена функция quickselect.

Я знаю, как работает quicksort, а не быстро. Код, который я только что представил, представляет собой пример, который мы получили о том, как форматировать быстрый выбор.

EDIT: исправленный код

int quickSelect(int items[], int first, int last, int k) 
{
    int pivot = partition(items, first, last);
    if (k < pivot-first+1) 
    { //boundary was wrong
        return quickSelect(items, first, pivot, k);
    } 
    else if (k > pivot-first+1) 
    {//boundary was wrong
        return quickSelect(items, pivot+1, last, k-pivot);
    }
    else 
    {
        return items[pivot];//index was wrong
    }
}

Судебная процедура: @Haitao

Ответы

Ответ 1

Важной частью быстрого выбора является раздел. Поэтому позвольте мне сначала объяснить это.

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

Теперь мы находим k-й наименьший элемент. После случаев разделения:

k == pivot. Тогда вы уже нашли kth самых маленьких. Это связано с тем, что раздел работает. Есть ровно k - 1 элементы, которые меньше, чем элемент kth.
k < pivot. Тогда kth наименьшее находится в левой части pivot.
k > pivot. Тогда kth наименьшее находится на правой стороне стержня. И чтобы найти его, вам действительно нужно найти k-pivot наименьшее число справа.

Ответ 2

btw, ваш код содержит несколько ошибок.

int quickSelect(int items[], int first, int last, int k) {
    int pivot = partition(items, first, last);
    if (k < pivot-first+1) { //boundary was wrong
        return quickSelect(items, first, pivot, k);
    } else if (k > pivot-first+1) {//boundary was wrong
        return quickSelect(items, pivot+1, last, k-pivot);
    } else {
        return items[pivot];//index was wrong
    }
}

Ответ 3

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

Я говорил об остальном в предыдущем ответе .

Ответ 4

int partition(vector<int> &vec, int left, int right, int pivotIndex)
{
        int pivot = vec[pivotIndex];
        int partitionIndex = left;

        swap(vec[pivotIndex],vec[right]);
        for(int i=left; i < right; i++) {
                if(vec[i]<pivot) {
                        swap(vec[i],vec[partitionIndex]);
                        partitionIndex++;
                }
        }
        swap(vec[partitionIndex], vec[right]);

        return partitionIndex;
}

int select(vector<int> &vec, int left, int right, int k)
{
        int pivotIndex;
        if (right == left) {
                return vec[left];
        }
        pivotIndex = left + rand() % (right-left);

        pivotIndex = partition(vec,left,right,pivotIndex);
        if (pivotIndex == k) {
                return vec[k];
        } else if(k<pivotIndex) {
                /*k is present on the left size of pivotIndex*/
                return partition(vec,left,pivotIndex-1, k);
        } else {
                /*k occurs on the right size of pivotIndex*/
                return partition(vec, pivotIndex+1, right, k);
        }
        return 0;
}

Ответ 5

int quickSelect(int A[], int l, int h,int k)
{
        int p = partition(A, l, h); 
        if(p==(k-1)) return A[p];
        else if(p>(k-1)) return quickSelect(A, l, p - 1,k);  
        else return quickSelect(A, p + 1, h,k);

}

//функция раздела такая же, как QuickSort

Ответ 6

Вы можете найти quickSelect здесь, используя трехстороннее разделение.

Код написан в Scala. Кроме того, я буду добавлять больше алгоритмов и структур данных в своем путешествии к освоению предмета.

Вы также можете заметить, что существует средняя функция для массивов с нечетным числом элементов, реализованных с помощью метода quickSelect.

edit: требуется перетасовать массив, чтобы гарантировать линейное среднее время работы