Algorithms and Data Structures

Insertion sort

Insertion sort is very similar to the selection sort algorithm. It’s very intuitive and also keeps the left part of the array sorted and iterates further up until reaching the end of the array.
More specifically, in the insertion sort algorithm, we start from the leftmost element and progressively move to the right. As soon as we find an element that is smaller than the elements to its left, we shift all the elements one by one to the right to open up a space for the current value and place it in its correct position. So, if we have an array [0, 2, 4, 1, 10, 8] and we’re currently looking at the value 1, we would first shift the value 4, then the value 2 to the right, and then place 1 between 0 and 2. Therefore, getting [0, 1, 2, 4, 10, 8]. We’ll then move to the next element 10. Won’t do anything as it’s larger than all the elements on the left. Then will take 8, and will shift 10 to the right to make sure we place 8 between 4 and 10.
a = [...]
for i in range(1, len(a)):              # start from the second element
    while i > 0 and a[i] < a[i - 1]:    # as long as the current element is smaller
        a[i - 1], a[i] = a[i], a[i - 1] # shift the current element with the predecessor
        i -= 1                          # keep track of the index of the current element
print(a)
The insertion sort algorithm inserts the current element to its correct position in the processed array. So, in the worst case, if the elements of the array have a decreasing order, we would be required to shift all the elements coming before i to place the current item in its correct position. This will result in a total of operations.
 
Let’s simulate the algorithm on several arrays:
[4, 1, -1, 0, 2, 8]
  1. i = 1 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]
  1. i = 2 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8] ⇒ swap ⇒ [-1, 1, 4, 0, 2, 8]
  1. i = 3 ⇒ do nothing
  1. i = 4 ⇒ swap ⇒ [-1, 1, 0, 4, 2, 8] ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
  1. i = 5 ⇒ do nothing
  1. print [-1, 0, 1, 2, 4, 8]
[10, 5, 1, -7]
  1. i = 1 ⇒ swap ⇒ [5, 10, 1, -7]
  1. i = 2 ⇒ swap ⇒ [5, 1, 10, -7] ⇒ swap ⇒ [1, 5, 10, -7]
  1. i = 3 ⇒ swap ⇒ [1, 5, -7, 10] ⇒ swap ⇒ [1, -7, 5, 10] ⇒ swap ⇒ [-7, 1, 5, 10]
[1, 2, 3, 4, 5]
  1. i = 1 ⇒ do nothing
  1. i = 2 ⇒ do nothing
  1. i = 3 ⇒ do nothing
  1. i = 4 ⇒ do nothing

Challenge

Given n integers, sort them in increasing order using insertion sort.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 1000) the number of elements in the array.
The next line contains n space-separated integers ( ≤ ≤ ).

Output

The program should print the array in the input sorted in increasing order.

Examples

Input
Output
5 5 5 3 2 3
2 3 3 5 5
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue