CODEWITHSUNDEEP
c++loopsquicksort
adohertyd
adohertyd

Reputation: 2689

Find nth largest number infinite loop C++

I have a vector of N numbers and I want to find the nth number in the array. I'm using a variation of the quicksort but I'm getting an issue with infinite loops at times and I think it's if the largest number is the only option in the two arrays. A number can appear many times in the array so if, for example I select 10 for N and I want to find 1st largest number I might end up with {9,9} in the left array leading to an infinite loop. What can I do to remedy this? Here is my code.

#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;

}

Upvotes: 2

Views: 861

Answers (2)

rici
rici

Reputation: 241771

Since you are creating new vectors anyway (I suppose because you don't want to mutate the input vector), you might as well just avoid putting the pivot element into either left or right. In that case, if the pivot turns out to be the element you're looking for, it will be caught by else return pivot, and if you end up with the degenerate case where the partition is all equal elements, then nothing will be placed into either left or right, and the single value of the partition will be correctly returned.

The way quicksort avoids this problem is to never put the pivot element into the subvectors which are being sorted; consequently, even if one of the vectors ends up being all the same element, it still ends up being shorter than it was. That's a subtlety with quicksort which is rarely explained well, although Sedgwick does discuss ways to improve quicksort's performance on vectors with many repeated elements.

Upvotes: 2

Michael Shmalko
Michael Shmalko

Reputation: 710

Checking for either of sub-arrays being empty will help to detect infinite loop, and also a crash in some other cases.

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

Edit An infinite loop is only possible when either of the arrays is 0 and the other one is filled with the same value.

Upvotes: 1

Related Questions