Quicksort String Vector Alphabetically

Question

I was having trouble with my code. I pass in an array of strings (names) and I want to do a quick sort and sort them alphabetically. Then, what I would like to do is with my array of years and ages, is swap those values respectively with the values swapped in my names array. However, I'm having trouble trying to implement that.

In the main function, I pass in:

quicksort(names, names[0], names[names.size() - 1]);

And in that code contains

void quicksort(vector<string> &names, string min, string max){
cout << "\n\tSorting names...\n";

int             temp = 0, 
                i = 0;

string          lowMin = max,
                lowMax = min,
                highMin = max,
                highMax = min,
                pivot;

vector<string>  below, 
                above;

if (min != max){

    pivot = (max[i] + min[i]) / 2;

    while (temp < names.size()){
        if (names[temp] <= pivot){
            if (lowMax.compare(names[temp]) < 0){
                lowMax = names[temp];
            }

            if (lowMin.compare(names[temp]) > 0){
                lowMin = names[temp];
            }

            below.push_back(names[temp]);

        }
        else {
            if (highMax.compare(names[temp]) < 0){
                highMax = names[temp];
            }

            if (highMin.compare(names[temp]) > 0){
                highMin = names[temp];
            }

            above.push_back(names[temp]);
        }
        temp++;
    }

    if ((below.size() > 1) && (names.size() != below.size())){
        quicksort(below, lowMin, lowMax);
    }
    if ((above.size() > 1) && (names.size() != above.size())){
        quicksort(above, highMin, highMax);
    }
    for (size_t i = 0; i < below.size(); i++){
        names[i] = below[i];
    }
    for (size_t i = below.size(); i < names.size(); i++){
        names[i] = above[i - below.size()];
    }

    }

} // // End quicksort()

In this case, would it be better to make a swap function and send in two integers so I can swap values in my other vector arrays? For example, I was thinking swapValue(int i, int j){ /* do something */} Also, can someone explain to me the difference between foobar[i].swap(foobar[j]) and swap(foobar[i], foobar[j])? Are these methods more efficient than say creating a temp variable and swapping values?

If you would put all three related values in a struct/class and make a vector of objects, a simple std::sort call would be enough, instead of writing the whole algorithm... — deviantfan, Nov 28 '15 at 01:46
Even if you wanted to implement quicksort, you can use other STL algorithm functions to do so -- http://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c — PaulMcKenzie, Nov 28 '15 at 02:21

score 5 · Accepted Answer · edited May 23 '17 at 11:59

Don't implement quicksort if you do it only because you need some sorting algorithm to use.

You seem to have three std::vector for name, age and year, where elements at the same position are related. Why not combine everything?

struct Person //or some name
{
    std::string name;
    int age;
    int year;

    int operator<(const Person &other) //comparison
    {
        return name.compare(other.name);
    }
};

Of course, you could make a full class with the Big5 etc. too, if you want.

Now, with a vector<Person> v;, you can use std::sort:

std::sort(v.begin(), v.end());

That's all.

...If you still want to have a quicksort function, take eg. this, and change the lines with the swaps so that swaps are made on all three vectors.

About your other question:

The swap of std::string and the independent function swap with string paramters do the same thing (technically they don't have to, they are completely independent, but they do).

And why swap(a,b) is better than c=a;a=b;b=c;:
In the second code, values are copied three times. For std::string, this means three times allocating new memory and copying the whole content. Swap can do it without any content copy (it can access the internal pointers etc. and exchange only these).

Quicksort String Vector Alphabetically

1 Answers1