Java Insertion Sort simple example

java insertion sort quick example

Insertion Sort is a sorting algorithm with complexity of O(n2). In this example we will implement it using Java.

It’s not hard at all to understand the Insertion Sort. We have an integer array. All we do is creating the sorted array step by step:

  • iterate through the array
  • on each iteration we place entry in the correct place in the left (if the entry is smaller than the item from the left, we swap them both)
  • in the end of iteration we will have a sorted array.

Insertion sort java

Insertion Sort Java implementation

public class InsertionSort {

    public  int [] arr;

    public InsertionSort(int arr[]) {
        this.arr = arr;
        printArray(arr);
    }

    public void sort() {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j >0; j--) {
                if (arr[j] < arr[j-1]){
                    swap(arr, j, j-1);
                    printArray(arr);
                }
            }
        }
    }

    public static void main(String[] args) {
        new InsertionSort(initRandomArray(10,10)).sort();
    }
}

In this class we created a method sort() that runs the algorithm. Just run a main method. Array will be randomly regenerated each time.

In the code below we use some utility methods like swap(), initRandomArray(), printArray(). They are listed below:

public static void printArray(int[] arr) {
        for (int i : arr){
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void swap (int [] arr, int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }

    public static int[] initRandomArray(int size, int range) {
        int [] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = new Random().nextInt(range);
        }
        return arr;
    }

I hope this article was helpful. For more information checkout this video.

 

Leave a Reply

Be the First to Comment!