Bubblesort Driving me nuts

Question

This is pretty straightforward question. I checked online with the bubble sort code, and it looks like i am doing the same. Here's my complete C++ code with templates. But the output is kinda weird!

#include <iostream>

using namespace std;

template <class T>
void sort(T a[], int size){
    for(int i=0; i<size; i++){
        for(int j=0; j<i-1; j++){
            if(a[j+1]>a[j]){
                cout<<"Yes at j="<<j<<endl;
                T temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}

int main(){
    int a[] = {1,2,6,3,4,9,8,10};
    sort<int>(a,8);
    for(int i = 0; i<8; i++){
        cout<<a[i]<<endl;
    }
    return 0;
}

Output:

But when i slightly change the logic to try to sort it on ascending order. i.e., changing to : if(a[j+1]<a[j]) , The output is fine!

Where am i doing this wrong?

Thanks in advance!

Answer 1

When using bubble sort, you need to keep in mind in which directions your "bubbles" move. You first have to pick the biggest/smallest element from all the array and move it to the end at position n-1. Then pick the next one and move it to to position n.

  for (int i=size; i>1; i=i-1) { // << this is different
    for (int j=0; j<i-1; j=j+1) {
      if (a[j] < a[j+1]) {
        std::swap(a[j], a[j+1]);
      }
    }
  }

See here for an even better implementation.

Answer 2

The problem with your code is that you try to bubble stuff down, but loop upward. If you want to bubble stuff down, you need to loop downward so an element that needs to go down goes down as far as it needs to. Otherwise, with every iteration of i you only know that an element may be bubbled down one space.

Similarly, if you bubble things upwards, you also need to loop upwards.

If you want to see what happens, here's your code with some output statements so you can follow what's going on:

#include <iostream>

using namespace std;

template <class T>
void sort(T a[], int size){
    for(int i=0; i<size; i++){
        cout << "i: " << i << endl;
        for(int j=0; j<i-1; j++){
            if(a[j+1]>a[j]){
                cout << "\t Yes at j = " << j << endl;
                T temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;

                for(int k = 0; k < size; k++) {
                    cout << "\t a[" << k << "]: " << a[k] << endl;
                }

                cout << endl;
            }
        }

        cout << "\n" << endl;
    }
}

int main(){
    int a[] = {1,2,6,3,4,9,8,10};

    cout << "initially:" << endl;
    for(int k = 0; k < 8; k++) {
        cout << "a[" << k << "]: " << a[k] << endl;
    }

    cout << "\n" << endl;

    sort<int>(a,8);
    cout << "\n sorted:" << endl;
    for(int i = 0; i<8; i++){
        cout << a[i] << endl;
    }
    return 0;
}

If you run this, you can see that for entries with higher index, there aren't enough iterations left to bubble them down all the way to where they need to go.

Also, here's code with your bubbling-down fixed (i.e. sorting in reverse order):

#include <iostream>

using namespace std;

template <class T>
void sort(T a[], int size){
    for(int i=0; i<size; i++){
        cout << "i: " << i << endl;
        for(int j=size - 1; j>i; j--){
            if(a[j-1]<a[j]){
                cout << "\t Yes at j = " << j << endl;
                T temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp;
            }
        }
    }
}

int main(){
    int a[] = {1,2,3,4,5,6,8,10};
    sort<int>(a,8);
    cout << "\n sorted:" << endl;
    for(int i = 0; i<8; i++){
        cout << a[i] << endl;
    }
    return 0;
}

Answer 3

It is a logic problem:

for(int i = 0; i < size; i++){
    for(int j = 0; j < (i); j++){
        if(a[i] > a[j]){
            cout<<"Yes at j="<<j<<endl;
            T temp = a[j];
            a[j] = a[i];
            a[i] = temp;
        }
    }
}

You should change the a[j+1] for a[i]

Answer 4

You are comparing and swapping wrong numbers, look for differences here:

template <class T>       
void sort(T a[], int size){
   for(int i = 0; i < size; i++){
       for(int j = i+1; j < size; j++){
               if(a[i] < a[j]){                                                                                                                                                                                 
                  cout << "Yes at j=" << j << endl;
                  //swap(a[j], a[j+1]);
                  T temp = a[j];
                  a[j] = a[i];
                  a[i] = temp;
          }            
      }                
  }                    
}