How do you get the array after the third swap of bubble sort algorithm?

[imastruggler]

int jumbled2[]= {5,9,50,6,1,70,0}

It's in ascending order and the answer is 9,50,6,5,1,70,0.

I don't understand why it looks like that though. How did 9 get ahead of 5?

Shouldn't it look like this?

5,9,50,6,1,70,0

1st swap -> 5,9,6,50,1,70,0
2nd swap -> 5,9,6, 1,50,70,0
3rd swap -> 5,9,6,1,50,0,70
5,9,6,1,50,0,70

[lastchance]

It is what you would get if you were sorting for DESCENDING order. Are you sure that wasn't the intention?

[gunnerfunner]

Actually lastchance this is an interesting one, i'm getting results similar to OP in an ascending order bubble-sort – the first three iterations of the inner-loop are no-op as orginal_array[0] < original_array[1] < original_array{2] but as soon as it reaches original_array[3] which is > orginal_array{2] the output is not quite what one'd expect:

#include <iostream>

int main()
{
    int jumbled2[]= {5,9,50,6,1,70,0};

    std::cout << "original array \n";
    for (size_t i = 0; i < 7; ++i)
    {
        std::cout << jumbled2[i] << " ";
    }
    std::cout << "\n\nBubble sort steps \n";

    for (size_t i = 0; i < 7; ++i)
    {
        for (size_t j = i + 1; j < 7; ++j)
        {
            if (jumbled2[j] < jumbled2[i])
            {
                int temp = jumbled2[i];
                jumbled2[i] = jumbled2[j];
                jumbled2[j] = temp;
            }
            for (size_t k = 0; k < 7; ++k)
            {
                std::cout << jumbled2[k] << " ";
            }
                std::cout << "\n";
        }
    }
}
Output
original array
5 9 50 6 1 70 0

Bubble sort steps
5 9 50 6 1 70 0
5 9 50 6 1 70 0
5 9 50 6 1 70 0
1 9 50 6 5 70 0
1 9 50 6 5 70 0
0 9 50 6 5 70 1
0 9 50 6 5 70 1
0 6 50 9 5 70 1
0 5 50 9 6 70 1
0 5 50 9 6 70 1
0 1 50 9 6 70 5
0 1 9 50 6 70 5
0 1 6 50 9 70 5
0 1 6 50 9 70 5
0 1 5 50 9 70 6
0 1 5 9 50 70 6
0 1 5 9 50 70 6
0 1 5 6 50 70 9
0 1 5 6 50 70 9
0 1 5 6 9 70 50
0 1 5 6 9 50 70

There might be some kind of compiler optimization going on here but not quite sure exactly what

[lastchance]

The original post:

int jumbled2[]= {5,9,50,6,1,70,0}
It's in ascending order and the "answer" [with which the OP disagrees] is 9,50,6,5,1,70,0.

If you sort in ASCENDING order (and I agree with the OP here):
- after 1st swap: 5,9,6,50,1,70,0
- after 2nd swap: 5,9,6,1,50,70,0
- after 3rd swap: 5,9,6,1,50,0,70

If you were to sort for DESCENDING order ("sludge sort"!):
- after 1st swap: 9,5,50,6,1,70,0
- after 2nd swap: 9,50,5,6,1,70,0
- after 3rd swap: 9,50,6,5,1,70,0

I entirely agree with the OP's analysis if these are to be sorted in ascending order . I'm just noting that the nominal answer with which he disagrees is what you would get if you were attempting to put things in descending order instead.


NOTE: I think my version of bubblesort is different from yours, @GunnerFunner, as I only compare adjacent elements. Maybe it's semantics; maybe I'm just plain wrong. For an ascending-order sort this is what I use:

#include <iostream>
#include <vector>
using namespace std;

//======================================================================

template <class T> void swp( T &a, T &b )
{
   T t = a;
   a = b;
   b = t;
}

//======================================================================

template <class T> void show( vector<T> &a, bool swapped = false )
{
   for ( int i = 0; i < a.size(); i++ ) cout << a[i] << "  ";
   if ( swapped ) cout << "SWAPPED";
   cout << endl;
}

//======================================================================

template <class T> void bubbleSort( vector<T> &a )
{
   int n = a.size();
   for ( int i = 0; i < n - 1; i++ )
   {
      bool swapped = false;
      for ( int j = 0; j < n - 1 - i; j++ )
      {
         if ( a[j+1] < a[j] )
         {
            swapped = true;
            swp( a[j], a[j+1] );
                                       show( a, true );
         }
                                       else show( a );
      }
      if ( !swapped ) break;
   }
}

//======================================================================

int main()
{
   vector<int> a = { 5, 9, 50, 6, 1, 70, 0 };
   bubbleSort( a );
}

Sort for ascending order:

5  9  50  6  1  70  0  
5  9  50  6  1  70  0  
5  9  6  50  1  70  0  SWAPPED
5  9  6  1  50  70  0  SWAPPED
5  9  6  1  50  70  0  
5  9  6  1  50  0  70  SWAPPED
5  9  6  1  50  0  70  
5  6  9  1  50  0  70  SWAPPED
5  6  1  9  50  0  70  SWAPPED
5  6  1  9  50  0  70  
5  6  1  9  0  50  70  SWAPPED
5  6  1  9  0  50  70  
5  1  6  9  0  50  70  SWAPPED
5  1  6  9  0  50  70  
5  1  6  0  9  50  70  SWAPPED
1  5  6  0  9  50  70  SWAPPED
1  5  6  0  9  50  70  
1  5  0  6  9  50  70  SWAPPED
1  5  0  6  9  50  70  
1  0  5  6  9  50  70  SWAPPED
0  1  5  6  9  50  70  SWAPPED

Sort for descending order (just change < into > in the code for now):

9  5  50  6  1  70  0  SWAPPED
9  50  5  6  1  70  0  SWAPPED
9  50  6  5  1  70  0  SWAPPED
9  50  6  5  1  70  0  
9  50  6  5  70  1  0  SWAPPED
9  50  6  5  70  1  0  
50  9  6  5  70  1  0  SWAPPED
50  9  6  5  70  1  0  
50  9  6  5  70  1  0  
50  9  6  70  5  1  0  SWAPPED
50  9  6  70  5  1  0  
50  9  6  70  5  1  0  
50  9  6  70  5  1  0  
50  9  70  6  5  1  0  SWAPPED
50  9  70  6  5  1  0  
50  9  70  6  5  1  0  
50  70  9  6  5  1  0  SWAPPED
50  70  9  6  5  1  0  
70  50  9  6  5  1  0  SWAPPED
70  50  9  6  5  1  0  
70  50  9  6  5  1  0