3
\$\begingroup\$

The task I'm solving is:

  1. Sort a list by its keys
  2. Print out the corresponding values on one line separated by whitespace
  3. Replace the values of the first half of the input to "-"
  4. Use Counting Sort

The following code works, but times out when given 1 million entries:

public class Solution {

static String[] countingSort(String[][] arr) {
    String[] result = new String[arr.length];
    int[] count = new int[100];
    for(int i=0;i<arr.length;i++) {
        count[Integer.parseInt(arr[i][0])]++;
    }
    for(int i=1;i<count.length;i++) {
      count[i] += count[i-1];
    }
    for(int i=arr.length-1;i>=0;i--) {
        result[count[Integer.parseInt(arr[i][0])]-1] = arr[i][1];
        count[Integer.parseInt(arr[i][0])]--;
    }
    return result;
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    String[][] arr = new String[n][2];
    for(int a0 = 0; a0 < n; a0++){
        int a = in.nextInt();
        arr[a0][0] = Integer.toString(a);
        if(a0<n/2) {
            String s =in.next();
            arr[a0][1] = "-";
        } else {
            String s = in.next();
            arr[a0][1] = s;
        }
    }
    in.close();
    String[] result = countingSort(arr);
    for(int i=0;i<result.length;i++) {
        System.out.print(result[i]+" ");
    }
}
  1. input is being put into 2 dimensional array. values are being replaced with "-" for first half of the values. [array: arr]
  2. Array is passed to method [array: arr, method: countingSort]
  3. New array of size 100 is being created as the keys are 0 < key < 100 [array: count]
  4. occurrences of each key are added in the newly created array [array: count]
  5. values of the array are being accumulated [array: count]
  6. the values of the corresponding key are being sorted into the result array according to the count array.
  7. result is being returned.

Particular concerns:

  1. How can the code be improved in order to increase performance and avoid timeout using counting sort?
  2. Are there any other possibilities (sorting algorithms) which have higher performance (can solve the problem faster)?
\$\endgroup\$
1
\$\begingroup\$

Algorithm is ok, and there is nothing faster than counting sort. You just need to use single System.out.print:

StringBuilder sb = new StringBuilder();
for (int i = 0; i < result.length; i++) {
    sb.append(result[i]).append(" ");
}
System.out.print(sb.toString());

It is faster than many separate calls;

\$\endgroup\$
  • \$\begingroup\$ thanks a lot! :) it worked! Why is it faster though? Unfortunately, i dont understand the reason \$\endgroup\$ – hooni Feb 15 '18 at 19:39
  • \$\begingroup\$ Part of speedup comes from using StringBuffer instead of plain String concat for result[i]+" ". Compiler often does it on its own, but not in loops. also System.out is a java.io.PrintStream and there is a synchronized block and buffer flushing inside write() method (called by print()). \$\endgroup\$ – user158037 Feb 16 '18 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.