Here is the code for Insertion Sort, Bubble Sort and Selection Sort

Insertion Sort

#include <stdio.h>
main()
{
int i,j,key;
int a[5]={5,2,3,4,1};
for(i=1;i<5;i++)
{
	key=a[i];
	while(i>0 && a[i-1]>key) {
		j=a[i];
		a[i]=a[i-1];
	   a[i-1]=j;
	   --i;
	}	
}
int k;
for(k=0;k<5;k++)
{printf("%d	", a[k]);}
printf("\n");
	}

Bubble Sort

#include <stdio.h>
main()
{
int i,j,x;
int a[5]={5,2,3,4,1};
for(i=0;i<5;i++) {
	for(j=i+1;j<5;j++) {
		if(a[i]>a[j]) {
			x=a[i];
			a[i]=a[j];
			a[j]=x;
			
	}
}
}
int k;
for(k=0;k<5;k++) {printf("%d	",a[k]);} printf("\n");
}

Selection Sort

#include <stdio.h>
main()
{
int i,j,x,min,k;
int a[5]={5,3,2,4,1};
for(i=0;i<5;i++) {
	min=i;
	for(j=i+1;j<5;j++) {
		if(a[min]>a[j]) {
			min=j;
	}
	x=a[min];
	a[min]=a[j];
	a[j]=x;
}	}
for(k=0;k<5;k++) {printf("%d ",a[k]);}
	printf("\n");
}

*****************************************************************************************

The above codes are only for array with 5 elements in it. It will also work for "n "elements. Check it out for "n" elements.

Copyrights@Anil Kumar

The bubble sort doesn't "bubble". ;)

Bubble sort compares only adjacent values in an array. What you have labeled Bubble sort, is actually Substitution sort, which is in the same class, but compares non-adjacent array values, 95% of the time (or so).

Also, Bubble sort usually has (and always should have), a sorted = 0 and sorted = 1 flag, so it knows when it can stop sorting early, because the array is now sorted. This is really useful on data that is either already sorted, or almost in sorted order.

This is Bubble sort:

void bubbleSort(int a[], int hi) {   
   int i, n, temp, swapped;
   n = hi;
   do {
      swapped = 0;
      for(i =0; i < n-1; i++) {  
         if(a[i] > a[i + 1 ]) {
            temp = a[i];
            a[i] = a[i + 1];
            a[i + 1] = temp; 
            swapped = 1;
         }
      } //end for
      --n;
   }while(swapped);
}

The Insertion sort is a bit different than what I'm used to seeing, (assigning the j value inside the while loop? J should be an index only, imo). Generally, adding a line of code into the inner nested loop of a sorting code, is sure to slow it down. Without testing it, I can't say that is the case here.

I'll test this one out, and report back.

This is the Insertion sort code that I'm used to:

void insertionSort(int a[], int lo, int hi) {
   int i, j, val; 
   for(i=lo+1;i<hi;i++) {  
      val = a[i];
      j = i-1;
      while(a[j] > val) {
         a[j + 1] = a[j];
         --j;
         if(j<0) break;
      }   
      a[j+1] = val;
   }
}

Edited 5 Years Ago by Adak: n/a

I tried the OP's Insertion sort on 10 and on 50,000 random integers,and it wouldn't sort either list, correctly.

BUBBLE SORT
Algorithm written for bubble sort is completely different. In bubble sort the largest number is in the last position(in case of arranging it in ascending order).,for the first loop j will compare till last and for second i loop j have to compare one loop less because last element need not to be compared as its the largest.
and in bubble sort comparision is between j element.
here's the algorithm:-

for(i=0;i<n-1;i++)
{
     for(j=0;j<n-1-i;j++)
     {
        if(arr[j]>arr[j+1])
            swap(arr[j],arr[j+1]);
     }
}

INSERTION SORT
The insertion sort inserts each elements in proper place same like playing cards, in which we place the cards in proper place.
in pass i comparision , ith element is compared from (i-1)th to 0th element and placed in proper position according to ascending value.
algorithm is:--

