Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • 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 = 0val = -1idx = 2 ⇒ swap ⇒ [-1, 1, 4, 0, 2, 8]
    1. i = 1val = 0idx = 3 ⇒ swap ⇒ [-1, 0, 4, 1, 2, 8]
    1. i = 2val = 1idx = 3 ⇒ swap ⇒ [-1, 0, 1, 4, 2, 8]
    1. i = 3val = 2idx = 4 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
    1. i = 4val = 4idx = 4 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
    1. i = 5val = 8idx = 5 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
    [10, 5, 1, -1, -2, -7]
    1. i = 0val = -7idx = 5 ⇒ swap ⇒ [-7, 5, 1, -1, -2, 10]
    1. i = 1val = -2idx = 4 ⇒ swap ⇒ [-7, -2, 1, -1, 5, 10]
    1. i = 2val = -1idx = 3 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
    1. i = 3val = 1idx = 3 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
    1. i = 4val = 5idx = 4 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
    1. i = 5val = 10idx = 5 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
    [1, 2, 3, 4, 5]
    1. i = 0val = 1idx = 0 ⇒ swap ⇒ [1, 2, 3, 4, 5]
    1. i = 1val = 2idx = 1 ⇒ swap ⇒ [1, 2, 3, 4, 5]
    1. i = 2val = 3idx = 2 ⇒ swap ⇒ [1, 2, 3, 4, 5]
    1. i = 3val = 4idx = 3 ⇒ swap ⇒ [1, 2, 3, 4, 5]
    1. i = 4val = 5idx = 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: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

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