Мой быстрый выбор возвращает k-е значение, а не k-е наименьшее значение - PullRequest
Новая
       16

Мой быстрый выбор возвращает k-е значение, а не k-е наименьшее значение

0 голосов
/ 27 апреля 2020

Я пытаюсь реализовать Quickselect, который должен найти k-й наименьший элемент в массиве целых. Однако функция findKthSmallest () возвращает k-е значение, а не k-е наименьшее. Я не могу понять, почему это происходит - я перепробовал множество небольших изменений, а теперь несколько раз перефразировал и переписывал. Кажется, это должно быть очень просто, но я не знаю. Вот мой код C ++: 

#include <iostream>
#include <vector>
#include <random>
#include <string>
using namespace std;

//note: when i put an 'I' at the end of a variable name, it stands for Index. (and V stands for Value)

string vecToStr(vector<int>);

class KSE {//KSE stands for Kth Smallest Element
public:
    KSE(vector<int> S, int K);
    vector<int> set;
    int k;
    int kthSmallest;
private:
    int findKthSmallest();
//  int findKthSmallest(int leftI, int rightI);
    int partition(int leftI, int rightI, int pivotI);
    void swap(int aI, int bI);
};

//KSE definitions:

KSE::KSE(vector<int> S, int K) {
    set = S;
    k = K;
    kthSmallest = findKthSmallest();
}

int KSE::findKthSmallest() {
    int leftI = 0;
    int rightI = set.size() - 1;
    int pivotI = -1;
    while (true) {
        if (leftI == rightI)
            break;//-----------------------------break

        //pivotI = rand() % (rightI - leftI + 1) + leftI - 1;//random number in the range of leftI to rightI, inclusive
        pivotI = leftI;
        cout << "pivot is " << set[pivotI] << endl;
        pivotI = partition(leftI, rightI, pivotI);

        cout << "set after partition: " << vecToStr(set) << endl;

        if (k == pivotI)
            break;
        else if (k < pivotI)
            rightI = pivotI - 1;
        else//if k > pivotI
            leftI = pivotI + 1;

        cout << "loopdone" << endl;
    }
    return set[k];
}

int KSE::partition(int leftI, int rightI, int pivotI) {
    //https://youtu.be/MZaf_9IZCrc
    int i = leftI - 1;
    for (int j = leftI; j <= rightI - 1; j++) {
        if (set[j] < set[pivotI]) {
            i++;
            swap(i, j);
        }
    }
    swap(i + 1, pivotI);
    pivotI = i + 1; 
    return pivotI;
}

void KSE::swap(int aI, int bI) {
    cout << "swapping " << set[aI] << " with " << set[bI] << endl;
    int tempV = set[aI];
    set[aI] = set[bI];
    set[bI] = tempV;
}

int main() {

    vector<int> kse_case1_set = { 2,3,5,8,12,1,7,10,13,30,6,14,15,18,22 };
    int kse_case1_k1 = 4;
    cout << "Testing Find Kth Element Algorithm" << endl << endl;
    cout << "set = " << vecToStr(kse_case1_set) << endl;

    KSE test1 = KSE(kse_case1_set, kse_case1_k1);
    cout << "when k = " << test1.k << endl;
    cout << "\tkth smallest element = " << test1.kthSmallest  << endl << endl;

    cout << "Press Enter to exit.";
    cin.get();
}

//to help with printing test cases:
string vecToStr(vector<int> vec) {
    string str = "[";
    for (int i{ 0 }; i < vec.size() - 1; i++) {
        str += to_string(vec[i]);
        str += ", ";
    }
    str += to_string(vec[vec.size() - 1]);
    str += "]";
    return str;
}

И вот что он выводит: 

set = [2, 3, 5, 8, 12, 1, 7, 10, 13, 30, 6, 14, 15, 18, 22]
pivot is 2
swapping 2 with 1
swapping 3 with 1
set after partition: [3, 1, 5, 8, 12, 2, 7, 10, 13, 30, 6, 14, 15, 18, 22]
loopdone
pivot is 5
swapping 5 with 2
swapping 8 with 2
set after partition: [3, 1, 8, 2, 12, 5, 7, 10, 13, 30, 6, 14, 15, 18, 22]
loopdone
pivot is 12
swapping 12 with 5
swapping 12 with 5
set after partition: [3, 1, 8, 2, 12, 5, 7, 10, 13, 30, 6, 14, 15, 18, 22]
loopdone
when k = 4
        kth smallest element = 12

Press Enter to exit.

4-й наименьший элемент (начиная с 0-го) должен быть 6, а не 12. Вы, ребята, ребята? знаете, что идет не так?

...