for(i=0;i<n;i++)
{
     value=arr[i];
     for(j=i-1;j>=0&& value<arr[j];j--)
          arr[j+1]=arr[j];
     arr[j+1]=value;
}

Your version of Bubble sort has poorer run times, because it does not have the "sorted" flag, and does not decrement n after each pass. That means it won't stop early when the list is already in sorted order, and it keeps working in both the inner and the outer loops, to an n index that it doesn't need to go to.

Your version of Insertion sort ran 0.75 seconds slower, sorting 50k random integers, on average. I believe that is because compilers can't optimize more complex lines of code, as well as they can simpler lines of code. Even if there are more of those simple lines of code, they're faster in this case.

Edited 5 Years Ago by Adak: n/a

RE-BUBBLE SORT
Ummm...Adak Please check the code again and guide me if the code needs more improvement.

for(i=0;i<n-1;i++)
{
     FLAG=0;
     for(j=0;j<n-1-i;j++)
     {
        if(arr[j]>arr[j+1])
            swap(arr[j],arr[j+1]);
     }
     if(FLAG==0) break;
}

INSERTION SORT
Wow...How do you calculate the exact time complexity of my code. Please guide me in this with some examples.
Thanks Adak.. :)

I missed a part of incrementing FLAG in my bubble sort code..
RE-BUBBLE SORT

for(i=0;i<n-1;i++)
{
     FLAG=0;
     for(j=0;j<n-1-i;j++)
     {
        if(arr[j]>arr[j+1])
        {
            swap(arr[j],arr[j+1]);
            FLAG++;
        }
     }
     if(FLAG==0) break;
}

RE-BUBBLE SORT

When FLAG evaluates to false (0), the sort will end

int n = hi - 1; //n is one less than our highest valid index
for(FLAG=1;FLAG;;) //or FLAG > 0. i isn't needed
{
     FLAG=0;
     for(j=0;j<n;j++)  //no more n-1!
     {
        if(arr[j]>arr[j+1])
        {
            swap(arr[j],arr[j+1]);
            FLAG++;
        }
     }
     --n; //decrement n after each inner loop finishes - very fast!
     //no break statement needed now
}

That should definitely speed it up a bit. This is the best design for a Bubble sort, that I know of. Insertion sort is really the way to go for small set sorting, (< 200 or so), if run-time is an issue with the program.

I don't test the time complexity of the programs, I pasted your code into a testing program, and ran it several times. Take an average run from that.

I strongly recommend that you make such a testing program for yourself, and gradually add sorting algorithms to it, each one in it's own function, and reloading it's own data (not being timed for that part, of course).

For a programmer, this is like the Jedi knight making his Lightsaber, imo. Hint: I use clock() with two clock_t data types (I call them start and stop), to do the actual timing. Newer chipsets from Intel especially, have a more accurate timer, but this is good enough for me).

Edited 5 Years Ago by Adak: n/a

Thanks Adak..:)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
    clock_t start,end;
    double timeused;
    int a,b,i;
    start=clock();
    scanf("%d %d",&a,&b);
    for(i=a;i<=b;i++);printf("%d",b);
    end=clock();
      printf("\n\n%d",(end-start));
        system("pause");
    return (EXIT_SUCCESS);

}

Here I ve written a code which checks the time count.
on entering a=1 and b=100.
end-start is somtimes giving 1912 and when I compile the same program with same input giving end-start=1134.
Variation in such a big range..:-O
Is the time outputting in nanosecond..???

for(FLAG=1;FLAG;;)

Is there some typing error with some extra semicolons or this is also a type of using for loop.

Variation in such a big range..

Variation is expected. A better test would take the mean and standard deviation of multiple runs.

Is the time outputting in nanosecond..???

The result is clock ticks, for whatever your implementation decides that to be. While still non-portable, a better method is like so:

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

