JAVA EXAMPLE PROGRAMS

JAVA EXAMPLE PROGRAMS

Publish Your Article Here

Program: Implement insertion sort in java.


Insertion sort is a simple sorting algorithm, it builds the final sorted array one item at a time. It is much less efficient on large lists than other sort algorithms.

Advantages of Insertion Sort:

1) It is very simple.
2) It is very efficient for small data sets.
3) It is stable; i.e., it does not change the relative order of elements with equal keys.
4) In-place; i.e., only requires a constant amount O(1) of additional memory space.

Insertion sort iterates through the list by consuming one input element at each repetition, and growing a sorted output list. On a repetition, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Insertion Sort
Image source: “Introduction to Algorithms”, The MIT Press


The best case input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., Θ(n)). During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array. The simplest worst case input is an array sorted in reverse order. The set of all worst case inputs consists of all arrays where each element is the smallest or second-smallest of the elements before it. In these cases every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. This gives insertion sort a quadratic running time (i.e., O(n2)). The average case is also quadratic, which makes insertion sort impractical for sorting large arrays. However, insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quicksort; indeed, good quicksort implementations use insertion sort for arrays smaller than a certain threshold, also when arising as subproblems; the exact threshold must be determined experimentally and depends on the machine, but is commonly around ten.


package com.java2novice.algos;

public class MyInsertionSort {

	public static void main(String a[]){
		int[] arr1 = {10,34,2,56,7,67,88,42};
		int[] arr2 = doInsertionSort(arr1);
		for(int i:arr2){
			System.out.print(i);
			System.out.print(", ");
		}
	}
	
	public static int[] doInsertionSort(int[] input){
		
	    int temp;
	    for (int i = 1; i < input.length; i++) {
		    for(int j = i ; j > 0 ; j--){
			    if(input[j] < input[j-1]){
				    temp = input[j];
				    input[j] = input[j-1];
				    input[j-1] = temp;
			    }
		    }
	    }
	    return input;
	}
}


Output:
 2, 7, 10, 34, 42, 56, 67, 88, 
<< Previous Program | Next Program >>

Java Sorting Algorithms Examples

  1. Implement bubble sort in java.
  2. Implement selection sort in java.
  3. Implement insertion sort in java.
  4. Implement quick sort in java.
  5. Implement merge sort in java.
Knowledge Centre
What is servlet context?
The servlet context is an interface which helps to communicate with other servlets. It contains information about the Web application and container. It is kind of application environment. Using the context, a servlet can obtain URL references to resources, and store attributes that other servlets in the context can use.
Famous Quotations
We know what we are, but know not what we may be.
-- William Shakespeare

About Author

I'm Nataraja Gootooru, programmer by profession and passionate about technologies. All examples given here are as simple as possible to help beginners. The source code is compiled and tested in my dev environment.

If you come across any mistakes or bugs, please email me to [email protected].

Most Visited Pages

Other Interesting Sites

Reference: Java™ Platform Standard Ed. 7 - API Specification | Java™ Platform Standard Ed. 8 - API Specification | Java is registered trademark of Oracle.
Privacy Policy | Copyright © 2017 by Nataraja Gootooru. All Rights Reserved.