Today was my first formal computing training, by experienced mentors and lecturers, and it’s already at the stage of Olympiad Training Camp! Yes, I have never attended a programming lesson before this. I read through books and internet for information. At that time, my progress was *really* slow, because no one can explain the concepts to me. However, those were the past!

The first lesson was Insertion-Sort Algorithm. Insertion-Sort is easy to understand: Imagine you have a list of number cards on the board. Pick up the second card from your left, say **key** (the first card has nothing to sort) and compare it with the card on its left. If it’s larger than the **key** card, move it to the right and repeat this procedure, until you reach the end (the first card from your left) or the card you were comparing is smaller than the **key** card, then you can leave the **key** card on the space that the previous card left. Then, go to the next **key** card.

Visualgo.net provide a good visualization on Insertion-Sort Algorithm. Select `INSERTION`

on the menu bar at the top and adjust the speed at the bottom left slider.

Below are the codes for Insertion-Sort Algorithm:

**Pseudocode**

Insertion_Sort(A)
for i from 1 to A.length
key = A[i]
j = i - 1
while j > 0 and A[j] > key
A[j+1] = A[j]
j = j - 1
A[j+1] = key

**C++ Implementation**

void Insertion_Sort(int A[], int length){
for (int i = 1; i < length; i++){
int key = A[i];
int j = i - 1;
while (j >= 0; A[j] > key){
A[j+1] = A[j];
j--;
}
A[j+1] = key;
}
}

Despite the fact that Insertion-Sort is easy and straightforward, it is not a good sorting algorithm. This is because you would have to go through all the cards, say, . For the worst-case, which is when the cards are reverse-sorted, every -th card needs steps to sort into the correct position. The total steps required is , yield the time complexity .

### Like this:

Like Loading...

*Related*