int main(void)
{
    int a, b;

    printf("Enter a range: ");
    fflush(stdout);
    
    if (scanf("%d%d", &a, &b) == 2) {
        clock_t start;
        int i;
        
        if (a > b) {
            int save = a;
            a = b;
            b = save;
        }
        
        start = clock();
        
        for (i = a; i <= b; i++)
            ;
            
        printf("Elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);
    }

    return 0;
}

The idea is to take the difference in ticks and divide by the standard CLOCKS_PER_SEC macro to get sub-second precision.

Is there some typing error with some extra semicolons or this is also a type of using for loop.

In a for loop, all of the clauses are optional, but the semicolons separating the clauses are not. For example, this is an infinite loop with no initialization or update:

for ( ; ; ) {
    /* ... */
}

Thank you Narue.. :)

But I see You have done some little changing in code posted by me.
clock() has called after scanf() I also did same thing but it was giving output 0 for 1 to 100 input now I understand why it was so and another CLOCKS_PER_SEC as though I was using CLOCK_PER_SEC giving undeclared, so I didn't used it but thanks for that.

and in the for loop, I was taking about Adak's 4 semicolon that makes me little confused.
for(; ; ; ;)what does this signifies..??

I was writing for(;;;; )instead.what does this signifies..??

It signifies a syntax error. The for loop has three clauses (initialization, loop condition, and update), each separated by a semicolon. Thus only two semicolons are allowed even if the clauses are omitted.

Sorry, cse.avinash. Didn't notice that error. I made that little change from using a do while loop, in the editor, and with my eyesight, that's not the best idea.

I only see three semi-colons now, but either way, that has to be a record number. ;)

Edited 5 Years Ago by Adak: n/a

Welcome to the forum, raj2raj! ;)

It's nearly always better to start your question in a new thread, instead of a "zombie" thread like this one, but anyway. Bucket sort is like you had 10 kinds of coins, in a mixed up pile, on the table, and you needed to sort them.

So you use 5 cups, one cup for each two denominations of coin. The coins are now "close" to being sorted, but not finished. Now you use another sorting algorithm, to finish off the sorting, within the cups. Insertion sort is commonly used since it's fantastic for close-to-sorted groups like this.

After each cup (bucket), has been sorted, all the coins are put back together again, in sorted order.

There are several ways to alter this algorithm into various "flavors" of a bucket sort.

A lot more info is here:

http://en.wikipedia.org/wiki/Bucket_sort

along with pseudo code, etc.

There are some horrid Insertion sort codes above your post, in this thread. Don't use them. Use this one:

void insertionSort(int a[], int lo, int hi) {
   int i, j, val;
   for(i=lo+1;i<hi;i++) {
      val = a[i];
      j = i-1;
      while(a[j] > val) {
         a[j + 1] = a[j];
         --j;
         if(j<0) break;
      }
      a[j+1] = val;
   }
}    

Edited 3 Years Ago by Adak

Hey i am using the code of selection sort like this:

#include<stdio.h>
#include<conio.h>
void selection(int a[],int n)
{
    int i,j,temp;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(a[i]>a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=a[i];
            }
        }
    }
}

Can this code be used?

public void InsertionSort(int[] intArray)

    {

        Console.WriteLine("==========Integer Array Input===============");

        for (int i = 0; i < intArray.Length; i++)

        {

            Console.WriteLine(intArray[i]);

        }



        int temp, j;

        for (int i = 1; i < intArray.Length; i++)

        {

            temp = intArray[i];

            j = i - 1;



            while (j >= 0 && intArray[j] > temp)

            {

                intArray[j + 1] = intArray[j];

                j--;

            }



            intArray[j + 1] = temp;

        }



        Console.WriteLine("==========Integer Array OutPut===============");         

        for (int i = 0; i < intArray.Length; i++)

        {

            Console.WriteLine(intArray[i]);

        }

    }
This question has already been answered. Start a new discussion instead.