## Algorithms - Insertion Sort

Insertion sort is a very simple sorting algorithm that is relatively efficient for **small lists and mostly-sorted lists**.

It is often used as part of more sophisticated algorithms. It does sort by taking elements from the list one by one and inserting them in their correct position into a new sorted list. In arrays, the new list and the remaining elements can share the array's space, but **insertion is expensive**, requiring shifting all following elements over by one. The insertion sort works just like its name suggests - it inserts each item into its proper place in the final list.

- Insertion sort takes advantage of presorting.

More efficient in practice than most other simple quadratic (O(n2)) algorithms such as selection sort or bubble sort

the best case (nearly sorted input) is**O(n)**. - Efficient for small data sets.
- It requires fewer comparisons compared with bubble sort unless its list is backward.

the time complexity is**O(n + d)**, where**d**is the number of inversions. - It requires only one comparison per element for a presorted list.
- It is
**stable**sort. It does not change the relative order of elements with equal keys. - It is
**in-place**sorting. It only requires a constant amount**O(1)**of additional memory space. - It is online sorting. It can sort a list as it receives it.
- With a sorted array, we can insert new elements.
- It is similar to the way we sort
**card deck**.

The simplest implementation of this requires two list structures - the source list and the list into which sorted items are inserted. To save memory, most implementations use an **in-place** sort that works by moving the current item past the already sorted items and repeatedly swapping it with the preceding item until it is in place.

**Shell sort** is a variant of insertion sort that is more efficient for **larger lists**. This method is much more efficient than the bubble sort, though it has more constraints.

Psedo code should look like this:

for i = 1, n j = i while(j > 0 and E[j] < E[j-1]) swap(E[j], E[j-1]) j--

C++ code

#include <iostream> #include <iomanip> using namespace std; void swap(int &x;, int &y;) { int temp = x; x = y; y = temp; } void insertion(int a[], int sz) { for(int i=1; i < sz; i++) { int j = i; while(j > 0 && (a[j] < a[j-1])) { swap(a[j], a[j-1]); j--; } cout << endl; for (int k = 0; k < sz; k++) cout << setw(3) << a[k]; } } int main() { int a[] = { 15, 9, 8, 1, 4, 11, 7, 12, 13, 6, 5, 3, 16, 2, 10, 14}; int size = sizeof(a)/sizeof(int); for (int i = 0; i < size; i++) cout << setw(3) << a[i]; insertion(a, size); cout << endl; return 0; }

This is the way we're sorting cards.

Start by picking up a single card to form **a hand that is already sorted**. For each card picked up, find the right place to insert card into the hand, thus maintaining the invariant that the cards in the hand are sorted. When we hold cards in our hand, it is easy to insert a card into its correct position because the other cards are just pushed aside a bit to accept the new card.

Output from the run:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Code using linked list:

#include <iostream> using namespace std; struct List { int data; struct List *next; } ; void printList(struct List *head) { struct List* ptr = head; while(ptr) { cout << ptr->data << " " ; ptr = ptr->next; } cout << endl; } struct List* createList(int a[], int sz) { struct List *head = new struct List; struct List *current = head; for(int i = 0; i < sz; i++) { current->data = a[i]; if (i == sz - 1 ) { current->next = NULL; break; } current->next = new struct List; current = current->next; } return head; } // from http://analgorithmaday.blogspot.com/2011/01/insertion-sort-with-linked-listin-place.html struct List* insertion(struct List *head) { if(head == 0) return head; // unsorted list - from the 2nd element struct List *unsorted = head->next; while(unsorted != 0) { // take key as an element in the unsorted list. struct List *prev = 0; struct List *iter = head; struct List *key = unsorted; // iterate within the sorted list and find the position while(iter != 0) { if(iter->data < key->data) { prev = iter; iter = iter->next; } else break; } unsorted = unsorted->next; // if reached the end of sorted list if(iter == key) continue; // note down the position to replace in a sorted list struct List *replace = iter; //move iter to end of the sorted list while(iter->next != key) iter=iter->next; // link to the upsorted list iter->next = unsorted; // delete the key and replace it in sorted list if(prev == 0) { head = key; } else { prev->next = key; } key->next = replace; printList(head); } return head; } int main() { int a[] = { 15, 9, 8, 1, 4, 11, 7, 12, 13, 6, 5, 3, 16, 2, 10, 14}; int size = sizeof(a)/sizeof(int); struct List *head = createList(a, size); printList(head); head = insertion(head); printList(head); cout << endl; return 0; }

Q: An array contains two sub- sorted arrays. Give an in-place algorithm to sort two sub arrays.

The following code uses the insertion sorting algorithm devised in the previous section.

We have an input array **a[] = 1 4 5 7 8 9 2 3 6 10 11** composed of two sorted sub-arrays. We want to sort the array in place. In the process, we need to use **swap()** function which does in-place swap.

#include <iostream> using namespace std; void swap(int &x;, int &y;) { x = x ^ y; y = x ^ y; x = x ^ y; } void insertion(int a[], int sz) { for(int i=1; i < sz; i++) { int j = i; while(j > 0) { if(a[j-1] > a[j]) swap(a[j-1],a[j]); j--; } } for(int i = 1; i < sz; i++) cout << a[i] << " "; } int main() { int a[] = { 1, 4, 5, 7, 8, 9, 2, 3, 6, 10, 11 }; int size = sizeof(a)/sizeof(int); for (int i = 0; i < size; i++) cout << a[i] << " "; cout << " ==> " << endl; insertion(a, size); cout << endl; return 0; }

Output:

1 4 5 7 8 9 2 3 6 10 11 ==> 2 3 4 5 6 7 8 9 10 11

Ph.D. / Golden Gate Ave, San Francisco / Seoul National Univ / Carnegie Mellon / UC Berkeley / DevOps / Deep Learning / Visualization