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[1000001] = {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.

    Reply
  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 ?

    Reply
  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

    Reply
  4. Nikhil Khetan

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

    #include
    using namespace std;
    int main(){
    int A[1000001]={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;
    }

    Reply
  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

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *