We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Practice
  2. Algorithms
  3. Sorting
  4. Insertion Sort - Part 2
  5. Discussions

Insertion Sort - Part 2

  • cdima + 7 comments

    Pretty badly described algorithm, needs a better description of the steps.

    • lk00100100 + 0 comments
      [deleted]
    • lk00100100 + 12 comments

      You can sort of follow this GIFFY

      https://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif

      • krishna3317 + 0 comments

        Thanks it helped me

      • surya_palla1 + 0 comments

        thank u , it helped me.

      • dlgustlr45 + 0 comments

        Thank you very much!!

      • Lundii + 0 comments

        Thanks. Very helpful.

      • mohansai01234 + 0 comments

        thanks bro. it helped me a lot

      • wqian + 0 comments

        Thank you! It helped me!

      • mikelee89 + 0 comments

        Thank you , helped a lot!

      • adamxtokyo + 0 comments

        Thanks, that helped a lot. Here's my Javascript implementation of that gif lol =P

        function insertionSort2 (n, arr) {

    let storage
    for (let i = 1; i < n; i++) {
        storage = arr.splice(i, 1)[0]

        for (let j = i; j >= 0; j--) {
            if (storage > arr[j-1] || j === 0) {
                arr.splice(j, 0, storage)
                break
            }
        }

        console.log(arr.join(' '))
    }
}
      • yaroverg + 0 comments

        The GIFY was great

      • yashdeepagarwal + 0 comments

        Thank you. Helped alot!

      • akshay_goyal1008 + 0 comments

        thanks for the giffy

      • reachout2amit + 0 comments

        Discription for algo is not good. It wasted lots of my time. Got clarification from this giffy. Thank you so much for posting this.

    • sshivasurya + 1 comment

      https://github.com/shivasurya/cc150/blob/master/sorting/insertions%20sort/C%20lang/insertion.c

      check this with algorithm description

      • wqian + 0 comments

        Wow, thank you for sharing! It helped me!

    • duniya_ke_neta + 1 comment
      [deleted]
      • alison_thaung + 2 comments

        Here's another, slightly condensed Python3 solution

        s = int(input().strip())
ar = [int(temp) for temp in input().strip().split(' ')]

def insertionSort(ar, i):
    new = sorted(ar[:i+1]) + ar[i+1:]
    return ' '.join(str(k) for k in new)

for i in range(1, s):
    print(insertionSort(ar, i))
        • kerryjones21 + 0 comments

          Using an in-built sort function defeats the purpose of learning sorting algorithms...

        • aakritigupta110 + 0 comments

          coooooollll..... u are a true coder....

    • formiaczek + 3 comments

      agreed, it's a shame that it assumes some iterations that print the array even if nothing was moved, i.e.:

      Input
6
1 4 3 5 6 2

Expected Output

1 4 3 5 6 2
1 3 4 5 6 2
1 3 4 5 6 2
1 3 4 5 6 2
1 2 3 4 5 6

      And solutions like:

      void insertion_sort(vector<int> values)
{
    print_values(values);
    
    while(true)
    {
        auto what = std::adjacent_find(values.begin(), values.end(), std::greater<int>());
        if(what == values.end())
        {
            return;
        }

        auto last = what+1;
        auto v = *last;
        auto tmp = *last;
        
        auto where = std::lower_bound(values.begin(), what, v);
        for(auto x = last; x != where; --x)
        {
            auto prev = x-1;
            *x = *prev;
        }
        *where = tmp;
        print_values(values);
    }
}

      that are insertion sort, would print it only when it actually changed, i.e.:

      Your Output (stdout)

1 4 3 5 6 2 
1 3 4 5 6 2 
1 2 3 4 5 6
      • BALYAM_muralidh2 + 1 comment
        static void insertionSort2(int n, int[] arr) {
        // Complete this function
       
     for(int k=0;k<arr.length-1;k++){
         for(int i=0;i<arr.length-1;i++){
          int key = arr[k+1];
             if(i==k+1)
                 break;           
             if(arr[i]>key){
                 arr[k+1]=arr[i];
                 arr[i]=key;
             }
         }
         for(int i=0;i<arr.length;i++)
         {
         System.out.print(arr[i]+" ");
     } 
         System.out.println();
     }
    }
        • Pheonixevolution + 0 comments

          thanks it helped me !

      • atript + 0 comments

        i think the idea is that they can check whether you have implemented the algorithm right. that is more accurately tested when all iterations and exchanges are recorded.This is not about efficiency, its about learning.

      • facitoo + 0 comments

        dude! thats heck of a complex solution!

    • billchenxi + 0 comments

      I agreed, why do we have to print out in that weird way???

    • darmuneeb322 + 0 comments

      The problem seems to be designed in a very bad way.But after finally solving it you kindof get the idea what insertion sort does at every step.