Insertion Sort Algorithm

A Java example of the insertion sort algorithm.

Running a test file of 100000 randomly ordered integers through this algorithm takes about 1.53 seconds on my system. I will be using the same test file for comparison against other sorting algorithms.

Josh


/**
 * A very basic Insertion Sort class.
 * 
 * This class will only sort an int[].
 * 
 * @author Joshua Weise
 */
public class InsertionSort {

	// array of numbers
	private int[] data;
	
	public InsertionSort(int[] data) {
		this.data = data;
	} 
	
	// Insertion sort data
	public void sort() {
		for (int i = 1; i < data.length; i++) {
			// the value we are moving left
			int y = data[i];
			// the array location we could move our value into
			int z = i;
			// loop until we find the farthest left we can move our value into
			// moving the other values out of the way right as we go
			while (z > 0 && y < data[z-1]) {
				data[z] = data[z - 1] ;
				z--; 
			}
			// put our original value into its new position
			data[z] = y;
		}
	}
	
	// return data
	public int[] getData() {
		return data;
	}
	
}

This entry was posted in Java, Sorting Algorithms. Bookmark the permalink.

Leave a Reply