The insertion sort is another sorting algorithm. Just like the Bubble Sort, it has a very simple implementation and its easy to be able to see whats going on. It is not recommended to handle sorting large amounts of data (depending on size). For large amounts of data, a Merge Sort, QuickSort, or the Heap Sort is most appropriate.The sorting process is as follows:

- Best case scenario for this algorithm is O(n) where n=1, so only 1 swap is done, Average case and Worst case scenario is O(n^2)
- An example of a worst case scenario is when the collection is in reverse order (like 5,4,3,2,1), a best case scenario is when the collection is already sorted or only 1 swap needs to be done (like 1,2,3,5,4), and average case is where the collection is completely unsorted (like 2,5,1,4,3)

In pseudo-code:

INSERTION-SORT (A)

1fori <-0tolength[A]

2donextItem <- A[i]

3i<-j

4whilej >0 andA[j - 1]>nextItem

5[doAj] <-A[j - 1]

6j <- j- 1

7A[j] <-nextItem

Implementation C++:

void InsertionSort(vector<int> items, int start, int end) { int nextItem; for(unsigned int x = start; x < end; x++) { nextItem = items[x]; int j = x; while(j > 0 && items[j - 1] > nextItem) { items[j] = items[j - 1]; j--; } items[j] = nextItem; } }

Implementation C#:

class Program { static void Main(string[] args) { Console.WriteLine("Unsorted:"); int[] collection = { 3, 5, 64, 1, 9, 7, 11, 23, 50 }; for (int i = 0; i < collection.Length; i++) {//first lets write the collection before its sorted Console.Write("{0} ", collection[i]); } Console.WriteLine(); Console.WriteLine(); //here begins the insertion sort int temp; int x; for (int i = 0; i < collection.Length; i++) { temp = collection[i]; /*temp is equal to the first index of the array, * so when i = 1, temp will equal the value of whichever * index the array has for position 1, so if position 1 contains the number 7, temp = 7*/ x = i - 1;//variable x is equal to i - 1, which will be used in the comparison statement below /*while x is greater than or equal to 0 AND temp is less than the current index of the array */ while (x >= 0 && temp <= collection[x]) { collection[x + 1] = collection[x];//make the swap x--; /*move down the collection, we start at position 1 of the array, * but we subtract until we're at the end of the array (the end position of an array is * written as Length - 1).*/ } collection[x + 1] = temp;//swap completed } Console.WriteLine("Sorted!"); for (int i = 0; i < collection.Length; i++)//re-write the collection array to the console window { Console.Write("{0} ", collection[i]); } Console.ReadLine(); } }

Illustrations of the algorithm:

Advertisements

Pingback: Quicksort | Bits and Pieces of Code

Pingback: Heapsort C# Tutorial | Bits and Pieces of Code