Sorting as we give input

[prodicus]

Like I have input in range of 0-10^6. So first storing the integers(again in the range 0-10^6) and then sorting will certainly take a lot of time.

I was wondering whether we can sort on the go(like as the user is giving the data by standard input) and we are sorting it.


I don't want to use any standard library for this just yet(if there is any, it would be kind of you to point out).
I am certainly baffled by this problem, any help would be appreciated guys.

[MiiNiPaa]

I don't want to use any standard library for this just yet

There is only one standard library. Just FYI.

You need an online sorting algorithm.
Insertion sort would be easiest to implement: http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/insertion-sort/

If you feel confident in your abilitiesm you can try to implement online mergesort: http://en.wikipedia.org/wiki/Merge_sort#Utility_in_online_sorting

[helios]

Inserting sorted adds more total time than sorting the entire sequence in one go. The former takes O(n^2) with insertion sort and O(n log n) with balancing trees (but a relatively slow n log n). Sorting an array takes a very fast O(n log n).
Don't do it unless you specifically need the sequence to maintain order as it's populated.

That said, the particular sorting algorithm is probably irrelevant if we're talking about sorting input that a user has to manually type in.

[S G H]

If you could use the standard library:

#include <map>
#include <iostream>

int main()
{
    std::map<int,unsigned int> items;
    int input;
    while(std::cin >> input) {
        ++items[input];
        for(std::map<int,unsigned int>::iterator it = items.begin(); it != items.end(); ++it)
        {
            std::cout << "value" << it->first << "has been inserted" << it->second << "times" << std::endl;
        }
    }
    return 0;
}

[prodicus]

@MiiNiPaa Sorry, what I meant was that I don't want to use inbuilt functions just yet.

[JLBorges]

0-10^6 is way too small a range for this to be a real problem:

#include <iostream>

int main()
{
    const unsigned int SZ = 1000001 ; // 0 - 10^6
    static unsigned int bucket[SZ] = {0} ;

    unsigned int number ;
    while( std::cin >> number ) ++bucket[ number%SZ ] ;

    for( unsigned int num = 0 ; num < SZ ; ++num )
    {
        const unsigned int cnt = bucket[num] ;
        for( unsigned int i = 0 ; i < cnt ; ++i ) std::cout << num << ' ' ;
    }
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/026de0d3b191aa55