Basic C programming course

Sắp xếp là bài toán rất thường gặp trong ứng dụng công nghệ thông tin. Có nhiều thuật toán sắp xếp khác nhau, ví dụ như:

• Sắp xếp nổi bọt (Bubble Sort)
• Sắp xếp chọn (Selection Sort)
• Sắp xếp chèn (Insertion Sort)
• Sắp xếp vun đống (Heap Sort)
• Sắp xếp trộn (Merge Sort)
• Sắp xếp phân đoạn (Quick Sort, hay còn gọi là sắp xếp nhanh)
• Sắp xếp theo cơ số (Radix Sort)

Nhiệm vụ của bài tập này là cài đặt thuật toán sắp xếp chèn, mà cụ thể là sắp xếp tăng dần, sắp xếp từ phải qua trái. Trong đó yêu cầu in ra kết quả trung gian có được trong quá trình sắp xếp. Tìm hiểu về thuật toán sắp xếp này ở các địa chỉ sau:
https://vi.wikipedia.org/wiki/Sắp_xếp_chèn
https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm

Input

Dòng 1: n - một số nguyên dương, n < 20
Dòng 2: n số nguyên trên đoạn [0, 999]

Output

Thực hiện sắp xếp chèn cho dãy đã cho và in ra:
- Dãy số ban đầu
- Các dãy trung gian mỗi khi có một sự hoán đổi giá trị các phần tử trong dãy
- Dãy kết quả cuối cùng
Trước mỗi dãy là số thứ tự của dãy. Các số nguyên được in ra với 4 vị trí.

Example

Input:
10
2  3  7  5  6  4  0  6  4  6

Output:
   0:    2   3   7   5   6   4   0   6   4   6
   1:    2   3   7   5   6   4   0   4   6   6
   2:    2   3   7   5   6   0   4   4   6   6
   3:    2   3   7   5   0   6   4   4   6   6
   4:    2   3   7   5   0   4   6   4   6   6
   5:    2   3   7   5   0   4   4   6   6   6
   6:    2   3   7   0   5   4   4   6   6   6
   7:    2   3   7   0   4   5   4   6   6   6
   8:    2   3   7   0   4   4   5   6   6   6
   9:    2   3   0   7   4   4   5   6   6   6
  10:    2   3   0   4   7   4   5   6   6   6
  11:    2   3   0   4   4   7   5   6   6   6
  12:    2   3   0   4   4   5   7   6   6   6
  13:    2   3   0   4   4   5   6   7   6   6
  14:    2   3   0   4   4   5   6   6   7   6
  15:    2   3   0   4   4   5   6   6   6   7
  16:    2   0   3   4   4   5   6   6   6   7
  17:    0   2   3   4   4   5   6   6   6   7