Bubble sort isnt completely working

This is a discussion on Bubble sort isnt completely working within the C++ Programming forums, part of the General Programming Boards category; so i basically looked at some pseudo code and tried to code it but when i run it i get ...

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    106

    Bubble sort isnt completely working

    so i basically looked at some pseudo code and tried to code it but when i run it i get like one number out of order, any idea?

    Code:
    #include <iostream>
    
    using namespace std;
    
    #define NUMBER_OF_ELEMENTS 15
    
    
    int main(){
        int toSort[NUMBER_OF_ELEMENTS];
    
        cout<< "Enter the numbers:\n ";
        for (int i = 0; i < NUMBER_OF_ELEMENTS; i++){
            cout<< "\n\t";
            toSort[i] = rand();
        }
    
        bool sorting = true;
        do{
            int total = 0;
            for(int b = 0; b <= NUMBER_OF_ELEMENTS; b++){
                if(toSort[b + 1] < toSort[b]){
                    int tmp = toSort[b];
                    toSort[b] = toSort[b + 1];
                    toSort[b + 1] = tmp;
                }
                else{
                    total++;
                }
            }
            if (total >= NUMBER_OF_ELEMENTS){
                sorting = false;
            }
        } while(sorting == true);
    
        cout<<"Everything sorted:";
    
        for (int z = 0; z < NUMBER_OF_ELEMENTS; z++){
            cout<<"\n\t";
            cout<<toSort[z];
        }
    
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,648
    At a glance, this line looks suspect:
    Code:
    for(int b = 0; b <= NUMBER_OF_ELEMENTS; b++){
    In the loop, you access toSort[b + 1]. This means that if b == NUMBER_OF_ELEMENTS, you are accessing toSort out of bounds, since you will be accessing toSort[NUMBER_OF_ELEMENTS + 1], when in fact the last element of toSort that you may access is toSort[NUMBER_OF_ELEMENTS - 1].
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,548
    Except for the issues laserlight pointed out, this...
    Code:
                    int tmp = toSort[b];
                    toSort[b] = toSort[b + 1];
                    toSort[b + 1] = tmp;
    ...is equal to...
    Code:
    std::swap(toSort[b], toSort[b + 1]);
    Just pointing that out.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Worse still, you've over-running the array by TWO items!
    Subtract one AND use strictly less-than in your loop condition.

    I'm surprised you came up with the idea of counting the non-swaps rather than the simpler option of just setting a flag for the actual swaps.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    106
    Okay guys thanks for the input, I went back and edited the code, and I actually meant to ask about a function to swap memebers of any array in the op. Anyway this works, and I changed it to where it doesn't have a counter and makes sorting true again, so it will keep looping, but if i remember correctly my execution time was less when i had the counter.

    Code:
    #include <iostream>
    
    using namespace std;
    
    #define NUMBER_OF_ELEMENTS 200
    
    
    int main(){
        int toSort[NUMBER_OF_ELEMENTS];
    
        for (int i = 0; i < NUMBER_OF_ELEMENTS; i++){
            toSort[i] = rand();
        }
    
        bool sorting = true;
        do{
            sorting = false;
            int total = 0;
            for(int b = 1; b < NUMBER_OF_ELEMENTS; b++){
                if(toSort[b - 1] > toSort[b]){
                    swap(toSort[b], toSort[b - 1]);
                    sorting = true;
                }
            }
        } while(sorting == true);
    
        cout<<"Everything sorted:";
    
        for (int z = 0; z < NUMBER_OF_ELEMENTS; z++){
            cout<<"\n\t";
            cout<<toSort[z];
        }
    
    }

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    You can remove the unused variable 'total'. Otherwise that looks good now.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,648
    You should #include <algorithm> for std::swap instead of relying on it being indirectly included. Personally, I would change while (sorting == true) to while (sorting), since it is clear that sorting is a boolean flag variable.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bubble sort confusion
    By Cpt_Tangerine in forum C++ Programming
    Replies: 2
    Last Post: 07-21-2010, 10:35 AM
  2. terminate a bubble sort
    By mallyg34 in forum C++ Programming
    Replies: 1
    Last Post: 05-15-2010, 10:42 PM
  3. bubble sort help.
    By zeromx in forum C Programming
    Replies: 9
    Last Post: 10-30-2006, 06:37 AM
  4. Bubble sort
    By Lionmane in forum C Programming
    Replies: 5
    Last Post: 07-09-2005, 11:30 AM
  5. Urgent - Bubble Sort problem
    By Bada Bing in forum C Programming
    Replies: 1
    Last Post: 11-15-2001, 04:56 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21