2

N 個の数値のベクトルがあり、配列内の n 番目の数値を見つけたいと考えています。クイックソートのバリエーションを使用していますが、無限ループの問題が発生することがあります.2つの配列で最大数が唯一のオプションであると思います. 数値は配列に何度も表示される可能性があるため、たとえば、N に 10 を選択し、1 番目に大きい数値を見つけたい場合、左側の配列で {9,9} になって無限ループにつながる可能性があります。これを解決するにはどうすればよいですか? これが私のコードです。

#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <vector>

using namespace std;
int partition(int n, int arrsize, vector<int> intarr); //pass vector by val

int main() {

    int n, N;

    cout << "Please enter n: " << endl;
    cin >> n;
    cout << "Please enter N: " << endl;
    cin >> N;

    vector<int> array;
    srand(time(NULL));

    for(i=0; i < N; i++) {
        array.push_back(1 + rand() % N);
        cout << array.at(i) << ", ";
    }

    //Get the nth largest value of array[N]
    int arraylen = array.size();
    cout << "\nArraylen is " <<  arraylen << endl;
    int result = partition(n, arraylen, array);

    cout << "The " << n << "th largest number is: " << result <<endl;

    return 0;
}

int partition(int n, int arrsize, vector<int> intarr) {
    //1. Get a random value from the array:
        int random = rand() % arrsize;
        int pivot = intarr.at(random);

    //2. Partition the array into 2 halves left < pivot > right
        vector<int> left;
        vector<int> right;

        for(int j=0; j < arrsize; j++) {
            if (intarr[j] >= pivot)
                left.push_back(intarr[j]);
            else if (intarr.at(j) < pivot)
                right.push_back(intarr[j]);
            else continue;
        }

        cout << "\n \n" << "Left = ";

        for(int k = 0; k < left.size(); k++) {
            cout << left.at(k) << ", ";
        }

        cout << endl << "Right = ";

        for(int k = 0; k < right.size(); k++) {
            cout << right.at(k) << ", ";
        }

        int leftlen = left.size();
        int rightlen = right.size();

        if (n < leftlen)
            return partition(n, leftlen, left);

        else if (n > (arrsize - rightlen)) {
            n = n - (leftlen);
            return partition(n, rightlen, right);
        }

        else return pivot;

}
4

2 に答える 2

2

とにかく新しいベクトルを作成しているので（入力ベクトルを変更したくないためだと思います）、ピボット要素を左また​​は右に配置しないようにすることもできます。その場合、ピボットが探している要素であることが判明した場合、それは によってキャッチされelse return pivot、パーティションがすべて等しい要素である退化したケースになると、左のどちらにも何も配置されませんまたは正しい場合、パーティションの単一の値が正しく返されます。

クイックソートがこの問題を回避する方法は、ソートされるサブベクトルにピボット要素を決して入れないことです。その結果、ベクトルの 1 つがすべて同じ要素になってしまったとしても、それでも以前よりも短くなってしまいます。これはクイックソートの微妙な点であり、うまく説明されることはめったにありませんが、Sedgwick は多くの繰り返し要素を持つベクトルでのクイックソートのパフォーマンスを向上させる方法について議論しています。

于 2012-11-17T00:35:33.593 に答える
1

サブ配列のいずれかが空であることを確認すると、無限ループや他の場合のクラッシュを検出するのに役立ちます。

int leftlen = left.size();
int rightlen = right.size();
if (leftlen == 0 || rightlen == 0) /* break processing */

編集無限ループは、配列のいずれかが 0 で、もう一方が同じ値で埋められている場合にのみ可能です。

于 2012-11-17T00:08:27.653 に答える