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.

What do you get when you try?

(Hint: the swap is:

Code:

---

        {
            t=a[y];
            a[y]=a[y+1];
            a[y+1]=t;
        }

---

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.

Quote:

---

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.

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

---

If you want to you could find an animation of bubble sort, maybe it will demonstrate the bubbliness. :) e.g., Sort Applet

Quote:

---

Originally Posted by Krash005

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.

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.

The "bubbling" in bubble sort refers to the fact that the largest element is "bubbled" to the top (end) of the array.