Algorithm - Insertion Sort (Concept,Pseudocode and C++ code)

Insertion Sort

Insertion sorting is an algorithm that completes a sort by finding and inserting its position by comparing all elements of the data array with the parts of the array that are already sorted, in order from the beginning.

• Insertion sort starts from the second index
• Compare two value : data value (A) and the data of the prior index of the corresponding data (key value)
• If the key value is smaller
  • the A value is copied to the later index
• This is repeated until the key value encounters larger data
  • Insert key value right after location where big data is met

Code Design

index
value

• example of four datas in the list

  1. (5 3 2 4)

  1 0
  3 5
  (3 5 2 4)

  base data index	compared data index
  1	0

  2. (3 5 2 4)

  2 1
  2 5
  (3 2 5 4)
  1 0
  2 3
  (2 3 5 4)

  base data index	compared data index
  2	1

  3. (2 3 5 4)

  3 2
  4 5
  (2 3 4 5)
  2 1
  4 3
  1 0

  base data index	compared data index
  3	2

  4. (2 3 4 5)

Pseudocode

Time Complexity

two for loops : $O(n^2)$

C++ code implementation

#include<iostream>
using namespace std;

void insertionSort(int * data, int size)
{
	for(int i = 0; i < size-1 ; ++i )
	{
		for(int base = i+1 ; base != 0 ; --base)
		{
			if(data[base] < data[base-1])
			{
				int temp = data[base];
				data[base] = data[base-1];
				data[base-1] = temp;
			}
			else
				break;
		}
	}	
}
int main()
{
	int data_i[] = {4,5,3,2,1};

	int len = sizeof(data_i) / sizeof(data_i[0]);
	cout  << len << endl;

	for(int i = 0; i < len; ++i)
		cout << data_i[i] << endl;

	insertionSort(data_i, len);
	
	for(int i = 0; i < len; ++i)
		cout << data_i[i] << endl;
		
	return 0;
	
}