13. InsertionSort

Sorts a random array of integers, using the method called "insertion sort".

**Description: ** Sorts a random array of integers, using the method called "insertion sort".

Code

/*
 * Insertion sort -- ref: Algorithm Text, Cormen
 */
package asu.insertionsort;

import java.util.Arrays;
 
public class InsertionSort {
    
    public static void main(String[] args) {
        //initialize an array of integers:
        final int N = 10;
        int[] array = new int[N];

        //generate random integers from 0 to 99:
        for (int i = 0; i < array.length; i++) {
            array[i] = (int)(100 * Math.random());
        }

        //print the random array:
        System.out.println("Original array:");
        printArray(array);

        insertionSort(array);
        //Java has sort function. Arrays.sort(array);

        //print the sorted array
        System.out.println("Scorted array:");
        printArray(array); 
    }
    
    private static void printArray(int[] a) {
        for(int i = 0; i < a.length; i++) {
            System.out.println("a[" + i + "] = " + a[i]);
        }
    }
    
    private static void insertionSort(int[] a) {
        for(int j = 1; j < a.length; j++) {
            int key = a[j];
            int i = j - 1;
            while (i >= 0 && a[i] > key) {
                a[i+1] = a[i];
                i = i - 1;
            }
            a[i+1] = key;
        }
    }
}

Output

Original array:
a[0] = 56
a[1] = 28
a[2] = 55
a[3] = 73
a[4] = 65
a[5] = 64
a[6] = 51
a[7] = 69
a[8] = 28
a[9] = 15
Scorted array:
a[0] = 15
a[1] = 28
a[2] = 28
a[3] = 51
a[4] = 55
a[5] = 56
a[6] = 64
a[7] = 65
a[8] = 69
a[9] = 73