Insertion Sort

Insertion Sort is more efficient than the simple Bubble sort.

It begins by only comparing the first element, and the one to it’s right. If the one on it’s right is smaller, they swap. Step 2, compares the second element and the one on it’s right. If the element on it’s right is smaller, it swaps; and does step 1 again. However, if the second element and it’s right hand side partner don’t swap, step 2 finishes. Step 3 compares the third element and the one of it’s right…. etc. Unless the list is in complete reverse order, it will make less comparisons than the Bubble sort.

It’s better with a picture.

Example of the insertion sort.

Example of the insertion sort.

Here’s an example in code:


#include <iostream>
void InsertionSort(int a[], int length)
{
 for (int i=0; i<length - 1; i++)
 {
 int j = i;
 while (j>=0 && a[j]>a[j+1])
 {
 int temp = a[j];
 a[j] = a[j+1];
 a[j+1] = temp;
 j= j-1;
 }
 }
}

int main(){

int a[] = {8,5,7,6,2,3};
 int size = sizeof(a) / sizeof(*a);
 InsertionSort(a, size);

 for (int i=0; i<size; i++)
 {
 std::cout << a[i];
 }

}

 

Advertisements