Search This Blog

Friday, September 25, 2015

Comparison of Sorting Algorithms Based on Execution Time

Last weekend I tried implementing various Sorting algorithms, and compared there outputs.

I ensured fair comparison of these algorithms by using same data for sorting -
1. I generated 10,000 Random numbers between from 0 to 50,000
2. Wrote output of above to a text file.
3. I used this text file as input test various sorting algorithms

Following table shows the comparison of these algorithms based on time required for sorting (it does not include time required to read and write input/ output)


Algorithm Time (in Milisecond)
Radix Sort Array Based Implementation 
*(Implemented for 5 digit numbers)
0.63
Counting Sort 
*(Implemented for numbers between 0 to 50,000)
0.792
Merge Sort
2.214
Quick Sort Non Recursive
2.266
Quick Sort Recursive
2.267
Heap Sort
3.416
Radix Sort Linked List Based Implementation  
*(Implemented for 5 digit numbers)
4.844
Insertion Sort
68.991
Shell Sort
96.15
Selection Sort
125.29
Bubble Sort 239.601


Programming Language used - C
Compiler - GCC (gcc version 4.8.4 (Ubuntu 4.8.4-2ubuntu1~14.04))



Tuesday, February 28, 2012

Inside C++ Object Model by Stanley B. Lippman

Hi Everyone, Just sharing my thoughts after reading Inside C++ Object Model by Stanley B. Lippman. This is a must read book for every C++ programmer. I liked this most after the God's (Bjarne Stroustrup's) Design and Evolution of C++. This books tells you - 1. In depth understanding of internals of Virtual functions. 2. Some compiler level details and insight to make you write great code. 3. Solid understanding of function calling mechanism and return statements. 4. At few places this book even touches the Assembly level details. If you have 3-4+ years of C++ experience then this book is must read.

Thursday, December 8, 2011

Printing different representations of a Number

Today I wanted to print Binary representations of 0 to 40... But I did not know how to do it.
I did knew few algorithms for conversion but I was looking for ready-made solution.

"itoa() is the required function"

Here is a simple C++ program in QT to print Decimal, Binary, Octal and Hex Representation of numbers 0 to 99



#include <QtCore/QCoreApplication>
#include <stdlib.h>
#include <iostream>
#include <iomanip>

using namespace std;

int main(int argc, char *argv[])
{

    QCoreApplication a(argc, argv);

    char binary_repr[12];
    char octal_repr[12];
    char hex_repr[10];

    cout << "| Decimal |  Binary  | Octal  | Hex |" << endl;
    for(int i = 0; i <=99; ++i)
    {

        _itoa_s(i, binary_repr, 2);
        _itoa_s(i, octal_repr, 8);
        _itoa_s(i, hex_repr, 16);

        cout << "|" << setw(9) <<  i
             << "|" << setw(10) << binary_repr
             << "|" << setw(8) << octal_repr
             << "|"  << setw(5) << hex_repr
             << "|" << endl;
    }
    return a.exec();
}