Insertion Sort - Part 2

  • + 4 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