Sorting in Java – Take III

Insertion Sort

The insertion sort, unlike the other sorts, passes through the array only once. Its commonly compared to organizing a deck of playing cards.
You pick up the random cards one at a time. As you pick up each card, you insert it into its correct position in your hand of organized cards.
The insertion sort splits an array into two sub-arrays. The first sub-array (like the cards in your hand) is always sorted and increases in size as the sort continues. The second sub-array (like the cards to be picked up) is unsorted, contains all the elements yet to be inserted into the first sub-array, and decreases in size as the sort continues.
The insertion sort can be very fast and efficient when used with smaller arrays. Unfortunately, it loses this efficiency when dealing with large amounts of data.


package Sorting;
// Insertion Sort
public class InsertionSort {

public void InSort(int a[],int n){
 int key=0;
 int j=0;
 for (int i=1;i<n;i++){
 key=a[i];
 j=i-1;
 while((j>=0) && (a[j]>key)){
 a[j+1]=a[j];
 j=j-1;
 }
 a[j+1]=key;
 }

 for(int i=0;i<n;i++){
 System.out.println(a[i]);
 }
 }

 public static void main(String[] args) {
 new InsertionSort().InSort(new int[] {66,45,76,12,9,4},6);// Elements and number of elements
 }
}

 

Advertisements