CODEWITHSUNDEEP
c++
Mubashir Mazhar
Mubashir Mazhar

Reputation: 27

Bubble sort: Why it isn't working correctly?

When I type 1, 2, 3, 4, 5 as input. The output is fine as it's already sorted from lowest to high. But when I type 5, 4, 3, 2, 1 it's outputting:

4, 3, 2, 1, 5

I am trying to do bubble sort by the way.

   main() {
        int a[5], i, smallest, temp;
        cout << "Enter 5 numbers: " << endl;
        for ( i = 0; i <= 4; i++ ) {
            cin >> a[i];
        }

        for ( i = 0; i <= 4; i++ ) {
            smallest = a[i];
            if ( smallest > a[i+1] ) {
                temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
        }
        cout << endl << endl;

        for ( i = 0; i <= 4; i++ ) {
            cout << a[i] << endl;
        }
        system("pause");
    }

I did change my code to this after your helpful replies:

for ( i = 0; i <=4; i++ ) {
    smallest = a[i];
    for ( j = 1; j <= 4; j++ ) {
        if ( smallest > a[j] ) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
}

I don't know why it's not working. I am really sorry as I am a noob in programming so please bear with me I'm just starting out :)

Any help will be highly appreciated.

Thanks ^.^

Upvotes: 1

Views: 87

Answers (2)

Honza Dejdar
Honza Dejdar

Reputation: 957

Because all your algorithm does, is to move the largest number to the end of the array. As bubble sort has time complexity O(n²), it's necessary to use two nested cycles. You can just repeat the cycle you wrote until the array is sorted. Note that this is not very efficient, but it should work.

You should also check that you would not access indices that are out of bounds of the array.

Upvotes: 1

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186668

Single pass is not enough, you have to scan the array over and over until no swap performed:

 bool sorted = false;

 while (!sorted) {
   sorted = true;   

   for ( i = 0; i <= 4 - 1; i++ ) { /* notice 4 - 1 since we address a[i + 1] */
        smallest = a[i];

        if ( smallest > a[i+1] ) {
            temp = a[i];
            a[i] = a[i+1];
            a[i+1] = temp;

            sorted = false;
        }
    } 
 }

Upvotes: 6

Related Questions