MCO Training Camp Day 1: #1 First Formal Training!

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, $n$. For the worst-case, which is when the cards are reverse-sorted, every $i$ -th card needs $i - 1$ steps to sort into the correct position. The total steps required is $n(n-1)/2$, yield the time complexity $O(n^2)$.