Data Structure – Insertion Sort

it’s similar to bubbleSort, but it happened only in 1 PASS

by comparing every two items from left to right in array, pull one item from array then find its proper place and insert it there, then shift the rest of items – normally it would be SORTED items.

LEFT considered SORTED

items in RIGHT side considered UNSORTED.

when to use:

  • small datasets
  • nearly sorted large datasets
  • because the number of comparisons and swaps is relatively small.

orders:

  • very similar to  bubble sort
  • O(N^2) in worst case and average case
  • and for large semi-sorted data or small datasets we can say O(N)

space:

doesn’t need more data spaces so it can be done in the same place or in devices with minimum spaces.

how to implement:


/**
*
* @author Navid_
*/
public class InsertionSort {

public static int[] arr = new int[]{5, 10, 13, 90, 1};

public void sort(int[] array) {

int tmp = 0;
for (int i = 0; i + 1 < array.length; i++) { //loop through array if (array[i] >= array[i + 1]) {
// find the guy that needs to be inserted somewhere
System.out.printf("found an item to sort...array[%d] = %d\n", i + 1, array[i + 1]);
tmp = array[i + 1]; // save the unsorted guy
for (int k = i + 1; k >= 0; k--) {

//just handling when the first item is still larger than temp;
if (k == 0) {

System.out.printf("shifting to the RIGHT = %d and REPLACING the FIRST item in array with = %d, then BREAK.\n", array[k], tmp);
array[k] = tmp;
showContent(array);
break;
}

// trying to find the location and insert
if (array[k - 1] > tmp) {
System.out.printf("SHIFT to RIGHT= %d.\n", array[k - 1]);
array[k] = array[k - 1];
showContent(array);
} else {
System.out.printf("Found Place to INSERT so inserting ... array[%d] = %d.\n", k - 1, tmp);
array[k - 1] = tmp;
showContent(array);
break;
}

}

}

}

}

/**
* resetting array content to what it was.
*/
public static void resetData() {
//        myArray = new int[]{10, 2, 5, 20, 90, 12, 31, 5};
arr = new int[]{5, 10, 13, 90, 1};
}

/**
* showing content of array
*
* @param arr
*/
public void showContent(int[] arr) {

System.out.print("[ ");
for (int i : arr) {
System.out.printf("%d, ", i);
}
System.out.println(" ]");
}

public static void main(String[] args) {

InsertionSort is = new InsertionSort();

is.showContent(InsertionSort.arr);
is.sort(InsertionSort.arr);
is.showContent(InsertionSort.arr);

}

}

and its output will be something like this …

run:
[ 5, 10, 13, 90, 1,  ]
found an item to sort...array[4] = 1
SHIFT to RIGHT= 90.
[ 5, 10, 13, 90, 90,  ]
SHIFT to RIGHT= 13.
[ 5, 10, 13, 13, 90,  ]
SHIFT to RIGHT= 10.
[ 5, 10, 10, 13, 90,  ]
SHIFT to RIGHT= 5.
[ 5, 5, 10, 13, 90,  ]
shifting to the RIGHT = 5 and REPLACING the FIRST item in array with = 1, then BREAK.
[ 1, 5, 10, 13, 90,  ]
[ 1, 5, 10, 13, 90,  ]
BUILD SUCCESSFUL (total time: 0 seconds)

NOTE:

so for small amount of items you can still

Advertisements

One thought on “Data Structure – Insertion Sort

  1. Pingback: Data Structure – Sorting Algorithms in Java | Navid's Thoughts

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s