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

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