BubbleSort Vector

Question

I am trying to sort a vector of objects based on one of the objects attributes. Each Object has an integer value associated with it. I am trying to use a bubblesort to sort the array by descending order but it doesn't seem to be doing anything. Here is what I have tried:

void Database::sort (vector<Play*> &vec) {
  for (int i = 0; i < (vec.size() - 1); i++) {
    if (vec.at(i)->getRelevance() < vec.at((i + 1))->getRelevance()) {
      Play *tempObj = new Play(vec.at(i));
      vec.at(i) = vec.at((i +1));
      vec.at((i + 1)) = tempObj;
    }
  }
}

getRelevance() is the attribute to sort the objects by.

@Troy The reason is probably that [it's homework time at some college near you](http://stackoverflow.com/questions/18838109/seg-fault-with-iterators-in-a-recursive-function) :) . — us2012, Sep 16 '13 at 23:06
how would i go about using std::sort using getRelevance as the key? — Ntc, Sep 16 '13 at 23:07
Use an overload of std::sort that takes a custom comparator function. Is it part of your homework that you must use a hand written sort algorithm (bubblesort)? — goji, Sep 16 '13 at 23:08
@Ntc This question is about using `sort` with custom comparators: http://stackoverflow.com/questions/1380463/sorting-a-vector-of-custom-objects — us2012, Sep 16 '13 at 23:10
See http://www.cplusplus.com/reference/algorithm/sort/ then. — goji, Sep 16 '13 at 23:10
@Ntc: Oh, and in the future, please never ever ever allocate new objects when you can just swap their pointers! — yzt, Sep 16 '13 at 23:22
@Ntc: And at the same time as allocating unnecessary memory, you are overwriting the pointers to your old objects, which very likely results in a lot of memory leaks (unless you are holding on to all `Play` objects ever created and delete them somewhere.) — yzt, Sep 16 '13 at 23:33
im not using the above method anymore but, out of curiosity, what if i deleted it at the end of that method? — Ntc, Sep 16 '13 at 23:41
There's no reason to use `new` or `delete` in this code. If you want to swap two vector elements simply say `std::swap(vec.at(i), vec.at(i+1));` — Blastfurnace, Sep 17 '13 at 01:48

yzt · Accepted Answer · 2013-09-17T09:31:35.750

One of the problems with your code is that it only contains one loop! If you want to do bubble sort, you need two nested loops. For example, this would probably work:

void Database::sort (vector<Play*> &vec) {
    bool have_swapped = true;
    for (unsigned j = 1; have_swapped && j < vec.size(); ++j) {
        have_swapped = false;
        for (unsigned i = 0; i < vec.size() - j; ++i) {
            if (vec[i]->getRelevance() < vec[i + 1]->getRelevance()) {
                have_swapped = true;
                Play * tempObj = vec[i];  // Just use:
                vec[i] = vec[i + 1];      //    std::swap(vec[i], vec[i + 1]);
                vec[i + 1] = tempObj;     // instead of these three lines.
            }
        }
    }
}

You see the outer loop? It has two uses. One, it actually ensures that we are combing through the vector while there are still elements out of order (called inversions in algorithm textbooks, I believe,) and two, it lets us not go through and pointlessly check the elements that have "bubbled up" to the end of the vector as a result of previous inner loop iterations.

But bubble sort is not a good algorithm (unless you are sure your input data are almost sorted, in which case bubble sort can be very efficient.) Instead, you can do something like this:

std::sort (vec.begin(), vec.end(),
    [](Play * a, Play * b){return b->getRelevance() < a->getRelevance();}
);

And that's pretty much it.

Some notes:

You have to include <algorithm>.
That thing as the third parameter of the function is called a "lambda". Lambdas are basically functions with no names that you can just write in the middle of your code and pass around. I suggest you read up on them, since they are an important concept in computing and programming (independent of language you use.)
Since you want the items sorted in descending order of relevance and std::sort sorts ascendingly(?) by default, the lambda returns true when b's relevance is less than a's.
Using the standard sort algorithm, in addition to being shorter and sweeter than your hand-rolled code, and a lot more likely to be correct, means that you get very good performance generally (both algorithmic Big-O performance and implementation-wise.) It will certainly be much better that bubble sort (in the general case.)

Even now, my hand is twitching to go back and change the lambda to accept `Play * const &`! — yzt, Sep 16 '13 at 23:38
Thank you. I ended up using a struct comparator. Just out of curiosity, what else are lambdas used for? — Ntc, Sep 16 '13 at 23:51
also, why didn't my code work? Why wasn't it sorting it. Seems to me like it should, following traditional bubble sort. — Ntc, Sep 16 '13 at 23:55
I added a whole new section at the top of my answer about how to fix your original code. About lambdas, it's too much to go into here. Just Google it or read a book. — yzt, Sep 17 '13 at 09:36

BubbleSort Vector

1 Answers1