Реализация быстрого выбора

Question

Я пытаюсь реализовать алгоритм быстрого выбора. Хотя я очень хорошо понял теорию, стоящую за этим; Мне трудно преобразовать это в хорошо функционирующую программу.

Вот как я буду шаг за шагом реализовывать это и где я сталкиваюсь с проблемой:

Проблема: Найти 4-й наименьший элемент в A[] = {2,1,3,7,5,4,6}

k = 4,

индекс:0|1|2|3|4|5|6

Соответствующие значения: 2|1|3|7|5|4|6

первоначально, l = 0 а также r = 6

Шаг 1) Принятие точки поворота в качестве самого левого элемента (точка поворота всегда будет самой левой в этой задаче)-

pivot_index = 0

pivot_value = 2

Шаг 2) Применение раздела algo; поставить точку в нужном месте ([<p][p][>p])-

Мы получаем следующий массив: 1|2|3|7|5|4|6

где, pivot_index = i-1 = 1

и поэтому, pivot_value = 2

Шаг 3) Сравнить pivot_index с k-

k=3, pivot_index = 1; k>pivot_index

Следовательно, наше k-е наименьшее число лежит в правой части массива.

Правый массив = i to r а мы не заморачиваемся с левой частью (l to i-1) больше.

Шаг 4) Мы изменяем значение k как k - (pivot_index) => 4-1 = 2; k = 3,

Вот проблема: не должна ценность k быть 2? Потому что у нас есть два значения в левой части массива: 1|2? Должны ли мы рассчитать k как k - (pivot_index+1)?

Давайте предположим k = 3 верно.

Шаг 5) "Новый" массив для работы: 3|7|5|4|6 с соответствующими индексами: 2|3|4|5|6

Сейчас, pivot_index = 2 а также pivot_index = 3

Шаг 6) Применение алгоритма раздела к вышеуказанному массиву

3|7|5|4|6 (массив остается неизменным, так как сам pivot является самым низким значением).i = 3

pivot_index = i-1 = 2pivot_value = 3

Шаг 7) Сравнить pivot_index с k

k=3 а также pivot_index=2

k > pivot_index

и так далее....

Правильный ли этот подход?

Вот мой код, который не работает. Я использовал генератор случайных чисел для выбора случайного центра, который затем заменяется первым элементом в массиве.

#include<stdio.h>
#include<stdlib.h>

void print_array(int arr[], int array_length){

    int i;

    for(i=0; i<array_length; ++i) {
        printf("%d ", arr[i]);
    }

}

int random_no(min, max){

    int diff = max-min;
    return (int) (((double)(diff+1)/RAND_MAX) * rand() + min);

}

void swap(int *a, int *b){

    int temp; 

    temp = *a;
    *a = *b;
    *b = temp;
}

int get_kth_small(int arr[], int k, int l, int r){

    if((r-l) >= 1){

        k = k + (l-1); 

        int pivot_index = random_no(l, r);

        int i, j;
        swap(&arr[pivot_index], &arr[l]);           //Switch the pivot with the first element in the array. Now, the pivit is in arr[l]

        i=l+1;

        for(j=l+1; j<=r; ++j){
            if(arr[j]<arr[l]){
                swap(&arr[j], &arr[i]);
                ++i;
            }
        }

        swap(&arr[l], &arr[i-1]);                   //Switch the pivot to the correct place; <p, p, >p

        printf("value of i-1: %d\n", i-1);
        printf("Value of k: %d\n", k);

        if(k == (i-1)){
            printf("Found: %d\n", arr[i]);
            return 0;
        }

        if(k>(i-1)){
            k=k-(i-1);
            get_kth_small(arr, k, i, r);
        } else {
            get_kth_small(arr, k, l, r-1);
        }

        //get_kth_small(arr, k, i, r);
        //get_kth_small(arr, k, l, i-1);

    }

}

void main(){

    srand(time(NULL));

    int arr[] = {2,1,3,7,5,4,6};
    int arr_size = sizeof(arr)/sizeof(arr[0]);
    int k = 3, l = 0;
    int r = arr_size - 1;

    //printf("Enter the value of k: ");
    //scanf("%d", &k);

    get_kth_small(arr, k, l, r);

    print_array(arr, arr_size);
    printf("\n");

}

Answer 1

То, что вы описываете, является правильным способом реализовать быстрый выбор. Существует множество других подходов к выбору оси, и большинство из них даст ожидаемую сложность лучше, но по сути алгоритм тот же.

Answer 2

"Шаг 2: поставить точку поворота в нужном месте": не делайте этого. На самом деле вы не можете поставить точку поворота в нужном месте, так как не знаете, что это такое. Правило разбиения состоит в том, чтобы все элементы были меньше или равны, чем стержень, перед теми, которые больше. Просто оставьте точку, где она есть!

Быстрый выбор происходит следующим образом: найти Kth среди N Элементы, 1) выбрать значение поворота, 2) переместить все элементы меньшие или равные оси поворота перед другими, образуя две зоны длины Nle а также Ngt3) Рекурсировать на соответствующую зону с (K, Nle) или же (K-Nle, Ngt), до тех пор N=1,

На самом деле, любое значение может быть принято за сводку, даже если оно не представлено в массиве; но раздел должен быть таким, чтобы Nle а также Ngt ненулевые