C++: How to alphabetize a vector of strings without using sorting function from algorithm library

Question

I have a vector of strings, where all of the strings have been converted to upper case so that they can be compared. I need to use for loops to alphabetize my vector. I need to alphabetize the existing vector rather than create a new one. This is my function definition:

void alpha(vector <string>& words){
    int minPos;
    int i = 0;
    for (i = 0; i < words.size(); i++) {
        minPos = i;
        for (int k = i + 1; k < words.size(); k++) {
            if (words.at(i) < words.at(k)) {
                minPos = k;
            }
        }
        }
        string temp = words.at(minPos);
        words.at(minPos) = words.at(i);
        words.at(i) = temp;
}

Here is the error that I am currently getting in main.cpp when this function is called:

libc++abi.dylib: terminating with uncaught exception of type std::out_of_range: vector

I understand that this means that I am probably trying to reach an index that is out of range, but I'm not sure where this would be, or whether I am even on the right track with this to begin with. I would appreciate any guidance.

Thanks for your question. How big is your vector? Do you use this sorting often? Because your sorting algorithm is very suboptimal. — Yaroslav Nikitenko
– Yaroslav Nikitenko, Commented Apr 17, 2020 at 7:31

paxdiablo · Accepted Answer · 2020-04-17 07:45:24Z

You are doing your swap operation after the i loop has finished, where i is now set to words.size(). Since allowable indexes are 0 through words.size() - 1 inclusive, this is generating an out-of-bounds error.

You need to move the swap operation to inside that loop:

void alpha(vector <string>& words) {
    // For each possible position in the collection.

    for (int i = 0; i < words.size(); ++i) {
        // Locate next lowest element (it should be in that position).

        int minPos = i;
        for (int k = i + 1; k < words.size(); ++k) {
            if (words.at(minPos) < words.at(k)) {
                minPos = k;
            }
        }

        // If not already there, swap it with what is there.

        if (i != minPos) {
            string temp = words.at(minPos);
            words.at(minPos) = words.at(i);
            words.at(i) = temp;
        }
    }
}

You'll also see a couple of other improvements, to wit:

minimising the scope of variables to where they should be used (had you done this with i, it would have been impossible to compile your incorrect code).
no performing an unnecessary swap operation if the correct item is already in the correct spot.
fixing a slight bug in the way you detect if a later item should override the current (basically, using minPos rather than i).
adding comments. I can't stress enough how this is almost always the thing that should be done first when coding.

As an aside, I can only assume this is classwork since no-one in their right mind^(a) would opt to use a manual method when there's something far more appropriate in the standard library:

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

And just one minor note. You use the variable minPos but your actual comparison code will sort the array from largest to smallest. So you should possibly call that maxPos, or change the comparison to the opposite sense (sorting smallest to largest by using >).

^(a) So obviously excluding teachers :-)

Thank you so much! Yes, this is classwork. It has been a rough go of it ever since we moved online and there's less help available and we don't have class as often. Sorry about not having comments. If I'm being totally honest, there are no comments because I had no idea what I was doing. Thank you for your help. It worked for my purpose and I appreciate it a lot.

molbdnilo · Accepted Answer · 2020-04-17 07:35:07Z

1

Your indentation is misleading.

This is the more conventional indentation:

void alpha(vector <string>& words){
    int minPos;
    int i = 0;
    for (i = 0; i < words.size(); i++) {
        minPos = i;
        for (int k = i + 1; k < words.size(); k++) {
            if (words.at(i) < words.at(k)) {
                minPos = k;
            }
        }
    }
    string temp = words.at(minPos);
    words.at(minPos) = words.at(i);
    words.at(i) = temp;
}

where you can see that the swap is not inside the loop, where it should be, but outside.
And after the outer loop, i is words.size().

As a side note, if you had declared i in its loop like you did with k, this would have been a compilation error and much easier to spot.

answered Apr 17, 2020 at 7:35

molbdnilo

67.1k3 gold badges46 silver badges90 bronze badges

1 Comment

HannahF Over a year ago

Thank you so much! I appreciate it. It is working now!!

Collectives™ on Stack Overflow

C++: How to alphabetize a vector of strings without using sorting function from algorithm library

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related