Thread: bubble sort not sorting numbers in order.

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    42

    bubble sort not sorting numbers in order.

    Hi,

    I was wondering if you can help me figure out why my bubble sort is not sorting the random numbers in order. My code is the following:

    Code:
    #include <iostream>
    #include <cstdlib>
    #include <ctime>
    using namespace std;
    
    typedef int intArray[];
    void generate(intArray nums, int size, int low, int high);
    void bubSort(intArray nums, int size);
    void displayNums(intArray nums, int size);
    void display(int n);
    bool notInOrder(int a, int b);
    void swap(int& a, int& b);
    
    int main()
    {
      const int MAX_SIZE = 5000; // arbitrary
      int numbers[MAX_SIZE];
      int howMany;
    
      cout << "How many numbers to sort? ";
      cin >> howMany;
    
      if(howMany > MAX_SIZE)
        {
          howMany = MAX_SIZE;
        }
    
      generate(numbers, howMany, 0, 999);
      cout << "Numbers generated..." << endl;
      displayNums(numbers, howMany);
      cout << endl;
      cout << "After sorting..." << endl;
      displayNums(numbers, howMany);
      cout << endl;
    }
    
    void generate(intArray nums, int size, int low, int high)
    {
      int n, i = 0;
      do
        {
          n = (rand() + time(0)) % 100;
          if(n >= low && n <= high)
    	{
    	  nums[i] = n;
    	  i++;
    	}
        }while (i <= size);
    }
    
    void bubSort(intArray nums, int size)
    {
      for(int k = size-2; k >= 0; k--)
        {
          for(int i = 0; i <= k; i++)
    	{
    	  if(notInOrder(nums[i],nums[i+1]))
    	    {
    	      swap(nums[i],nums[i+1]);
    	    }
    	}
        }
    }
    
    void displayNums(intArray nums, int size)
    {
      for(int s = 1; s <= size; s++)
        {
          cout.width(4);
          cout << nums[s];
          if(s != 0 && s%15 == 0)
    	{
    	  cout << endl;
    	}
        }
    }
    
    bool notInOrder(int a, int b)
    {
      return (a > b);
    }
    
    void swap(int& a, int& b)
    {
      int temp;
      temp = a;
      a = b;
      b = temp;
    }
    And the results I get are:
    Code:
    Numbers generated...
      90  45  47  83  59  42  51  44  18  81
    After sorting...
      90  45  47  83  59  42  51  44  18  81
    I have no idea why they are not being sorted correctly. I am sure the problem is there staring me in the face, but I've been trying to figure out whats wrong for a couple of hours, and have resorted to coming on here, and getting help.

    I thank you in advance if you can help me solve my problem as to why the numbers are not being sorted.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    So ... you could call your sort function, maybe, if you want things to be sorted.

  3. #3
    Registered User
    Join Date
    Nov 2008
    Posts
    42
    Quote Originally Posted by tabstop View Post
    So ... you could call your sort function, maybe, if you want things to be sorted.
    Sorry, I seem really stupid now not noticing the most important part of the program not being there!! Thanks very much.
    Last edited by rushhour; 02-19-2009 at 10:53 AM.

  4. #4
    Registered User
    Join Date
    Nov 2008
    Posts
    42
    There is one other problem though, it seems as though my program sorts the numbers out, but some just disappear such as what happens in this one:

    Code:
    How many numbers to sort? 10
    Numbers generated...
       4  59  61  97  73  56  65  58  32  95
    After sorting...
      32  56  58  59  61  65  73  84  97  95
    Why does it seem to delete a number and then replace it with a random number?

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Arrays go from 0 to n-1, despite what your displayNums may believe.

  6. #6
    Registered User
    Join Date
    Nov 2008
    Posts
    42
    Quote Originally Posted by tabstop View Post
    Arrays go from 0 to n-1, despite what your displayNums may believe.
    Ok, well I've sorted out one problem in that it now doesn't replace numbers and the output is the following:

    Code:
    How many numbers to sort? 10
    Numbers generated...
      73  93  48  50  86  62  45  54  47  21  84
    After sorting...
      21  45  47  48  50  54  62  73  86  93  84
    Now it seems that it does not sort out the last number so in the case above, 84 should be before 86 and not at the end.

    Any idea why this is happening?

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Did you notice how 11 numbers were printed? Remember, arrays go from 0 to n-1.

  8. #8
    Registered User
    Join Date
    Nov 2008
    Posts
    42
    Quote Originally Posted by tabstop View Post
    Did you notice how 11 numbers were printed? Remember, arrays go from 0 to n-1.
    Sorry but, I really am struggling to know why it is doing this. Is the problem within the bubSort code?

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by rushhour View Post
    Sorry but, I really am struggling to know why it is doing this. Is the problem within the bubSort code?
    No.
    Code:
    for(int s = 1; s <= size; s++)
    Arrays go from 0 to n-1, not 1 to n.

  10. #10
    Registered User
    Join Date
    Nov 2008
    Posts
    42
    Ok well I've changed it, but it seems to be missing a number again, which was the second problem that I was having. My output now displays:
    Code:
    How many numbers to sort? 10
    Numbers generated...
      79  34  36  72  48  31  40  33   7  70
    After sorting...
      31  33  34  36  40  48  59  70  72  79
    and the 7 is missing from the sorting. So how can this problem be corrected?
    Last edited by rushhour; 02-19-2009 at 12:15 PM.

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by rushhour View Post
    Ok well I've changed it, but it seems to be missing a number again, which was the second problem that I was having. My output now displays:
    Code:
    How many numbers to sort? 10
    Numbers generated...
      79  34  36  72  48  31  40  33   7  70
    After sorting...
      31  33  34  36  40  48  59  70  72  79
    and the 7 is missing from the sorting. So how can this problem be corrected?
    I'm guessing the problem would be corrected by printing the ten numbers in the array, and not the last nine numbers of the array plus a random number after. Remember, everything I highlighted in red is wrong, and should not be in your program. When I change your print statement to print the ten numbers in the array, and not the last nine numbers of the array plus a random number after, I get correct results.

  12. #12
    Registered User
    Join Date
    Nov 2008
    Posts
    42
    So must the for loop be changed like this?
    Code:
    for(int s = 0;  s < size; s++)
    Really sorry, but i really am struggling to find the solution to the problem at hand.
    Last edited by rushhour; 02-19-2009 at 12:48 PM.

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by rushhour View Post
    So must the for loop be changed like this?
    Code:
    for(int s = 0;  s < size; s++)
    Really sorry, but i really am struggling to find the solution to the problem at hand.
    Since that is a loop that goes from 0 to n-1, that is the correct loop.

  14. #14
    Registered User
    Join Date
    Nov 2008
    Posts
    42
    Quote Originally Posted by tabstop View Post
    Since that is a loop that goes from 0 to n-1, that is the correct loop.
    Ok, but can you tell me why it still replaces one of the numbers? e.g. the output is:
    Code:
    How many numbers to sort? 10
    Numbers generated...
      24  44  99   1  37  13  96   5  98  72
    After sorting...
       1   5  13  24  35  37  44  72  96  98
    There seems to be no number 35. Can you explain why this is the case?

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by rushhour
    There seems to be no number 35. Can you explain why this is the case?
    hmm...
    Code:
    After sorting...
       1   5  13  24  35  37  44  72  96  98
    EDIT:
    Wait, a minute, you mean to say that there is no 35 before sorting? It was rather confusing to ask "why it still replaces one of the numbers" and then mention 35. You should mention 99 instead.

    Anyway, what is your current code?
    Last edited by laserlight; 02-19-2009 at 01:08 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    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 not working... wats d prob?
    By Huskar in forum C Programming
    Replies: 8
    Last Post: 03-31-2009, 11:59 PM
  2. testing a bubble sort algorithm
    By rushhour in forum C++ Programming
    Replies: 4
    Last Post: 02-27-2009, 01:00 AM
  3. Generating a sequence of numbers in a random order
    By mirbogat in forum C Programming
    Replies: 15
    Last Post: 08-12-2008, 02:01 PM
  4. help with debug (bubble sort algorithm)
    By lbraglia in forum C Programming
    Replies: 5
    Last Post: 10-19-2007, 05:24 PM
  5. bubble sorting multiple strings
    By jibbles in forum C Programming
    Replies: 10
    Last Post: 10-11-2003, 11:48 PM