CODEWITHSUNDEEP
c++vector
Will Nasby
Will Nasby

Reputation: 1148

Sorting a vector of strings by ints

I have a string of words, and they are ranked by relevance. Relevance is a float stored in a separate vector, but I have it that the positions of the two vectors correlate with each other.

float floatTemp1, floatTemp2;
string stringTemp1, stringTemp2;
for(int m=0; m<PlayList.size()-1; m++){
    for(int i=0; i<PlayList.size(); i++){
        if(storedRelevance[i+1]>storedRelevance[i]){
            floatTemp1 = storedRelevance[i];
            floatTemp2 = storedRelevance[i+1];
            storedRelevance[i]= floatTemp2;
            storedRelevance[i+1] = floatTemp1;
            stringTemp1 = relevantPlays[i];
            stringTemp2 = relevantPlays[i+2];
            relevantPlays[i]= stringTemp2;
            relevantPlays[i+1]= stringTemp1;
        }
    }
}

So basically, if the relevance of the vector in position [1] is greater than the relevance of [0], it'll swap the positions of the elements in both the relevance and string vectors. I get a segmentation fault every time I run it.

Upvotes: 1

Views: 214

Answers (5)

kfsone
kfsone

Reputation: 24269

There are several problems of various levels with your approach.

problem #1, i+1 could exceed PlayList.size().

 for ( ... i < storedRelevance.size() ... )
        if(storedRelevance[i+1]>storedRelevance[i]){

I think you have the conditions of your m and i loops the wrong way around.

problem #2, you copy both values from one place and then copy them back elsewhere, when you only need to "park" one of them:

            floatTemp1 = storedRelevance[i];
            floatTemp2 = storedRelevance[i+1];
            storedRelevance[i]= floatTemp2;
            storedRelevance[i+1] = floatTemp1;

better as

            floatTemp = storedRelevance[i];
            storedRelevance[i] = storedRelevance[i+1];
            storedRelevance[i+1] = floatTemp;

or better still

            std::swap(storedRelevance[i], storedRelevance[i+1]);

but again, i+1 could exceed PlayList.size() with your current implementatino.

BIG problem:

            stringTemp1 = relevantPlays[i];
            stringTemp2 = relevantPlays[i+2];

That +2 seems like ... the wrong string and is definitely going to exceed the array size.

            relevantPlays[i]= stringTemp2;
            relevantPlays[i+1]= stringTemp1;

I also don't understand the purpose of the outer, "m", loop, other than to make sure that the sort always costs O(N^2) complexity?

If you are simply doing this as an exercise to understand how to implement a sort, you may want to look at one of these alternate approaches:

Method 1: Use a struct/class to give the values locality (this is C++)

struct PlayListSearchResult {
    int m_relevance;
    const string& m_word; // a reference, so a short lifetime for these objects.

    PlayListSearchResult(int relevance_, const std::string& word_)
        : m_relevance(relevance_)
        , m_word(word_)
    {}
};

typedef std::vector<PlayListSearchResult> PlayListSearchResults;

// the sort:
     // given PlayListSearchResults results or &results:

     const numResults = results.size();
     bool needsRedo;
     do {
         needsRedo = false;
         for (size_t i = 0; i < numResults - 1; ++i) {
             if (!(results[i + 1].m_relevance < results[i].m_relevance))
                 continue;
             std::swap(results[i], results[i + 1]);
             needsRedo = true;
         }
     } while (needsRedo);

Method 2: Create an array of indexes:

std::vector<size_t> indexes;
for (size_t i = 0; i < results.size(); ++i) {
    indexes.push_back(i);
}

// do the sort, but instead of swapping relevance/word, just swap the index.

But otherwise, just look into std::sort or std::map

Upvotes: 0

BigTailWolf
BigTailWolf

Reputation: 1028

Your [i+1] and [i+2] index sometime calling somewhere out of your vector storage.

That's why you have segmentation fault.

A better why of doing this is using a struct to encapsulate your data

Struct Play {
    float score;
    string name;
}

And in your vector, just calling

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

std::sort is included in < algorithm>

Upvotes: 1

Loki Astari
Loki Astari

Reputation: 264739

You could keep the original arrays in their same order but have an indirection that is sorted.

std::vector<int>    sorted(PlayList.size());
for(int loop=0;loop < sorted.size();++loop) { sorted[loop] = loop;}

std::sort(sorted.begin(), sorted.end(),
           [](int lhs, int rhs){return storedRelevance[lhs]<storedRelevance[rhs]});


// Now you can access your playlist in order via the sorted vector.

// First Item
std::cout << relevantPlays[sorted[0]] << " " << storedRelevance[sorted[0]] << "\n";

Upvotes: 1

andre
andre

Reputation: 7249

use std::map<float, std::string> because the data is sorted as elements are added.

std::map<float, std::string> relevance_mapping;
std::vector<std::string> words;
std::vector<float> relevance;
//...

for(std::size_t i = 0; i < words.size(); i++) {
    relevance_mapping[relevance[i]] = words[i];
}

You can now iterate over relevance_mapping and you'll get a the data sorted by relevance.

Upvotes: 0

Mats Petersson
Mats Petersson

Reputation: 129524

I would suggest that you use a struct to store all your information about a single thing (e.g. a word, it's relevance, etc), then use std::sort with a function or functor that compares the relevance values.

Upvotes: 11

Related Questions