Print array in right order.

[Ajay]

An array was given with duplicates in random, WAP to print that in right order.
Please see example:

Given 5,12,,6,8,6,12,6,5,2
Output: 5,5,12,12,6,6,8,2

Here 12>6 but we will print 12 first because in original array 12 is before 6 for first time.

--
Ajay Kr. Gautam
Postgraduate Student,
Dept. of Computer Science & Engg., IT-BHU
Varanasi-221005, UP
India
-----------------------------------------------------------------
"Easy reading is damned hard writing."
~ Nathaniel Hawthorne

[Gaurav Kumar]

Here's a solutionf of complexity O(n log k) where k is the different numbers in the array.

 

#include<iostream>
#include<map>
using namespace std;

map <int , int> H;  
void fun(int v[],int N)
{
    int i,j;
    for (i=0;i<N;i++)
    {
        H[v[i]]++;
    }
    for (i=0;i<N;i++)
    {
        for (j=0;j<H[v[i]];j++)
            printf("%d,",v[i]);
        H[v[i]]=0;
    }
}

int main()
{
    int A[]= {5,12,6,8,6,12,6,5,2};
    fun(A,9);
}

 

But somehow i feel this complexity can be improved upon.

Gaurav Kumar

Seniour Undergraduate

Computer Science & Engineering,
Institute Of Technology,
Banaras Hindu University,
India.
Contact No:+91-9005-729-272
gaurav...@acm.org

(http://comeoncodeon.wordpress.com/ )