Thread: C bubble sort?

  1. #1
    Registered User
    Join Date
    Feb 2006
    Posts
    14

    C bubble sort?

    Hey guys, I have been trying to learn c, i have this book which has an example of what is labled as a bubble sort. I am having a little trouble understand a few parts, if anyone can help clear it up it would be greatly appreciated. Ok, I understand the first part with rand, it is generating 10 random numbers between 1-100, then displaying them in a list. What gets me is the outer/ inner thing. What is outer? Is it comparing the nums side by side? Also, why is inner = outer in the 3rd for loop? Thanks so much guys! Here is the code:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int main(int argc, char *argv[])
    {
      
      int nums[10];
      int ctr, temp, outer, inner, didSwap;
    
      for (ctr=0; ctr < 10; ctr++)
      {
          nums[ctr]= (rand() % 99 + 1);
      }
      
      for (ctr=0; ctr < 10; ctr++)
      {
      printf("%d\n" , nums[ctr]);
      }
      
      for (outer=0; outer < 9; outer++)
      {
          didSwap = 0;
          
          for (inner=outer; inner < 10; inner++)
          {
              if (nums[inner] < nums[outer])
              {
                 temp = nums[inner];
                 nums[inner] = nums[outer];
                 nums[outer] = temp;
                 didSwap = 1;
              }
           }       
          
          if (didSwap == 0)
          {
             break;
          }
      }
    
      printf("\nHeres is the sorted list:\n");
      
      for (ctr=0; ctr < 10; ctr++)
      {
      printf("%d\n", nums[ctr]);               
      }
      
      system("PAUSE");	
      return 0;
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    The basic idea is
    - the outer loop examines each item in the array
    - the inner loop moves it to the correct place to be called 'sorted'

    The loops exit when you finish swapping

  3. #3
    The Richness... Richie T's Avatar
    Join Date
    Jan 2006
    Location
    Ireland
    Posts
    469
    Code:
      for (outer=0; outer < 9; outer++)
      {
          didSwap = 0;
          
          for (inner=outer; inner < 10; inner++)
          {
              if (nums[inner] < nums[outer])
              {
                 temp = nums[inner];
                 nums[inner] = nums[outer];
                 nums[outer] = temp;
                 didSwap = 1;
              }
           }       
          
          if (didSwap == 0)
          {
             break;
          }
      }
    here's what i make of it: The first loop sets a reference position
    in the array, starting at 0. Then the second loop compares this to
    all array elements after this position to see which is greater
    or smaller, and swaps them if necessary. So starting at 0,
    it seaches the array and through successive swaps it moves
    the smallest number into position 0. Then it moves to position
    1, checks all elements after that postion and the result is that
    the smallest element from elements 1 to 9 is eventually moved
    into 1. So you can see that repeating the process each postion
    at a time will sort the array. Hope that clears it up
    No No's:
    fflush (stdin); gets (); void main ();


    Goodies:
    Example of fgets (); The FAQ, C/C++ Reference


    My Gear:
    OS - Windows XP
    IDE - MS Visual C++ 2008 Express Edition


    ASCII stupid question, get a stupid ANSI

  4. #4
    Registered User
    Join Date
    Feb 2006
    Posts
    14
    Quote Originally Posted by Richie T
    here's what i make of it: The first loop sets a reference position
    in the array, starting at 0. Then the second loop compares this to
    all array elements after this position to see which is greater
    or smaller, and swaps them if necessary. So starting at 0,
    it seaches the array and through successive swaps it moves
    the smallest number into position 0. Then it moves to position
    1, checks all elements after that postion and the result is that
    the smallest element from elements 1 to 9 is eventually moved
    into 1. So you can see that repeating the process each postion
    at a time will sort the array. Hope that clears it up
    It does somewhat..sorry, I am a bit frustrated with this..
    So the outer loop has the elments? 0-9? Whats getting me is the inner = outer part..if they are on the same element or they are eqaul how can it be comparing two nums? Thanks so much, sometimes I just cant visualize it in my head..

  5. #5
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,079
    They aren't on the same element. Because the inner loop is changing while the outer loop isn't. So you get something like this with your conditional statement:

    Conditional:
    Code:
    if (arry[x] >= arry[y])
    It loops like this:
    Code:
    if (arry[0] >= arry[1])
    ...
    if (arry[0] >= arry[2])
    ...
    if (arry[0] >= arry[3])
    ......
    if (arry[1] >= arry[2])
    ...
    if (arry[1] >= arry[3])
    ......
    if (arry[8] >= arry[9])
    All the way through. Continually pushing the greatest element to the back, then cutting that element off. Then it pushes the the greatest of those elements to the back, then it cuts off that element... and so on.
    Sent from my iPadŽ

  6. #6
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by fredanthony
    sometimes I just cant visualize it in my head..
    Allow me to introduce "debugging with printf". Just sprinkle the code with output statements to help you figure out what is going on.
    Code:
      for (outer=0; outer < 9; outer++)
      {
          didSwap = 0;
          for (inner=outer; inner < 10; inner++)
          {
              printf("outer = %d, ", outer);
              printf("inner = %d, ", inner);
              printf("nums[%d] = %d, ", inner, nums[inner]);
              printf("nums[%d] = %d, ", outer, nums[outer]);
              if (nums[inner] < nums[outer])
              {
                 printf("swapping, ");
                 temp = nums[inner];
                 nums[inner] = nums[outer];
                 nums[outer] = temp;
                 didSwap = 1;
              }
              putchar('\n');
           }
    
          if (didSwap == 0)
          {
             break;
          }
      }
    Then in the middle of the normal output you would see something like this.
    Code:
    outer = 0, inner = 0, nums[0] = 32, nums[0] = 32, 
    outer = 0, inner = 1, nums[1] = 93, nums[0] = 32, 
    outer = 0, inner = 2, nums[2] = 2, nums[0] = 32, swapping, 
    outer = 0, inner = 3, nums[3] = 74, nums[0] = 2, 
    outer = 0, inner = 4, nums[4] = 89, nums[0] = 2, 
    outer = 0, inner = 5, nums[5] = 73, nums[0] = 2, 
    outer = 0, inner = 6, nums[6] = 80, nums[0] = 2, 
    outer = 0, inner = 7, nums[7] = 80, nums[0] = 2, 
    outer = 0, inner = 8, nums[8] = 41, nums[0] = 2, 
    outer = 0, inner = 9, nums[9] = 95, nums[0] = 2, 
    outer = 1, inner = 1, nums[1] = 93, nums[1] = 93, 
    outer = 1, inner = 2, nums[2] = 32, nums[1] = 93, swapping, 
    outer = 1, inner = 3, nums[3] = 74, nums[1] = 32, 
    outer = 1, inner = 4, nums[4] = 89, nums[1] = 32, 
    outer = 1, inner = 5, nums[5] = 73, nums[1] = 32, 
    outer = 1, inner = 6, nums[6] = 80, nums[1] = 32, 
    outer = 1, inner = 7, nums[7] = 80, nums[1] = 32, 
    outer = 1, inner = 8, nums[8] = 41, nums[1] = 32, 
    outer = 1, inner = 9, nums[9] = 95, nums[1] = 32, 
    outer = 2, inner = 2, nums[2] = 93, nums[2] = 93, 
    outer = 2, inner = 3, nums[3] = 74, nums[2] = 93, swapping, 
    outer = 2, inner = 4, nums[4] = 89, nums[2] = 74, 
    outer = 2, inner = 5, nums[5] = 73, nums[2] = 74, swapping, 
    outer = 2, inner = 6, nums[6] = 80, nums[2] = 73, 
    outer = 2, inner = 7, nums[7] = 80, nums[2] = 73, 
    outer = 2, inner = 8, nums[8] = 41, nums[2] = 73, swapping, 
    outer = 2, inner = 9, nums[9] = 95, nums[2] = 41, 
    outer = 3, inner = 3, nums[3] = 93, nums[3] = 93, 
    outer = 3, inner = 4, nums[4] = 89, nums[3] = 93, swapping, 
    outer = 3, inner = 5, nums[5] = 74, nums[3] = 89, swapping, 
    outer = 3, inner = 6, nums[6] = 80, nums[3] = 74, 
    outer = 3, inner = 7, nums[7] = 80, nums[3] = 74, 
    outer = 3, inner = 8, nums[8] = 73, nums[3] = 74, swapping, 
    outer = 3, inner = 9, nums[9] = 95, nums[3] = 73, 
    outer = 4, inner = 4, nums[4] = 93, nums[4] = 93, 
    outer = 4, inner = 5, nums[5] = 89, nums[4] = 93, swapping, 
    outer = 4, inner = 6, nums[6] = 80, nums[4] = 89, swapping, 
    outer = 4, inner = 7, nums[7] = 80, nums[4] = 80, 
    outer = 4, inner = 8, nums[8] = 74, nums[4] = 80, swapping, 
    outer = 4, inner = 9, nums[9] = 95, nums[4] = 74, 
    outer = 5, inner = 5, nums[5] = 93, nums[5] = 93, 
    outer = 5, inner = 6, nums[6] = 89, nums[5] = 93, swapping, 
    outer = 5, inner = 7, nums[7] = 80, nums[5] = 89, swapping, 
    outer = 5, inner = 8, nums[8] = 80, nums[5] = 80, 
    outer = 5, inner = 9, nums[9] = 95, nums[5] = 80, 
    outer = 6, inner = 6, nums[6] = 93, nums[6] = 93, 
    outer = 6, inner = 7, nums[7] = 89, nums[6] = 93, swapping, 
    outer = 6, inner = 8, nums[8] = 80, nums[6] = 89, swapping, 
    outer = 6, inner = 9, nums[9] = 95, nums[6] = 80, 
    outer = 7, inner = 7, nums[7] = 93, nums[7] = 93, 
    outer = 7, inner = 8, nums[8] = 89, nums[7] = 93, swapping, 
    outer = 7, inner = 9, nums[9] = 95, nums[7] = 89, 
    outer = 8, inner = 8, nums[8] = 93, nums[8] = 93, 
    outer = 8, inner = 9, nums[9] = 95, nums[8] = 93,
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  7. #7
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,079
    Code:
              printf("nums[%d] = %d, ", inner, nums[inner]);
              printf("nums[%d] = %d, ", outer, nums[outer]);
    You should swap these two, but very nice.
    Sent from my iPadŽ

  8. #8
    Registered User
    Join Date
    Feb 2006
    Posts
    14

    Thumbs down

    wow, that was cool stuff, I think I get it now..I have been trying to wrap my head around this for like 4 days Thanks so much guys, I appreciate all of your help and input!!
    Last edited by fredanthony; 02-13-2006 at 11:43 AM.

  9. #9
    Registered User
    Join Date
    Feb 2006
    Posts
    14
    For some reason the nested for's got me. So the outer stays on the first element while the inner goes through all ten comparing and rearranging, then if there are more to swap the outer loop increments one and then inner continues comparing... You guys have been such great help!

  10. #10
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Search the board for "bubble sort" and you sould find lots of material.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  11. #11
    Registered User
    Join Date
    Feb 2006
    Posts
    43
    You also need to seed the random otherwise you will get the same output everytime.
    Also, can anyone help explain the purpose of the didSwap variable and the clauses that come with it? Because it seems to me that whatever it does is flawed, because say the random numbers generated are 1,5,4,3,2,6,7,8,9,10. #1 is the first, and is also the smallest of all the numbers, this means it will skip over the if clause inside the inner loop, and therefore didSwap will remain as a value of 0 therefore causeing the outer loop to break, but the numbers will still be in the same order. I wasn't sure if I was reading the code right so I tried running the program over and over again to see if it would ever come out unsorted, and I was starting to think I was being stupid and missing something obvious when I got an original output of 31,41,47,98,50,87,86,50,55,67. And then a final output of the same thing, because 31 is the lowest number even though the rest of the integers aren't properly sorted.
    Unless anyone else can think of a good reason for this, then I suggest finding a better book....

  12. #12
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by CrazedBrit
    Also, can anyone help explain the purpose of the didSwap variable and the clauses that come with it?
    I thought that was the new improved bubble sort!
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

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. My bubble sort only sorts once
    By Muller in forum C Programming
    Replies: 8
    Last Post: 03-27-2009, 04:36 PM
  3. help with debug (bubble sort algorithm)
    By lbraglia in forum C Programming
    Replies: 5
    Last Post: 10-19-2007, 05:24 PM
  4. Bubble Sort... which type?
    By gflores in forum C++ Programming
    Replies: 8
    Last Post: 08-15-2004, 04:48 AM
  5. Bubble Sort, Qucik Sort
    By insomniak in forum C Programming
    Replies: 2
    Last Post: 03-15-2003, 04:54 PM