Insertion Sort

Introduction

Insertion sort is called insertion sort because the algorithm repeated inserts a value into an array that is already sorted. It essentially chops the array into two pieces. The first piece is sorted, the second is not. We repeatedly take a number from the second piece and insert it into the already sorted first piece of the array.

Algorithm

1. start with second variable.

2. put number into a temporary variable. This makes it possible to move items into the spot the number use to occupy. This spot is now considered to be an empty spot in the sorted portion of the array

3. if number in temporary can go into empty spot, put it in

4. otherwise move last item in the part into empty spot

5. repeat steps 3 to 4 until item is temp is placed into the first part of the array

6. repeat for every number in the second part of the array until all numbers are placed

Animation

Data Structure Animations using Processing.js by cathyatsenecacathyatseneca.github.io

C/C++ Implementation

void insertionSort(int arr[],int size){
    int curr;
    int i, j;
    for(i=1;i<size;i++){
        curr=arr[i];
        for(j=i;j>0 && arr[j-1] > curr;j--){
            arr[j]=arr[j-1];
        }
        arr[j]=curr;
    }
}