Sorting Algorithm - Insertion sort Implementation

,

Today I will show the way I have implemented the Insertion Sort algorithm.

Insertion Sort

Insertion sort is a simple sorting algorithm that sorted partition grown from left to right.

Implementation

Ascending

  • Split the array to two parts: sorted partition and unsorted partition. The algorithm will make the sorted partition grows from left to right.

  • The first element of the array (index = 0) will belong to sorted partition.

  • Traverse the array from the second element (index = 1) to the last element of the array. We traverse the array by ascending order, btw. The part from a[1..n] is unsorted partition.

Each of iteration, large comparison the first element of unsorted partition versus the last right elements of sorted partition.

Another loop will look through the sorted partition by descending way, and then shift right elements of sorted partition to one position ahead of their current position.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// pseudo code

for (i = 1; i < arr.length; i++) {
  int firstEleUnSortedPart = arr[i];

  int lastRightEleSortedPart = i - 1;

  while (lastRightEleSortedPart >= 0 && arr[lastRightEleSortedPart] > firstEleUnSortedPart) {
    arr[lastRightEleSortedPart + 1] = arr[lastRightEleSortedPart]
    lastRightEleSortedPart = lastRightEleSortedPart - 1;
  }

  // Now the lastRightEleSortedPart has been changed after loop
  a[lastRightEleSortedPart + 1] = firstEleUnSortedPart;
}
  • The algorithm ends when there is no element in unsorted partition means the outside loop hit to last element of the array.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int length = arr.length;

for(int i = 1; i < length; i++) {
  int fstEle = arr[i];

  int j = i - 1;

  // shift elements of arr[0..i-1] to right side that > fstEle
  while (j >= 0 && arr[j] > fstEle) {
    arr[j+1] = arr[j];
    j = j - 1;
  }

  arr[j + 1] = fstEle;
}

printArray(arr);