Insertion Sort - Handling empty list

Question

I'm trying to implement insertion sort using stl and vectors. I came up with this solution so far:

void insertionSort(vector<int> &v, int splitIndex);

int main() {

    //vector<int> x = {55,33,99,11,22,44};
    //vector<int> x = {55};
    //vector<int> x = {55,11};
    vector<int> x;

    insertionSort(x, 0);

    printVector(x);

    return 0; }

void insertionSort(vector<int> &v, int splitIndex) {

    vector<int>::iterator right = v.begin() + splitIndex + 1;

    if(right == v.end())
        return;

    vector<int>::iterator left = v.begin() + splitIndex;

    while(*right < *left && right != v.begin()) {
        iter_swap(right, left);
        right--;
        left--;
    }

    insertionSort(v, splitIndex+1); }

It's working on all cases except for the empty vector case because the "right" pointer will be pointing outside the vector limit. I know it can be fixed by adding a condition on the beginning:

if(v.size() < 2) return;

But I don't like that tis condition will be executed for every recursion call.

Please advice. Thanks.

I guess you can simply check if `splitIndex +1 < v.size()` at the begging of your sort function and remove `right == v.end()` checking. — JustRufus, Feb 26 '17 at 13:25
After your attempt [take a look at an implementation here](http://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c) — PaulMcKenzie, Feb 26 '17 at 15:18

Vlad from Moscow · Accepted Answer · 2017-02-26T14:45:04.477

In general this statement

vector<int>::iterator right = v.begin() + splitIndex + 1;

can result in undefined behavior particularly when the vector is empty.

This loop

while(*right < *left && right != v.begin()) {
    iter_swap(right, left);
    right--;
    left--;
}

also can have undefined behavior because before comparing the dereferenced iterators *right < *left you should at first be sure that right != v.begin(). Otherwise the iterator left will be outside the valid range of iterators for the vector.

I am suggesting the following function definition

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

void insertionSort( std::vector<int> &v, std::vector<int>::size_type i = 0 )
{
    if ( i < v.size() )
    {
        auto right = std::next( v.begin(), i );
        auto left = right;

        for ( ; right != v.begin() && *right < *--left; --right ) 
        {
            std::iter_swap( right, left );
        }

        insertionSort( v, i + 1 );
    }
}


int main() 
{
    std::vector<int> v0;
    std::vector<int> v1 = { 55 };
    std::vector<int> v2 = { 55, 11 };
    std::vector<int> v3 = { 55, 33, 99, 11, 22, 44 };

    insertionSort( v0 );

    std::cout << "v0:";
    for ( int x : v0 ) std::cout << ' ' << x;
    std::cout << std::endl;

    insertionSort( v1 );

    std::cout << "v1:";
    for ( int x : v1 ) std::cout << ' ' << x;
    std::cout << std::endl;

    insertionSort( v2 );

    std::cout << "v2:";
    for ( int x : v2 ) std::cout << ' ' << x;
    std::cout << std::endl;

    insertionSort( v3 );

    std::cout << "v3:";
    for ( int x : v3 ) std::cout << ' ' << x;
    std::cout << std::endl;

    return 0;
}

The program output is

v0:
v1: 55
v2: 11 55
v3: 11 22 33 44 55 99

score 0 · Answer 2 · answered Feb 26 '17 at 12:57

what if you'll create a starting method, which will check the array size, and only if larger than 2, will call the original method:

insertionSort(x);

which will be implemented as:

void insertionSort(vector &v){
    if(v.size() < 2) return;
    insertionSort(v, 0);
}

Insertion Sort - Handling empty list

2 Answers2