how to sort vector of a structure without C++ STL sort()

Question

I'm trying to sort a vector, which contain a structure. In this program i do't want to use any C++ Standard Template Library (STL) such as sort().

I tried this code

for (auto k = GTSlist.begin(); k != GTSlist.end(); k++)
{ 
    for (auto l = GTSlist.begin()+1; l != GTSlist.end(); l++)    
    {
        if(k->owner > l->owner)
        {
            auto tmp = k->owner;
            k->owner = l->owner;
            l->owner = tmp;
        }
    }
}

Print vector value

for (auto k = GTSlist.begin(); k != GTSlist.end(); k++) 
{
    cout << "\n print sorted vector k->owner =" << k->owner << "k->length =" << k->length ;
}

Declaration of structure

Struct Basic802154GTSspec
{
    int owner;
    int start;
    int length;
}

Declaration of structure

vector <Basic802154GTSspec> GTSlist;

Inserting value in vector

// GTSlist.end()=5,length = 1,2,3,4,5 , owner= 5,1,4,2,3 
for (auto k = GTSlist.begin(); k != GTSlist.end(); k++) {
    Basic802154GTSspec newGTSspec;
    newGTSspec.length = value shown above;
    newGTSspec.owner = value shown above;
    GTSlist.push_back(newGTSspec); 
}

Expected result

print sorted vector k->owner  k->length= 1,2; 2,4; 3,5; 4,3; 5,1

Actual result

print sorted vector k->owner  k->length= 1,1; 5,2; 2,3; 4,4; 3,5

[How to implement classic sorting algorithms using modern C++](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). You need to decide which algorithm, and then implement it. — PaulMcKenzie, Mar 25 '19 at 08:28
Note that you picked one of the worst sorting algorithms in terms of time taken, and that is the bubble sort. Imagine if you had to sort 100 items -- that is 10000 iterations. If you want to be serious about it, look at the link I have in the first comment and learn how those algorithms work in sorting data. — PaulMcKenzie, Mar 25 '19 at 08:33

Omnifarious · Answer 1 · 2019-03-25T15:31:51.577

This code is wrong:

if(k->owner > l->owner)
{
     auto tmp = k->owner;
     k->owner = l->owner;
     l->owner = tmp;
}

Do this instead:

if (k->owner > l->owner)
{
    auto tmp = *k;
    *k = *l;
    *l = tmp;
}

And, because I think auto obscures an important detail here:

if (k->owner > l->owner)
{
    Basic802154GTSspec tmp = *k;
    *k = *l;
    *l = tmp;
}

And, lastly, you should investigate using ::std::iter_swap as the other answer suggested. This is an STL convenience function and a companion to ::std::swap (which you could've also used here). The chief advantages you'd get with it is that you'd simplify your code slightly which removes chances for error, and that it would use move semantics where it could, which would be more efficient in many cases (though likely not your specific case).

If you don't know what move semantics are, don't worry about it right now. It's an intermediate to advanced C++ idea that you can skip worrying about as a beginner.

All that being said, it is foolish not to use the STL algorithms. Your sort implementation is the second worse sorting algorithm (bubble sort) I know. The only one that I know of that is worse is one that repeatedly shuffles the array until it by chance ends up in sorted order.

I'd say third worst. Second worst would be "random sort", worst would be "sleep sort". Although "sleep sort" is epic. — Laurent LA RIZZA, Mar 25 '19 at 08:41
@LaurentLARIZZA - Sleep sort? I'm going to have to look that one up. Oh! *laugh* Yes, that IS epic. Though, IMHO, it's a play on radix sort. It doesn't work on keys for which you can merely define an ordering relation but otherwise don't know anything about. :-) — Omnifarious, Mar 25 '19 at 13:31

bruno · Answer 2 · 2019-03-25T18:52:39.703

In

for (auto k = GTSlist.begin(); k != GTSlist.end(); k++)
{ 
    for (auto l = GTSlist.begin()+1; l != GTSlist.end(); l++)    
    {
        if(k->owner > l->owner)
        {
            auto tmp = k->owner;
            k->owner = l->owner;
            l->owner = tmp;
        }
    }
}

you only exchange 'owner' while you need to exchange all the struct content, and also l does not depend on k, do (I suppose you do not want to use std::swap too)

for (vector <Basic802154GTSspec>::iterator k = GTSlist.begin(); k != GTSlist.end(); k++)
{ 
    for (vector <Basic802154GTSspec>::iterator l = k+1; l != GTSlist.end(); l++)    
    {
        if(k->owner > l->owner)
        {
            auto tmp = *k;
            *k = *l
            *l = tmp;
        }
    }
}

You also have a catastrophic problem in

for (auto k = GTSlist.begin(); k != GTSlist.end(); k++) {
    Basic802154GTSspec newGTSspec;
    newGTSspec.length = value shown above;
    newGTSspec.owner = value shown above;
    GTSlist.push_back(newGTSspec); 
}

if GTSlist is not empty when you reach that for you will never stop and continuously add a new element in GTSlist

darune · Accepted Answer · 2020-12-14T10:22:00.500

You probably want to user iter_swap instead, and your function becomes extremely simpel:

template <typename ForwardIterator>
void bubble_sort( ForwardIterator first, ForwardIterator last )
{
    for ( ForwardIterator sorted = first; first != last; last = sorted )
    {
        sorted = first;
        for ( ForwardIterator current = first, prev = first; ++current != last; ++prev )
        {
            if ( *current < *prev )
            {
                std::iter_swap( current, prev );
                sorted = current;
            }
        }
    }
}

how to sort vector of a structure without C++ STL sort()

3 Answers3