How to optimize this code(Counting Sort)

Question

I was trying to solve classic count sort problem. my o/p is right, but the time limit exceeded.How can I optimize the below code. I'm under memory limit.

Time Limit: 5 sec Source Limit: 50000 Bytes

class TurboStart {
    static int integerArray[] = new int[1000001];

    public static void main(String[] args) throws NumberFormatException,
            IOException {
        int  i, j;
        BufferedReader reader = new BufferedReader(new InputStreamReader(
                System.in));
        j = Integer.parseInt(reader.readLine());

        while (j-- > 0) {
            integerArray[Integer.parseInt(reader.readLine())]++;
        }

        for (i = 0; i < 1000001; i++) {
            while (integerArray[i]-- > 0) {
                System.out.println(i);
            }

        }
    }
}

You might want to check your output loop, too: for frequent values, you are not only accessing the count array, but converting the count to digits over and again. — greybeard
– greybeard, Commented Nov 12, 2014 at 10:18

Ivaylo Strandjev · Accepted Answer · 2014-11-12 10:05:13Z

1

Don't use System.out.println but some smarter way of writing the output(BufferedWriter?). Your code for the sort is good so the bottleneck should be the I/O(which is often problem with Java on programming competitions).

answered Nov 12, 2014 at 10:05

Ivaylo Strandjev

71.4k18 gold badges130 silver badges183 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Key_coder Over a year ago

Work like a charm thanks a ton @Ivaylo Strandjev its was I/O problem

Collectives™ on Stack Overflow

How to optimize this code(Counting Sort)

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related