Thread: Can't see the bubbling in the bubble sort.

  1. #1
    Registered User
    Join Date
    Sep 2009
    Posts
    13

    Can't see the bubbling in the bubble sort.

    I'm as noobish as you get, first time using C and my first time programming. This is the 3rd program I am attempting to understand and replicate.

    I understand that bubble sorting compares two values and swaps them if the larger value is in front.

    However, with the following code, I just don't see how it happens when I try to "read" the code in plain English and write it out. I try to follow along with the numbers and do the math, but I don't get how the bubble sort is swapping anything. Can anyone explain just one full loop in English?

    I've seen other codings where a "swap" code (function?) seems to be used, but I don't see that here. This code was found here: HowStuffWorks "How C Programming Works"

    Code:
    #include <stdio.h>
    
    #define MAX 10
    
    int a[MAX];
    int rand_seed=10;
    
    /* from K&R
       - returns random number between 0 and 32767.*/
    int rand()
    {
        rand_seed = rand_seed * 1103515245 +12345;
        return (unsigned int)(rand_seed / 65536) % 32768;
    }
    
    int main()
    {
        int i,t,x,y;
    
        /* fill array */
        for (i=0; i < MAX; i++)
        {
            a[i]=rand();
            printf("%d\n",a[i]);
        }
    
        /* bubble sort the array */
    for (x=0; x < MAX-1; x++)
        for (y=0; y < MAX-x-1; y++)
            if (a[y] > a[y+1])
            {
                t=a[y];
                a[y]=a[y+1];
                a[y+1]=t;
            }
    /* print sorted array */
    printf("--------------------\n");
    for (i=0; i < MAX; i++)
    printf("%d\n",a[i]);
    
    
        return 0;
    }
    Thank you so much for even entertaining these noob questions. I will get better.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    What do you get when you try?

    (Hint: the swap is:
    Code:
            {
                t=a[y];
                a[y]=a[y+1];
                a[y+1]=t;
            }

  3. #3
    Registered User
    Join Date
    Sep 2009
    Posts
    13
    Well lets see.

    On the first loop, y is assigned to 0.

    So t gets assigned to a[0].
    Then a[0] is assigned to a[1].
    Then a[1] gets assigned to t.

    I can see, or sense rather, a circular motion there. I think it means that on the next pass, when y = 1, t will be assigned to a[1], then a[1] is assigned to a[2], and then a[2] assigned to t.

    But, I don't know what that means. How does the swap code know what the array's random values were? It looks like it's just dealing with the array's integers, not the random values for each integer.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    But, I don't know what that means. How does the swap code know what the array's random values were? It looks like it's just dealing with the array's integers, not the random values for each integer.
    Code:
     if (a[y] > a[y+1])
    That's how.


    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    That's a pretty nonsensical statement you've got there. Also you have to remember that assignment goes right to left.

    So let's make some numbers up:
    Code:
      t   a[0]  a[1]
    ----- ----- -----
      ?     8     5  
    Now a[0] gets assigned to t
      8     8     5  
    Now a[1] gets assigned to a[0]
      8     5     5
    Now t gets assigned to a[0]
      8     5     8

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    If you want to you could find an animation of bubble sort, maybe it will demonstrate the bubbliness. e.g., Sort Applet
    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.

  7. #7
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by Krash005 View Post
    But, I don't know what that means. How does the swap code know what the array's random values were? It looks like it's just dealing with the array's integers, not the random values for each integer.
    Can't make any sense of the above statement but you might be better off first reading up on it before trying to decipher its code.
    Check out the tutorial posted on this site's faq for the theory behind bubble sort.

  8. #8
    Registered User
    Join Date
    Sep 2009
    Posts
    13
    Sorry, lol. Yeah I was reading up on that very url while deciphering, trying to use it as like a translator. I watched a youtube video on bubble sorts too, before i started.

    I think I might be ok now, thanks to this forum's generous help.

    @ itBbitC & tabstop: My confusing statement was to say that, when I saw this and tabstop's very helpful example:
    Code:
      
     if (a[y] > a[y+1])
    
     t   a[0]  a[1]
    ----- ----- -----
      ?     8     5  
    Now a[0] gets assigned to t
      8     8     5  
    Now a[1] gets assigned to a[0]
      8     5     5
    Now t gets assigned to a[0]
      8     5     8
    I thought it meant "if the 0 in a[0] is bigger than the 1 in a[1]". So i was thinking "of course 1 is bigger than 1! Thats what I mean by the integer itself, rather than the value it represented. I also didn't know that assignments go right to left.

    I realize how stupid that was now, and why it was so nonsensical. Thanks for your patience though, i know this is all probably eyerollingly basic. dwks's link cleared things up even more.

  9. #9
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    The "bubbling" in bubble sort refers to the fact that the largest element is "bubbled" to the top (end) of the array.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 05-13-2009, 03:25 PM
  2. bubble sort not working... wats d prob?
    By Huskar in forum C Programming
    Replies: 8
    Last Post: 03-31-2009, 11:59 PM
  3. My bubble sort only sorts once
    By Muller in forum C Programming
    Replies: 8
    Last Post: 03-27-2009, 04:36 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