Insertion Sort program in Java

Insertion Sort:

Insertion sort is somewhat similar to selection but in insertion sort one element is selected from unsorted array and placed at proper location in sorted array.
Worst case performance:     О(n2) comparisons, swaps
Best case performance:         Ω(n) comparisons, O(1) swaps
Average case performance:  Ðž(n2) comparisons, swaps

 

insertion sort in java

insertion sort in java

import java.io.*;
class sort
{
static void insertion(int b[],int n)
{
int i,k,y,z=1;
for(k=1;k<n;k++)
{
y=b[k];
for(i=k-1;i>=0&&y<b[i];i--)
b[i+1]=b[i];
b[i+1]=y;
System.out.print("pass "+(z++)+":");
for(i=0;i<n;i++)
{
System.out.print("\t"+b[i]);
}
System.out.println();
}
System.out.println("\nSorted Elements are :");
for(i=0;i<n;i++)
System.out.print("\t"+b[i]);
System.out.println();
}

}

class sorting
{
public static void main(String args[ ])throws IOException
{
int i,n=0;
String ans="y";
DataInputStream in = new DataInputStream(System.in);
System.out.print("Enter how many numbers to be sorted : ");
n = Integer.parseInt(in.readLine());

int x3[]=new int[n];

System.out.println("Enter numbers");
for(i=0;i<n;i++)
{
x3[i]= Integer.parseInt(in.readLine());
}
System.out.println();
sort s=new sort();

System.out.println("SORTING BY INSERTION SORT");
s.insertion(x3,n);

}
}
/*OUTPUT:
Enter how many numbers to be sorted : 5
Enter numbers
65
45
60
33
15

 

SORTING BY INSERTION SORT
pass 1: 45 65 60 33 15
pass 2: 45 60 65 33 15
pass 3: 33 45 60 65 15
pass 4: 15 33 45 60 65

Sorted Elements are :
15 33 45 60 65
*/

4

Insertion Sort in C

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *