CareerCup

i don think there's any sorting technique in O(n) time

counting sort

i don think there's any sorting technique in O(n) time

i don think there's any sorting technique in O(n) time

Use any "Non-comparison sorts" (see wiki)

static void sortUnsortedArray()
{
int[] arr = new int[] { 1,3,2,1,6,45,6,7,3,67,43,499,9 };
int i=0, j=0, count = 0;
int[] tempArr=new int[500];
for (i = 0; i < arr.Length - 1; i++)
{
j = arr[i];
tempArr[j] = tempArr[j] + 1;
}

arr = new int[12];
int intAdd=0;
for (i = 0; i < tempArr.Length; i++)
{
if (tempArr[i] > 0)
{
count = tempArr[i];
while (count != 0)
{
arr[intAdd] = i;
count -= 1;
intAdd += 1;
}
}
}
}

Please correct this answer if any deviation.

Bucket sort should work

counting sort ,

what about using hashing technique ?

Hash the elements into a table.. Since there are duplicate values, associate a counter with each hash entry.. if there is a collision, increment the counter.. Once done (O(n)), read the table entry sequentially and multiply by counter and display the number that many number of times..

But, the precondition to produce expected result by reading table entries sequentially is that the entries are sorted. Your solution shows no magic how it will happen without a non-linear sorting process involved.

1. set the appropiate bits in a bit array
2. print the array index whoes bit is set.

Why not create build a multimap from the elements and print it out. I think keys in the map data structure are sorted??

Following are the steps to solve it in O(n):

1) Create a BST for the array
2) do inorder traversal

Please correct me if I am wrong

@jay - The best insert complexity for any "balanced" tree is min O(log n) amortized...and unbalanced BST has worst case O(n)...so your solution wont be O(n)...it might be worst case O(N^2) itself...
only counting sort/bucket sort would be O(n) worst case..

BTW its not written in question that we need worst case complexity?

In my opinion, Radix sort is good enough for this question...

Radix sort will do it in O(kn) where k = max possible no. of digits in an element.
for the example case-
1 1 1 2 2 4 444 44 5 5 45 45 6
1 1 1 2 2 4 4 5 5 6 444 44 45 45
1 1 1 2 2 4 4 5 5 6 44 45 45 444
Each of the above three steps takes O(n)
So the total time complexity becomes O(3n) which is basically O(n)

I guess it is radix sort, which in this case is O(3n).

Counting sort works. Keep a bit vector representing the values and hash the count in hash table. Then check bit vector and pull count from hash table and print the number as many times as count.

OK, there are lot of misinformation with the comments and answer. First thing you need to know is that any kinda comparison sorting algorithm you pick will have a lower bound of O(nlogn), you cant do any better than that.

In that case, you will need to use bucket sort, count sort or radix sort. Which will amortize O(n) solution. I see answers like O(3n), there is no such notion in algorithm.

O(n) == O(3n)== O(100n). there are all same. linear time.

So the answer is non comparison sorting algorithms.

Easy answer would be, I find the max element and then create a dictionary from 0 to max.

Keys will be the sequence from 0 to max, and values would be the occurences.

At the end, you traverse the dictionary once and voila.

The answer is "Spaghetti Sort" which is possible using quantum computing. Check the wikipedia page (I can't paste the links here)

I couldn't find any implemetation of Spaghatti sort.

if the range is known then we can imlement this o(n) time
but if the ange is not given and can be go beyond the range of machine then no easy to to do better than the normal agorithm like 0(nlgnn) do in heap sort and merge sort or average case of quick sort

As a lot of people already said.. there's no comparison sorting algorithm having a worst case running time better than O(nlgn). Out of the Linear time Sorting algorithms, in this particular case, Radix Sort is best suited !!

They say that in O(n) and it is only for integer. So we can the following:
int[] unsorted; //here is the input
int[] output;
int[] tmp;

int min=FindMax(unsorted);//O(n)
int max=FindMin(unsorted);//O(n)
int length=Math.Abs(max-min)
output=int[length];
tmp=int[unsorted.length];
for(int i=0;i<length;i++)//O(n)
{//Initializing
tmp[i]=0;
}
int inp;
for(int i=0;i<length;i++)//O(n)
{//Using the value as an index
inp=input[i];
tmp[inp-min]+=1;
}
int index=0;
int j=0;
for(int i=0;i<length;i++)//O(n)
{
if(tmp[i]!=0)//No occurrences
{index=0;
while(index<tmp[i])
{
output[j]=i-min;
j++;
index++;
}
}
//The final anwser is in output
//O(5n)==O(n)
}

I think radix sort would be the best. As its complexity is O(N*d) where d is negligible as compared to N.
Here is the implementation.

#include <stdio.h>
#include <limits.h>
#include <math.h>
 
int findMaxDigit(int *arr,int size)
{
        int i,max=INT_MIN,n=0;
        for(i=0;i<size;i++)
                if(arr[i]>max)
                        max=arr[i];
        
        while(max)
        {
                n++;
                max/=10;
        }
        return n;
}
 
int isEmpty(int *r,int j)
{
        return r[j]==-1;
}
 
void Enqueue(int (*Q)[10],int *f,int *r,int digit,int n)
{
        if(f[digit]==-1)
                f[digit]++;
        Q[++r[digit]][digit]=n;
}
 
int Dequeue(int (*Q)[10],int *f,int *r,int digit)
{
        int n=Q[f[digit]][digit];
        if(f[digit]==r[digit])
                f[digit]=r[digit]=-1;
        else
                f[digit]++;
        return n;
}
 
void radixSort(int *arr,int size)
{
        int i,j,k,Q[size][10],f[10],r[10],d,digit,top=-1;
        
        d=findMaxDigit(arr,size);
 
        for(i=0;i<size;i++)
                f[i]=r[i]=-1;
 
        for(i=0;i<d;i++)
        {
                for(j=0;j<size;j++)
                {
                        digit=(arr[j]/pow(10,i));
                        digit%=10;
                        Enqueue(Q,f,r,digit,arr[j]);
                }
                top=-1;
                for(j=0;j<10;j++)
                {
                        while(!isEmpty(r,j))
                                arr[++top]=Dequeue(Q,f,r,j);
                }
        }
        for(i=0;i<size;i++)
                printf("%d ",arr[i]);
}
 
int main()
{
        int arr[]={4,2,6,1,5,5,1,2,45,444,44,45,4,1};
 
        radixSort(arr,sizeof(arr)/sizeof(arr[0]));
 
        return 0;
}

simple

int[] Unsorted_integer = { 4, 2, 6, 1, 5, 5, 1, 2, 45, 444, 44, 45, 4, 1 };
Array.Sort(Unsorted_integer);