Bubble and Selection Sorting Problem

[SHENGTON]

Hello, good evening. :)

I got some problems with the "Bubble Sort" and "Selection Sort". My "Insertion Sort" is already ok. I just can't figure it out with this problem. Hope you can help me with this and explain it to me my mistakes.

Here's the whole code:

#include<stdio.h>
#include<conio.h>
void bubble(void);
void insert(void);
void select(void);
int main()
{
 int cho, i;
 do{
  printf("\n\n\n[1] Bubble Sorting\n");
  printf("[2] Insertion Sorting\n");
  printf("[3] Selection Sorting\n");
  printf("[4] Exit\n\n");
  printf("Enter your choice:");
  scanf("%d",&cho);
  i = getchar();
  if(cho==1)
  {
   bubble();
  }
  if(cho==2)
  {
   insert();
  }
  if(cho==3)
  {
   select();
  }
 }while(cho != 4);
  printf("\n\n\t\t\t    press enter when ready");
  i = getchar();
  ++i;
  clrscr();
  return 0;
}

void bubble(void)
{
 int a[100],n,i,j,t,k;
 clrscr();
 printf("Enter integer value for total no.s of elements to be sorted:");
 scanf("%3d",&n);
 printf("\n\n");
 for(i=0;i<=n-1;i++)
 {
  printf(" Enter integer value for element no.%d : ",i+1);
  scanf("%3d",&a[i]);
 }
 printf("\n\n Finally sorted array is  :");
 for(i=0;i<=n-1;i++)
 {
  printf("%3d",a[i]);
 }
 for(i=0;i<n;i++)
 {
  for(j=0;j<n-1;j++)
  {
   if(a[j]>a[j+1])
   {
    t=a[j+1];
    a[j+1]=a[j];
    a[j]=t;
   }
   a[j]=t;
   printf("\n The array after pass no.%d:",i);
   for(k=0;k<=n-1;k++)
   {
    printf("%3d",a[k]);
   }
  }
 }
}

void insert(void)
{
 int a[100],n,i,j,t,k;
 clrscr();
 printf("Enter an integer value for total no.s of elements to be sorted: ");
 scanf("%3d",&n);
 printf("\n\n");
 for(i=0;i<=n-1;i++)
 {
  printf(" Enter an integer value for element no.%d: ",i+1);
  scanf("%3d",&a[i]);
 }
 printf("\n\n Finally sorted array is  : ");
 for(i=0;i<=n-1;i++)
 {
  printf("%3d",a[i]);
 }
 for(i=1;i<=n-1;i++)
 {
  j=i;
  t=a[i];
  while(a[j-1]>t && j>0)
  {
   a[j]=a[j-1];
   j=j-1;
  }
  a[j]=t;
  printf("\n The array after pass no.%d: ",i);
  for(k=0;k<=n-1;k++)
  {
   printf("%3d",a[k]);
  }
 }
}

void select(void)
{
 int a[100],n,i,j,k,t;
 clrscr();
 printf("Enter an integer value for total no.s of elements to be sorted: ");
 scanf("%3d",&n);
 printf("\n\n");
 for(i=0;i<=n-1;i++)
 {
  printf(" Enter an integer value for element no.%d: ",i+1);
  scanf("%3d",&a[i]);
 }
 printf("\n\n Finally sorted array is  : ");
 for(i=0;i<=n-1;i++)
 {
  printf("%3d",a[i]);
 }
 for(i=0;i<n-1;i++)
 {
  for(j=i-1;j>n;j++)
  {
   if(a[i]<t)
   {
	t=a[i];
	a[i]=a[j];
    a[i]=t;
   }
  }
  a[i]=t;
  printf("\n The array after pass no.%d: ",i);
  for(k=0;k<=n-1;k++)
  {
   printf("%3d",a[k]);
  }
 }
}

[Adak]

This is Selection sort:

for(i=0;i<n-1;i++)  //OK
{
  for(j=i-1;j>n;j++)  //j=i+1
  {
    if(a[i]<t) //if(a[i] > a[j]
    {
      t=a[i];
      a[i]=a[j];
      a[i]=t;
    }
  }
  a[i]=t;  //delete this line entirely
}

j=i+i is because i<n-1, see? There's always room for j one more than i.

Selection sort is a good sort to memorize, btw. Slightly faster than Bubble sort, and easy to commit to memory, as well.

Check with Wikipedia on your Bubble sort - I never memorized that sort.

[Adak]

I didn't mention this, and should have - seems quite obvious, but still:

//j can never be > or == to n. That would be an error, so:

