Could anyone tell me what is wrong with my code:

int Partition(vector<string>& userIDs, int i, int k) {
    int pivot = (i   (k - i) / 2);
    string temp;
    
    while(i<k) {
        cout << "pivot:" << pivot << endl;
        while (userIDs.at(i).compare(userIDs.at(pivot))<0) {
            cout << "1. i:"<<i<<" UserIDs.at(i):" << userIDs.at(i) << " UserID.at(pivot): " << userIDs.at(pivot) << endl;
            i  = 1;
        }
        while (userIDs.at(pivot).compare(userIDs.at(k))<0) {
            cout << "2. k:" << k << " UserIDs.at(k):" << userIDs.at(k) << " UserID.at(pivot): " << userIDs.at(pivot) << endl;
            k -= 1;
        }

        if(i<k){
            cout << "3. i:" << i << " k:"<<k<<" UserIDs.at(i):" << userIDs.at(i) << " UserID.at(k) : " << userIDs.at(k) << endl;
            temp = userIDs.at(i);
            userIDs.at(i) = userIDs.at(k);
            userIDs.at(k) = temp;
            i  ;
            k--;
        }
        cout << "4. i:" << i << " k:" << k << endl;
    }
    cout << " 5. k:" << k << endl;
    return k;
}

void Quicksort(vector<string>& userIDs, int i, int k) {
    cout << "Quicksort i:" << i << " k:" << k << endl;
    if (i >= k) {
        return;
    }
    int lowEndIndex = Partition(userIDs, i, k);
    cout << "Quicksort lowEndIndex:" << lowEndIndex << endl;
    Quicksort(userIDs, i, lowEndIndex);
    Quicksort(userIDs, lowEndIndex 1, k);
}

When I input this list:

BigBen
GardenHeart
GreyMare
TeenPunch
WhiteSand
LifeRacer
Doom
AlienBrain

I get:

AlienBrain
BigBen
GreyMare
GardenHeart
Doom
LifeRacer
TeenPunch
WhiteSand

Why is Doom not in the correct place?

CodePudding user response：

#include <bits/stdc  .h>
using namespace std;

int Partition(vector<string>& userIDs, int i, int k) {
    int pivot = i;
    string pivotValue = userIDs[pivot];
    string temp;

    int leftIndex = i;
    int rightIndex = k;
    

    while(i<k) {
        while (userIDs[i].compare(pivotValue)<=0) {
            i  ;
            if(i >= rightIndex) break;
        }
        while (pivotValue.compare(userIDs[k])<=0) {;
            k--;
            if(k <= leftIndex) break;
        }

        if(i<k){
            temp = userIDs[i];
            userIDs[i] = userIDs[k];
            userIDs[k] = temp;
        }

        
    }
            // swap
    userIDs[pivot] = userIDs[k];
    userIDs[k] = pivotValue;
    
    return k;
}

void Quicksort(vector<string>& userIDs, int i, int k) {
    if (i >= k) {
        return;
    }

    int lowEndIndex = Partition(userIDs, i, k);
    Quicksort(userIDs, i, lowEndIndex - 1);
    Quicksort(userIDs, lowEndIndex   1, k);
}

int main() {
    
    vector<string> userIDs = {"BigBen", "GardenHeart", "GreyMare", "TeenPunch",
    "WhiteSand", "LifeRacer", "Doom", "AlienBrain" };

    Quicksort(userIDs, 0, userIDs.size() - 1);
    

    for(auto& c: userIDs) cout << c << " ";
    cout << endl;
    return 0;
}

Fixed the code and tested. Now it works. What were the problems?
As far as I noticed, firstly you didn't put break() statements within the while loops in case i or k exceeds the boundaries of the vector. I've changed the pivot from middle element to first element, but it's just my preference, you can implement the quicksort algorithm with your pivot in the middle, not a big deal. I've called first Quicksort() with lowEndIndex - 1 rather than lowEndIndex. I've used [] operator rather than at(), but again it's my preference. I guess the main problems were that break stuff and calling the quicksort method with lowEndIndex rather than lowEndIndex - 1.

Output:

AlienBrain BigBen Doom GardenHeart GreyMare LifeRacer TeenPunch WhiteSand