Swap neighbouring elements in std::list

Question

I want to change places of neighbouring elements in the std::list

Example of the list and values

A B C D E F G
3 2 1 2 1 3 2

What I expect to receive after sorting:

A B D C F E G
3 2 2 1 3 1 2

So, simple A > B = nothing to do, but C < D = swap them and go to E comparison.

I have no idea about how to swap neighbor elements.

So, I want to move forward to 1 step good elements

Answer 1

You can easily do this by using two iterators:

void biswap(std::list<int> &l)
{
    if (l.size() < 2)
        return;
    auto it2 = l.begin();
    auto it1 = it2++;
    auto e = l.end();
    for (;;)
    {
        if (*it1 < *it2)
            std::swap(*it1, *it2);
        it1 = it2++;
        if (it2 == e)
            return;
        it1 = it2++;
        if (it2 == e)
            return;
    }
}

Live example

Note: in case you're not using C++11 and thus calling size() might present a significant overhead, you can replace it with this (and of course replace all usage of auto with explicit types):

void biswap(std::list<int> &l)
{
    auto it2 = l.begin();
    auto e = l.end();
    if (it2 == e)
        return;
    auto it1 = it2++;
    if (it2 == e)
        return;
    for (;;)
    // ... the rest as before
}

Answer 2

If all you want to do is a pairwise traversal and swap elements if the first one is less than the second then you can e.g. use std::adjacent_find like this:

using std::swap;
for (auto it = std::begin(l); it != std::end(l); it = std::adjacent_find(it, std::end(l), std::less<int>{})) {
    swap(*it, *std::next(it));
}

This will cause the list of numbers 3 2 1 2 1 3 2 to be arranged as:

3 2 2 1 3 2 1

But, this is not the same as your expected result 3 2 2 1 3 1 2 and I don't undestand why you do not want to swap the last pair 1 2 like the others?

If what you want is an erratic pattern for sorting then there can be no simple solution. Instead you must use special handling of individual elements.

Answer 3

In case you don't have C++11 support, simple C++03 solution using 2 iterators could be:

#include <iostream>
#include <algorithm>
#include <list>

void swapNeighbours(std::list<int>& l) {

    std::list<int>::iterator it = l.begin();
    std::list<int>::iterator prev = it++;
    while (prev != l.end() && it != l.end()) {

        // swap if needed:
        if (*prev < *it)
            std::swap(*prev, *it);

        // move 2 times forward:
        if (++it == l.end())
            break;
        prev = it++;
    }
}

Then (based on your example) if you do:

void print(const std::list<int>& l) {
    std::list<int>::const_iterator i;
    for (i = l.begin(); i != l.end(); ++i) {
        std::cout << *i << ' ';
    }
    std::cout << std::endl;
}

int main() {

    std::list<int> l;
    l.push_back(3); l.push_back(2); l.push_back(1); l.push_back(2);
    l.push_back(1); l.push_back(3); l.push_back(2);

    print(l);
    swapNeighbours(l);
    print(l);
}

then for the:

A B C D E F G
3 2 1 2 1 3 2

there will be following comparisons: A < B? (no) C < D? (yes, swaps) E < F? (yes, swaps too) yielding the output:

3 2 2 1 3 1 2 

Answer 4

This gives the desired result and it switches the comparison for "good" elements, exactly as you asked:

#include <list>
#include <iostream>

using namespace std;

template<typename Type>
void print(const list<Type> & l)
{
    for (auto element : l) cout << element << " ";
    cout << endl;
}

int main(int argc, const char *argv[])
{
    list<int> l = {3,2,1,2,1,3,2}; 

    print(l);

    auto it = l.begin(); 
    while(std::next(it) != l.end())
    {
        if (*it < *std::next(it))
        {
            std::swap(*it, *std::next(it)); 
            ++it; 
        }
        ++it; 
    } 

    print(l); 

    return 0;
}

Executing results with:

3 2 1 2 1 3 2 
3 2 2 1 3 1 2

Answer 5

You can use standard algorithm std::adjacent_find to find a pair of elements for which first < second and then swap them.

For example

#include <iostream>
#include <algorithm>
#include <list>
#include <functional>
#include <iterator>

int main()
{
   std::list<int> l = { 3, 2, 1, 2, 1, 3, 2 };

   for ( int x : l ) std::cout << x << ' ';
   std::cout << std::endl;

   auto it = std::adjacent_find( l.begin(), l.end(), std::less<int>() );

   if ( it != l.end() ) std::swap( *it, *std::next( it ) );

   for ( int x : l ) std::cout << x << ' ';
   std::cout << std::endl;
} 

The output is

3 2 1 2 1 3 2 
3 2 2 1 1 3 2 

Or if you want to process all such situations when first < second then you can use the following code

#include <iostream>
#include <algorithm>
#include <list>
#include <functional>
#include <iterator>

int main()
{
    std::list<int> l = { 3, 2, 1, 2, 1, 3, 2 };

    for ( int x : l ) std::cout << x << ' ';
    std::cout << std::endl;

    std::list<int>::iterator it = l.begin();

    while ( ( it = std::adjacent_find( it, l.end(), std::less<int>() ) ) != l.end() )
    {
        std::swap( *it, *std::next( it ) );
    }

    for ( int x : l ) std::cout << x << ' ';
    std::cout << std::endl;
} 

The output is

3 2 1 2 1 3 2 
3 2 2 1 3 2 1