Insertion Sort : C++ implementation 100 times slower than C implementation

From:

sanket <sanketsharma09@gmail.com>

Newsgroups:

comp.lang.c++

Date:

Sun, 30 Oct 2011 22:40:18 -0700 (PDT)

Message-ID:

<f39210e6-d052-4f82-a619-d767983cbb07@v5g2000vbh.googlegroups.com>

Hello everyone,

I implemented the insertion sort algorithm in C and C++ and tried
comparing the performance.

Here are the implementations
1. C++

# include<iostream>
# include<vector>
# include<iterator>
# include<algorithm>
# include<cstdlib>
#include <boost/progress.hpp>

using namespace std;

typedef std::vector<int> t1;

void insertionsort(t1& vin)
{
    t1::iterator it1;
    t1::iterator it2;
    t1::iterator begin = vin.begin();
    t1::iterator end = vin.end();
    for(it1 = begin + 1; it1 != end; it1++)
    {
        int key = *it1;
        it2 = it1 - 1;
        while(*it2 > key && it2 >= begin ) { *(it2+1) = *it2; it2--;}
        *(it2 + 1) = key;
    }

    return;

}

int main(int argc, char* argv[])
{
    if(argc != 2){cout << "Usage:\na.out <number of elements>" << endl;
exit(-1);}

    int b = 0;
    int n = atoi(argv[1]);

    t1 v;
    v.reserve(n);
    for(int i=0; i < n; i++) { b = rand(); v.push_back(b);}
    t1 &vin = v;

    /*
    std::cout<< "Unsorted Array"<< std::endl ;
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, "
"));
    std::cout<< std::endl ;
    */

    boost::progress_timer howlong;
    insertionsort(vin);
    /*
    std::cout<< "Sorted Array"<< std::endl ;
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, "
"));
    std::cout<< std::endl ;
    */

    return 0;
}

2. C

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <boost/progress.hpp>

void insertionsort(int* a, int n)
{
    int i, j;
    int key;
    for(i= 0; i < n; i++)
    {
        key = a[i+1];
        j = i ;

        while(a[j] > key && j >= 0) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;
    }
}

int main(int argc, char** argv)
{
    int n = atoi(argv[1]);
    int * a = (int*)malloc(n * sizeof(int));
    int i = 0;

    for(i = 0; i < n; i++)
    {
        a[i] = rand()%100;
    }

    boost::progress_timer howlong;
    insertionsort(a, n);
    /*
    for(i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    */
    printf("\n");
    return 0;
}

Here are the performance results:

Number of integer elements C implementation C++ implementation
10000 0.16 s
1.17 s
100000 16.69 s
116.16s

I compiled both programs using g++ compiler and used boost to measure
the time elapsed.

This is shocking to me, since C++ should be close to C in performance.
Why is the C++ implementation 100 times slower?

Thanks,
Sanket