Insertion Sort Implementation in Java

Insertion sort is a simple algorithm. Insertion sort logic works as follows: To insert an element in an already existing set, we make room for the new item by moving larger items one position to the right. Then insert the new item at the newly available position. The algorithm most often used to sort cards in a bridge game is an example of Insertion Sort.

Following Java class shows how to implement Selection sort in Java.

/**
 * Insertion Sort Implementation In Java
 * 
 * @author zparacha
 *
 * @param <T>
 */

package com.zparacha.algorithms;

import java.util.Arrays;

public class InsertionSort<T extends Comparable<T>> {
	int size;
	T[] data;

	public InsertionSort(int n) {
		data = (T[]) new Comparable[n];
	}

	public void insert(T a) {
		data[size++] = a;

	}

	public boolean isSmaller(T x, T y) {
		return x.compareTo(y) < 0;
	}

	public void swap(int i, int j) {
		T temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}

	public void sort() {
		for (int i = 1; i < size; i++) {
			for (int j = i; j > 0 && isSmaller(data[j], data[j - 1]); j--) {
				swap(j, j - 1);
			}
		}
	}

	public static void main(String[] args) {
		InsertionSort<Integer> is = new InsertionSort<>(5);
		is.insert(3);
		is.insert(1);
		is.insert(5);
		is.insert(4);
		is.insert(2);
		System.out.println(Arrays.toString(is.data));
		is.sort();
		System.out.println(Arrays.toString(is.data));
	}
}

 

 

Leave a Reply

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