user3328381 user3328381 - 3 months ago 26
C++ Question

cin strings into a vector and quicksort them


Write a void function called string_list_sort() that reads in any number of strings (duplicates are allowed) from cin, stores them in a vector, and then sorts them. Don’t use the standard C++ sort function here — use the version of quicksort that you created.


My problem is I tried to use
strcmp()
but I got a lot of errors, so I tried this method, but I have a problem with
char val = v[end]
. I am not sure how to compare two
std::string
values.
I changed char to string and it works. Now my problem is for example v = {" apple", "car", "fox", " soap", "foz"}; the result I get is apple, soap, car, fox, foz which is not in alphabetical order

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <vector>
#include "error.h"

using namespace std;

void string_list_sort(vector<string> v){
string line;
while (getline(cin, line)){
if (line.empty()){
break;
}
v.push_back(line);
}
}

int partition(vector<string>&v, int begin, int end)
{
char val = v[end];
char temp;

int j = end;
int i = begin - 1;

while (true)
{
while (v[++i] < val)
while (v[--j] > val)
{
if (j == begin)
break;
}

if (i >= j)
break;

temp = v[i];
v[i] = v[j];
v[j] = temp;
}

temp = v[i];
v[i] = v[end];
v[end] = temp;

return i;
}

void quicksort(vector<string>& v, int begin, int end)
{
if (begin < end)
{
int p = partition(v, begin, end);
quicksort(v, begin, p - 1);
quicksort(v, p + 1, end);
}
}
void quick_sort(vector<string>& v)
{
quicksort(v, 0, v.size() - 1);
}

int main()
{
vector<string> v;
v =
{ " this is a test string,.,!"};
string word;
while (cin >> word)
{
v.push_back(word);
}
quick_sort(v);
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";

}
}

Answer

OP almost has a sorting function. Two mistakes in particular stand out:

char val = v[end];
char temp;

v is a vector<string> so v[end] will return a string.

string val = v[end];
string temp;

Takes care of that and makes the program compile and successfully sort. There is no need to go inside the strings to compare character by character. string does that work for you.

The second problem: Quicksort's partition function is supposed to look like (Looting from wikipedia here)

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo – 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot

        do
            j := j – 1
        while A[j] > pivot

        if i >= j then
            return j

        swap A[i] with A[j]

and OP's partition function has picked up a bunch of extra baggage that needs to be removed to get an optimal mark from their instructor. Take a look at the above pseudo implementation and compare it with yours. You may see the mistakes right way, but if not, stand on the shoulders of giants and translate it into C++ (hints: := is plain old = in C++, and you'll need to add some ;s and braces). Debug the result as required. I won't translate it because that would almost totally defeat the point of the assignment.

Side notes (gathering a few important comments):

When writing a test driver don't take in user input until you know the algorithm works. Start with preloaded input that is easy to visualize like

int main()
{
    vector<string> v{"C","B","A"};
    quick_sort(v);
    for (size_t i = 0; i < v.size(); i++)
    {
        cout << v[i] << " ";

    }
}

When the output is "A B C ", change the input to something more complicated, but still easy to visualize

vector<string> v{"A","C","Q","B","A"};

And when that works go nuts and feed it something nasty. I like the Major General's Song from the Pirates of Penzance.

Comments