Algorithms and Data Structures

Selection sort

The selection sort algorithm is one of the most intuitive sorting algorithms. It repeatedly finds the minimum element from the array and brings it to the front. Then moves on to finding the minimum element from the remaining array, and repeats this process until reaching the very end of the array.
a = [...]
for i in range(len(a)):             # We should place the minimum of a[i:] at a[i]
    val = min(a[i:])                # min value among a[i, i+1, ...n]
    idx = a.index(val, i)           # Finx the index of the minimum element
    a[i], a[idx] = a[idx], a[i]     # Swap a[i] and a[idx]
print(a)
On each iteration, we take the minimum from the remaining array and swap the current element and the minimum using their indices. In case the current one is the minimum, nothing will happen, as we’ll swap the current one with itself, which won’t change the array.
 
The selection sort algorithm finds the minimum element from the array and swaps the current index with that minimum. This means that on each iteration, we loop over the whole remaining array to find the minimum (the min function iterates over the array one by one to find the minimum value). Therefore, the whole running time of the algorithm is n iterations that do around n iterations ⇒ operations in total.
Let’s simulate the algorithm on several arrays:
[4, 1, -1, 0, 2, 8]
  1. i = 0 ⇒ val = -1 ⇒ idx = 2 ⇒ swap ⇒ [-1, 1, 4, 0, 2, 8]
  1. i = 1 ⇒ val = 0 ⇒ idx = 3 ⇒ swap ⇒ [-1, 0, 4, 1, 2, 8]
  1. i = 2 ⇒ val = 1 ⇒ idx = 3 ⇒ swap ⇒ [-1, 0, 1, 4, 2, 8]
  1. i = 3 ⇒ val = 2 ⇒ idx = 4 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
  1. i = 4 ⇒ val = 4 ⇒ idx = 4 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
  1. i = 5 ⇒ val = 8 ⇒ idx = 5 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
[10, 5, 1, -1, -2, -7]
  1. i = 0 ⇒ val = -7 ⇒ idx = 5 ⇒ swap ⇒ [-7, 5, 1, -1, -2, 10]
  1. i = 1 ⇒ val = -2 ⇒ idx = 4 ⇒ swap ⇒ [-7, -2, 1, -1, 5, 10]
  1. i = 2 ⇒ val = -1 ⇒ idx = 3 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 3 ⇒ val = 1 ⇒ idx = 3 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 4 ⇒ val = 5 ⇒ idx = 4 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 5 ⇒ val = 10 ⇒ idx = 5 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
[1, 2, 3, 4, 5]
  1. i = 0 ⇒ val = 1 ⇒ idx = 0 ⇒ swap ⇒ [1, 2, 3, 4, 5]
  1. i = 1 ⇒ val = 2 ⇒ idx = 1 ⇒ swap ⇒ [1, 2, 3, 4, 5]
  1. i = 2 ⇒ val = 3 ⇒ idx = 2 ⇒ swap ⇒ [1, 2, 3, 4, 5]
  1. i = 3 ⇒ val = 4 ⇒ idx = 3 ⇒ swap ⇒ [1, 2, 3, 4, 5]
  1. i = 4 ⇒ val = 5 ⇒ idx = 4 ⇒ swap ⇒ [1, 2, 3, 4, 5]

Challenge

Given n integers, sort them in increasing order using selection 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.4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in