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. Prepare
  2. Algorithms
  3. Sorting
  4. Insertion Sort - Part 2
  5. Discussions

Insertion Sort - Part 2

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