[Sorting] Insertion Sort 삽입정렬

Insertion Sort is almost as simple as Selection Sort, but a little more flexible!

 

The basic idea is to sort a collection of records by inserting them into an already sorted file. The process can be described as follows:

1. Take elements one by one
2. Insert the element in its proper position among those already taken and sorted in a new collection
3. Repeat these processes until all elements are taken and sorted in the proper order

 

# Example

array = { 12, 11, 13, 5, 6 };

1. Current value 11:
   12 > 11 { 11, 12, 13, 5, 6 }
2. Current value 13:
   12 < 13 and 11 < 13
3. Current value 5:
   13 > 5 { 11, 12, 13, 13, 6 },
   12 > 5 { 11, 12, 12, 13, 6 },
   11 > 5 { 11, 11, 12, 13, 6 }, and
   assign the current value to the first one { 5, 11, 12, 13, 6 }
4. Current value 6:
   13 > 6 { 5, 11, 12, 13, 13 },
   12 > 6 { 5, 11, 12, 12, 13 },
   11 > 6 { 5, 11, 11, 12, 13 },
   5 < 6 { 5, 11, 11, 12, 13 }, and
   assign the current value to the second one { 5, 6, 11, 12, 13 }

result = { 5, 6, 11, 12, 13 };

 

 

# Pseudocode

buf: array
tmp: temp value

for i is 1 to buf.size() - 1 do:
	tmp := buf[i]
    
    for j is i - 1 to 0 when buf[j] > tmp && j > -1 do:
    	buf[j + 1] := buf[j]
    end for
    
    buf[j + 1] := tmp
end

 

# Computation in C

 

# Time Complexity

• Worst complexity: O(n²)
• Average complexity: O(n²)
• Best complexity: O(n)

# Space complexity

• O(1)