buble sort

salahuddin_66 · 08-30-2004, 03:38 AM

hello

could some one describe me how it works
i could not understand clearly

---------------------------------------
/* now short them using a buble sort */

for (a=1; a<count; ++a)
for (b=count-1; b>=a; --b){

/* compair adjacent elements */
if (item[b-1] > item[b]){

/* excage elements */
t= item[b-1];
item[b-1] = item[b];
item[b]=t;

---------------------------------------

Code:

 
#include <stdio.h>
#include <stdlib.h>

int main(void) 
{
int item[100];
int a, b, t;
int count;

/*read in numbers*/

printf("how many numbers?");
scanf("%d", &count);

for(a=0; a<count; a++) scanf("%d", &item[a]);


/* now short them using a buble sort */

for (a=1; a<count; ++a)
   for (b=count-1; b>=a; --b){
   
   /* compair adjacent elements */
    if (item[b-1] > item[b]){
  
  /* excage elements */
   t= item[b-1];
   item[b-1] = item[b];
   item[b]=t;
   
   }
  
   }
   
   /* desplay stored list */   
   for (t=0; t<count; t++) printf("%d\t", item[t]);
     

return 0;

}

slackie1000 · 08-30-2004, 04:28 AM

hi there,

this is not a recommended method to sort elements. I would say that it can be used until 20/30 elements without headaches. It is the most primitive N^2 method. I suggest a look into Numerical Recipes book. Try to find Heapsearch or Quicksort for this kind of task.
What this code makes is perform a check per element couple and make the exchange if they are not sorted. one by one. most of the time this is not necessary. The easiest way to understand the code is a piece of paper and a pen. Write down some 5 numbers and you get how it works.

Regards

slackie1000

usercsr · 08-30-2004, 04:36 AM

This might help in understanding:

Sorting applet

slackie1000 · 08-30-2004, 04:38 AM

Quote:

This might help in understanding:

Sorting applet

great link...

interesting..

regards

slackie1000

aluser · 08-30-2004, 11:12 AM

bubble sort is a good algorithm if you're operating on data that's nearly sorted at the start. (Because it can abort when it makes a complete pass without swapping anything.) It's also in-place and the code is small, so it could be a good choice for sorting (small) sets in hardware.

Just thought I'd muddy the waters a bit in regard to the claim that it's a poor algorithm

In general, I admit that it isn't that great.

cppkid · 08-31-2004, 04:02 AM

How bubble sort works!!!

Lets suppose you have and arry of 6 elements to sort.

3 6 2 9 1 5

and you are using bubble sort, it will be sorted as,

STEP 1:
3 6 2 9 1 5 if( item[b-1] > item[b] ) { \\swap }
So in this case the value of b is 5 so we can say if( item[4] > item[5] ) { \\swap }
Now item[4] == 1 and item[5] == 5 and the condition is false so no action will be taken and the array will remain same as it is. and the variable b is decremented to 4.

STEP 2:
3 6 2 9 1 5 if( item[b-1] > item[b] ) { \\swap }
So in this case the value of b is 5 so we can say if( item[3] > item[4] ) { \\swap }
Now item[3] == 9 and item[4] == 1 and the condition is true so action will be taken and the values are swaped and array becomes.
3 6 2 1 9 5
and the variable b is decremented to 3.

STEP 3:
3 6 2 1 9 5 if( item[b-1] > item[b] ) { \\swap }
So in this case the value of b is 5 so we can say if( item[2] > item[3] ) { \\swap }
Now item[2] == 2 and item[3] == 1 and the condition is true so action will be taken and the values are swaped and array becomes.
3 6 1 2 9 5
and the variable b is decremented to 2.

STEP 4:
3 6 1 2 9 5 if( item[b-1] > item[b] ) { \\swap }
So in this case the value of b is 5 so we can say if( item[1] > item[2] ) { \\swap }
Now item[1] == 6 and item[2] == 1 and the condition is true so action will be taken and the values are swaped and array becomes.
3 1 6 2 9 5
and the variable b is decremented to 1.

STEP 5:
3 1 6 2 9 5 if( item[b-1] > item[b] ) { \\swap }
So in this case the value of b is 5 so we can say if( item[0] > item[1] ) { \\swap }
Now item[0] == 3 and item[1] == 1 and the condition is true so action will be taken and the values are swaped and array becomes.
1 3 6 2 9 5

As the variable b ==1 and so the loop will end because the condition was b<=a and a==1. But we have a nested loop so again all these steps will be repeated but the loop will end when b==2 because now a is incremented from 1 to 2 by the outter loop.
You can observe that the after each itteration of outter loop (after all STEPS), Atleaset one element is sorted to its required place. As the element 1 was on 5th place and after these steps it comes to 1st place where it was supposed to be, and the next group of steps will bring element 2 to 2nd place and so on. So it requires maximum of N group of steps to sort the array as each group sorts atleast one element. And that thing is menaged by the outer loop.

I hope you have no problem in exchange function (swap).

Wish you all the best.

salahuddin_66 · 08-31-2004, 04:44 AM

thanx