Insertion Sort Implementation In Java – Working Code Example

Insertion Sort Animation. Image Credit: Wikipedia / Creative Commons

Algorithm:

  • Take one element, compare with the one next to it and put in the order it belongs to, thus forming a partially sorted list.
  • Iterate through the list, one item at a time until no input elements remain.

Pseudo code is given below:

for i ← 1 to length(A)
j ← i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1

Complexity:

  • Best Case: O(n) – For already sorted list
  • Average Case: O(n^2)
  • Worst Case: O(n^2)

Notes / Usage:

  • Insertion Sort is:
    • Stable
    • Takes O(1) extra space for swapping
    • In-Place Sorting – No extra memory is required
  • One real life usage of this kind of sorting is sorting a deck of cards.

Java Implementation Code:

package com.icodejava.blog.datastructure;

import java.util.Arrays;

/**
* @author Kushal Paudyal
* www.icodejava.com
* Created On -  Feb 26, 2014
* Last Modified On - Feb 26, 2014
*/
public class InsertionSort {

public static void main(String args[]) {
    int[] numberArray = { 5, 4, 7, 3, 3, 9, 0, 1, 2, 8, 6, -5 };

    sort(numberArray);

}

public static void sort(int[] numberArray) {

     System.out.println("Input Array: " + Arrays.toString(numberArray));

     for (int i = 1; i < numberArray.length; i++) { 			
         for (int j = i; j > 0; j--) {
             // Start comparing data with adjacent one and swap if smaller
             if (numberArray[j] < numberArray[j - 1]) {
             swap(numberArray, j, j - 1);
         }
     }
}

System.out.println("Sorted Array: " + Arrays.toString(numberArray));

}

/**
* Swaps data from an array.
*/
private static void swap(int[] array, int firstIndex, int secondIndex) {
   if (array == null || firstIndex < 0 || firstIndex > array.length 
     || secondIndex < 0 || secondIndex > array.length) {
    return;
   }
   int temp = array[firstIndex];
   array[firstIndex] = array[secondIndex];
   array[secondIndex] = temp;

}

}


Output of running above program:

Input Array: [5, 4, 7, 3, 3, 9, 0, 1, 2, 8, 6, -5]
Sorted Array: [-5, 0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9]
Tagged , , , , , , . Bookmark the permalink.

One Response to Bubble Sorting A String Array in Ascending And Descending Order

  1. Ririn says:

    Thanks buat script codenya, membantu saya mengerkajan tugas saya

Leave a Reply

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