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;
}

---

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

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

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..

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.

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,

---

Code:

---

          printf("nums[%d] = %d, ", inner, nums[inner]);
          printf("nums[%d] = %d, ", outer, nums[outer]);

---

You should swap these two, but very nice. ;)

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 :p Thanks so much guys, I appreciate all of your help and input!!

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!

Search the board for "bubble sort" and you sould find lots of material.

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.... ;)

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!