Проблема выбора при использовании раздела Lomuto с неверными индексами - PullRequest
Новая
       29

Проблема выбора при использовании раздела Lomuto с неверными индексами

0 голосов
/ 19 октября 2019

В настоящее время я создаю алгоритм задачи выбора с использованием Lomuto Partition.

Это проблема поиска k-го наименьшего элемента в списке из n чисел, и я использую раздел для его поиска. Используя раздел, список переупорядочивается таким образом, чтобы левая часть содержала все элементы, меньшие или равные p, за которыми следует сама точка p, а затем все элементы, большие или равные p.

Inкод, я ввожу число k (k-е наименьшее k), и вывод должен возвращать k-е наименьшее число.

Когда я запускаю код и проверяю вывод, в большинстве случаев он работает хорошо, но когдаЯ ищу 5,6,7, 8-е наименьшее число, в котором запутан порядок (результат показывает, что 8-е наименьшее число - 6, а 7-е наименьшее - 22)

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

Вот функция быстрого выбора. 

    int Quickselect(int A[], int k, int len){
//s: index for the pivot.
//k: kth element value k.
//len: length of array

    int s = Partition(A, len);
    if (s == k-1) return A[s];      // if s==k-1 we found the kth smallest value and return, k-1 since k is the index of array
    else if (s > k-1) {             // if s>k-1 we divide the array and look for the kth value in the left part of the array
        int B[30];

        for(int i=0;i<s;i++)
            B[i] = A[i];

        Quickselect(B, k, s);
    }
    else{                           // if s<k-1 we divide the array and look for the kth value in the right part of the array
        int B[30];

        for(int i=0; i<len-s-1;i++)
            B[i]=A[s+1+i];

        Quickselect(B, k-1-s, len-s-1); 


    }
}

Вот полный код 

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

int Partition(int A[], int len);
// input: array A[], length of array A
// output: partitioned A[], new position of the pivot s

int Quickselect(int A[], int k, int len);
// input: array A[], kth smallest element k, length of array A
// output: the value of the kth smallest element in A[]


int main(void){

    int A[] = {4, 56, 73, 22, 1, 5, 3, 6, 7, 32, 98, 76, 8, 44, 99};    
    int len = sizeof(A)/sizeof(int);
    int k;

    printf("kth smallest element. what do you want for k? ");
    scanf("%d", &k);



    printf("the %dth smallest element is %d\n", k, Quickselect(A, k, len));

    printf("")
}


int Partition(int A[], int len){
    int l =0, r = len-1;        // l: left of array, r: right of array
    int pivot = A[0];           // the first element used as pivot
    int s = l;
    int temp;               // used for swapping values

    for(int i=l+1; i<=r; i++){
        if (A[i]<=pivot){
            s++;            // make space for the A[i] value to come in 
            temp = A[s];
            A[s]=A[i];
            A[i] = temp;
        }
        temp = A[s];
        A[s] = A[l];
        A[l] = temp;
    }

    return s;   // return index of pivot
}


int Quickselect(int A[], int k, int len){

    int s = Partition(A, len);
    if (s == k-1) return A[s];      // if s==k-1 we found the kth smallest value and return, k-1 since k is index of array
    else if (s > k-1) {             // if s>k-1 we divide the array and look for the kth value in the left part of the array
        int B[30];

        for(int i=0;i<s;i++)
            B[i] = A[i];

        Quickselect(B, k, s);
    }
    else{                           // if s<k-1 we divide the array and look for the kth value in the right part of the array
        int B[30];

        for(int i=0; i<len-s-1;i++)
            B[i]=A[s+1+i];

        Quickselect(B, k-1-s, len-s-1); 


    }
}

'''

Большое спасибо!

...