for(j = i + 1; j [B]<[/B] n; j++) //is correct, not j > n

[abhimanipal]

The pseudo code for bubble sort is

for i=0 to i<n
{
    for j=0 to j<n-1
    {
        if a[j] > a[i]
           then swap
    }
} 

Check out the wiki link for bubble sort to get a more detailed explanation.

[SHENGTON]

Hello Adak and abhimanipal, good day. :)

Thanks for replying Sirs.

I already figured it out about the Bubble Sorting. But the problem is, it will only display the final sorted numbers. I attached some screenshots of Bubble and Insertion sorting. I want to display the output of Bubble sorting like Insertion sorting(please take a look below). How will I gonna do that?

Hope you can help me with this.

Just forget my first code above. Here's my latest edited code:

#include<stdio.h>
#include<conio.h>
void bubble(void);
void insert(void);
void select(void);
int main()
{
 int cho, i;
 do{
  printf("\n\n\n[1] Bubble Sorting\n");
  printf("[2] Insertion Sorting\n");
  printf("[3] Selection Sorting\n");
  printf("[4] Exit\n\n");
  printf("Enter your choice:");
  scanf("%d",&cho);
  i = getchar();
  if(cho==1)
  {
   bubble();
  }
  if(cho==2)
  {
   insert();
  }
  if(cho==3)
  {
   select();
  }
 }while(cho != 4);
  printf("\n\n\t\t\t    press enter when ready");
  i = getchar();
  ++i;
  clrscr();
  return 0;
}

void bubble(void)
{
 int a[100],n,i,j,t,k;
 clrscr();
 printf("\n\n Enter integer for total numbers to be sorted: ");
 scanf("%d",&n);
 printf("\n\n");
 for( i=0;i<=n-1;i++)
 {
  printf(" Enter integer for no.%d : ",i+1);
  scanf("%d",&a[i]);
 }
 for(i=n-2;i>=0;i--)
 {
  for(j=0;j<=i;j++)
  {
   if(a[j]>a[j+1])
   {
    t=a[j];
    a[j]=a[j+1];
    a[j+1]=t;
   }
  }
 } 
 printf("\n\n Finally sorted array is: ");
 for(i=0;i<=n-1;i++)
 {
 printf("%3d",a[i]);
 }
}

void insert(void)
{
 int a[100],n,i,j,t,k;
 clrscr();
 printf("Enter integer for total numbers to be sorted: ");
 scanf("%3d",&n);
 printf("\n\n");
 for(i=0;i<=n-1;i++)
 {
  printf(" Enter integer for no.%d: ",i+1);
  scanf("%3d",&a[i]);
 }
 printf("\n\n Pass no.0: ");
 for(i=0;i<=n-1;i++)
 {
  printf("%3d",a[i]);
 }
 for(i=1;i<=n-1;i++)
 {
  j=i;
  t=a[i];
  while(a[j-1]>t && j>0)
  {
   a[j]=a[j-1];
   j=j-1;
  }
  a[j]=t;
  printf("\n Pass no.%d: ",i);
  for(k=0;k<=n-1;k++)
  {
   printf("%3d",a[k]);
  }
 }
}

void select(void)
{
 int a[100],n,i,j,k,t;
 clrscr();
 printf("Enter integer for total numbers to be sorted: ");
 scanf("%3d",&n);
 printf("\n\n");
 for(i=0;i<=n-1;i++)
 {
  printf(" Enter integer for no.%d: ",i+1);
  scanf("%3d",&a[i]);
 }
 printf("\n\n Pass no.0: ");
 for(i=0;i<=n-1;i++)
 {
  printf("%3d",a[i]);
 }
 for(i=0;i<n-1;i++)
 {
  for(j=i+1;j<n;j++)
  {
   if(a[i]>a[j])
   {
    t=a[j];
    a[j]=a[i];
    a[i]=t;
   }
  }
  printf("\n Pass no.%d: ",i);
  for(k=0;k<=n-1;k++)
  {
   printf("%3d",a[k]);
  }
 }
}

[Adak]

Just print out the numbers at the end of the first for loop, in the select function. That will show the status at the end of each pass, for Selection sort.

Your Bubble sort is wrong, however. Bubble sort is distinguished by always comparing two elements of the array, that are next to each other. Your so called Bubble sort, doesn't do that.

That's the difference between Bubble Sort and Selection Sort - In Bubble Sort, the numbers can never be moved more than 1 element. In Selection Sort, they can, although most of the logic, is the same as Bubble Sort.

So your Bubble Sort just ain't a bubbling, yet! ;)