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

  • 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: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

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