-1

I am a student completing a project right now and am making a larger version of this quick sort for objects within a vector, etc. I made this mini version to test out my quickSort algorithm, it should sort this vector of strings alphabetically (A->Z). I can't seem to get this to work:

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

int Partition1(vector<string> array, int low, int high){ //for lastName sort
    string pivot = array[high]; //pivot element
    int i = (low-1); //index of smaller element
    for(int j = low; j <= high-1; j++){ //loop from low to high
        //if current iteration is less than pivot, increment low AND swap elements at i and j
        if(array[j] < pivot){
            i++; //increment index of smaller element
            swap(array[i], array[j]);
        }
    }
    swap(array[i+1], array[high]);
    return (i+1);
}

void sort(vector<string> array, int first, int last){
    if(first < last){
        //partition array
        int pivot = Partition1(array, first, last);
        sort(array, first, pivot-1);
        sort(array, pivot+1, last);
    }
}

void swap(string &input1, string &input2) {
    string temp; //temp student object to hold info
    temp = input1;
    input1 = input2;
    input2 = temp;
}

int main(){
    vector<string> array = {"Eric", "Bob", "George", "Fred"};
    sort(array, 0, array.size()-1);
    for(int i = 0; i < array.size(); i++){
        cout << array[i] << endl;
    }
}

Instead of the desired output, it just leaves the list as is, and does not sort it alphabetically, which is what I'm aiming for (A->Z). What should I do to make it work? Is there anything I'm missing here?

rren_nn
  • 11
  • 2
    [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – Jesper Juhl Oct 23 '22 at 08:48
  • 1
    [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – Jesper Juhl Oct 23 '22 at 08:49
  • 1
    I would recommend interval indexing [low,end) - i.e. left-inclusive, right-exclusive. It makes easier to partition the intervals by avoiding +-1 issues. Which there are plenty in your code e.g. `(low-1);` will fail terribly when `low==0` which happens in the very first call. As Jesper pointed out, use a debugger to see what the code does. Also turn on compiler warnings and if possible use sanitizers. – Quimby Oct 23 '22 at 09:09

1 Answers1

0

You're taking vector<string> by value. That means, it's copied when you enter the function. Take it instead by reference: vector<string>&.

Also, I'd suggest not naming vector as array, as the latter is also a type in c++ and thus it's misleading.

lorro
  • 10,687
  • 23
  • 36