Search code examples
c++algorithmsortingbubble-sort

Bubblesort Driving me nuts

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:

The 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!

The next output

Where am i doing this wrong?

Thanks in advance!

Solution

  • 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.