# CodeChef Easy Problem: Turbo Sort

Here’s the problem:

————-

Given the list of numbers, you are to sort them in non decreasing order.

Input

t – the number of numbers in list, then t lines follow [t <= 10^6]. Each line contains one integer: N [0 <= N <= 10^6] Output

Output given numbers in non decreasing order.
Example

Input:
5
5
3
6
7
1
Output:
1
3
5
6
7
—————–

As you probably can guess the main challenge here is the speed at which you can process and sort the input. My solution was to simply create an empty array, and increment each position according to the numbers that were given as input. After that I would only need to traverse the array once outputing all the respective numbers. It worked.

``````#include <stdio.h>

int array = {0};

int main(){
int i,j;
scanf("%d",&j);
int x;

for (i=0;i<j;i++){
scanf("%d",&x);
array[x]++;
}

for (i=0;i<1000001;i++){
while(array[i]>0){
printf("%dn",i);
array[i]--;
}
}

return 0;
}``````

## 8 thoughts on “CodeChef Easy Problem: Turbo Sort”

1. shubham

I am not understanding the working of following code:
for (i=0;i<j;i++){
scanf("%d",&x);
array[x]++;
}
will u please explain how array[x]++ is working here.

1. shubham

Oh! i got it
it is just increasing the indices value….

1. pushpak

without swapping how did it worked.
and reversing it didn’t get that?

2. gautam

1. Won’t there be garbage values to some values for ‘x’? if the value is not inputted?
2. what if a number occurs twice ?

3. narendra jaggi

You’ve got to be kidding me!!! Tried with merge sort quick sort,Java’s inbuilt sort but it didn’t worked!!
Finally solved that too with easiest solution I can think of. Taken only 2.12 secs when the limit is 5 secs

4. Nikhil Khetan

I tried doing the same thing in cpp, but its not working.

#include
using namespace std;
int main(){
int A={0};
int n;
cin >> n;
int a;
while(n–){
cin >> a;
A[a]= A[a]+1;
}
int i=0;
while(i0){
cout << i << endl;
A[i]–;
}
i++;
}
return 1;
}

1. avishek

use scanf and printf instead of cin and cout

5. Ankit Verma

This code is good for quickly sorting values but this code fails when two or more same elements are entered in the array so don’t rely on this code take use of merge or heap sort