UVa 11462

From Algorithmist
Jump to navigation Jump to search

11462 - Age Sort[edit]

Summary[edit]

We have numbers (from 1 to 100) that represent certain ages, now we need to sort this ages, but in the problem statement say that the size of the input it's ~25Mb, pretty big!.
This problem is solvable with O() sorting algorithm provided in the library (qsort from stdlib.h or sort from algorithm).
Solutions implementing O(n) counting sort algorithm (explained below) and using scanf/printf for input/output clock at 0.400 to 0.600s.
Better run time can be achieved by optimizing input and output routine with fread/fwrite.

Explanation[edit]

Instead of normally put the ages in a vector of size , and apply a sort algorithm, one can store the times that appear a number in a vector of size 101 and print the solution based in how many times appeared the numbers from 1 to 100. For the second test case, we have:

[1] = 1
[2] = 2
[3] = 2
[4] = 0
[5] = 0
 .
 .
 .
[100]=0

Solutions[edit]

Input[edit]

5
3 4 2 1 5
5
2 3 2 3 1
0

Output[edit]

1 2 3 4 5
1 2 2 3 3