Sort an array of 0s, 1s and 2s in Java

Question

Write a program to sort an array of 0's,1's and 2's in ascending order.

Input:

The first line contains an integer 'T' denoting the total number of test cases. In each test cases, First line is number of elements in array 'N' and second its values.

Output:

Print the sorted array of 0's, 1's and 2's.

Constraints:

• 1 <= T <= 100
• 1 <= N <= 105
• 0 <= arr[i] <= 2

Example:

Input :

2
5
0 2 1 2 0
3
0 1 0

Output:

0 0 1 2 2
0 0 1

My approach:

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

class GFG {

    private static void printSortedArr (int[] arr) {
        int count0 = 0, count1 = 0, count2 = 0;

        for (Integer elem : arr) {
            if (elem == 0) {
                count0++;
            }
            else if (elem == 1) {
                count1++;
            }
            else {
                count2++;
            }
        }

        while (count0 != 0) {
            System.out.print(0 + " ");
            count0--;
        }

        while (count1 != 0) {
            System.out.print(1 + " ");
            count1--;
        }

        while (count2 != 0) {
            System.out.print(2 + " ");
            count2--;
        }
        System.out.println();
    }

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int numTests = Integer.parseInt(line);

        for (int i = 0; i < numTests; i++) {
            String line2 = br.readLine();
            int size = Integer.parseInt(line2);
            int[] arr = new int[size];
            String line3 = br.readLine();
            String[] inps = line3.split(" ");

            for (int j = 0; j < size; j++) {
                arr[j] = Integer.parseInt(inps[j]);
            }

            printSortedArr(arr);
        }
    }
}

I have the following questions with regards to the above code:

1. How can I further improve my approach?

2. Is there a better way to solve this question?

3. Are there any grave code violations that I have committed?

4. Can space and time complexity be further improved?

Reference

Answer 1

Descriptive names

    private static void printSortedArr (int[] arr) {

I don't like these names. I would rather write out array if that's what's being said. E.g.

    private static void printSortedArray(int[] numbers) {

Now I don't have to figure out that Arr is short for array. And numbers is more descriptive than array anyway.

Favor arrays over numbered variables

        int count0 = 0, count1 = 0, count2 = 0;

So here you have three variables that hold different values based on their names. However, we have a data type that enforces that relation, the array.

As proposed here:

    private static void printSortedArray(int[] array, int maxElement) {
        int[] counts = new int[maxElement + 1];

Now you have a more reusable method. It's no longer limited to just sorting an array of 0s, 1s, and 2s. It can sort any array of 0, ..., maxElement. Further, it is now self-organizing. Instead of

            if (elem == 0) {
                count0++;
            }
            else if (elem == 1) {
                count1++;
            }
            else {
                count2++;
            }

You can just say

            counts[element]++;

You no longer have to expand the if/else each time you add a new element value.

In a comment, you said

Isn't storing the values in an array a space overhead?

The difference between your original three variables and this array is the length variable. Other than that, both use the same space. The cost of the extra variable is more than made up with the reduction in errors from replacing the if/else monster with the simple array update.

For example, your original has a bug if the array contains numbers other than 0, 1, or 2. It silently counts any other number as a 2. The revised version would throw an array out of bounds exception in that case, and it will do so without any added checking on your part.

In another comment, you say

I thought that according to the problem statement, there was no explicit need to store the sorted elements in the array causing me to just print them. Also, I thought that using an array would be a space overhead.

In that case, the array duplicated the original array and was a space overhead. But the thing that you gain there is that you can reuse the created array for other things.

You are correct in pointing out that the current problem statement does not require separate action and display. What we are trying to tell you though is that in the real world, problem statements change. Your code is fragile. If the problem statement changes, you have to rewrite it. We want to encourage you to write robust code that will continue to work even if the goal changes. This is because the goal in a project tends to change a lot.

Donald Knuth said:

The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.

You are generally going to be better off writing for good engineering principles and then, in those rare instances where it matters, optimizing. Don't fall in love with your optimized solutions, as user requirements will stomp all over them.

What if you were asked to print out the counts for each element? You would have to modify this code to do that. However, if your method was

    // numbers can only contain values from 0 to maximumValue
    private static int[] countElementsByValue(int[] numbers, int maximumValue) {
        int[] counts = new int[maximumValue + 1];

        for (int element : numbers) {
            counts[element]++;
        }

        return counts;
    }

Then you could easily display the counts or the array. Or both. Because you have that information right there. With the original method, you would either need to rewrite it like this or recount the elements to do that display. Because the original method discards that information immediately. Or you could modify the original method. But then what happens when someone says that they want just the array without the counts?

In general, we prefer small methods that do one thing and only one thing over more complicated methods that do multiple things. This is especially true about mixing generation and display. That fails quite often, as we have found that requiring multiple displays over the same basic data is quite common. So there is a specific instance (don't mix generation and display) of the more general rule to keep difference actions separate.

Your original method might become something like

        int[] counts = countElementsByValue(numbers, 2);
        int[] sorted = expandCounts(counts);
        System.out.println(Arrays.toString(sorted));

Note how the last line doesn't have to know that it's displaying a sorted array. It doesn't care. Whatever the array is, it displays.

We could probably improve performance by writing a special display routine that works off the counts directly. But it wouldn't be that much of an improvement. And most of the time, it won't matter. With your example input, the time difference is going to be trivial. We'll spend more time compiling the program than running it.

Performance

If you're really worried about storage performance, then why read the data into an array at all?

            String line3 = br.readLine();
            String[] inps = line3.split(" ");

            for (int j = 0; j < size; j++) {
                arr[j] = Integer.parseInt(inps[j]);
            }

            printSortedArr(arr);

Could be

            for (String token : br.readline().split(" ")) {
                 char digit = token.charAt(0);
                 if (digit == '0') {
                     System.out.print("0 ");
                 } else {
                     counts[digit - '0']++;
                 }
            }

            int value = '0';
            for (int count : counts) {
                while (count > 0) {
                    System.out.print(value + " ");
                    count--;
                }

                value++;
            }
            System.out.println();

One reason not to do this is that, counter-intuitively, it is actually slower to mix input and output like this than to use more storage. In particular, System.out.print is not high performance with printing two characters at a time. You'd usually be better off using a StringBuilder to generate the string and then outputting that.

Why use readline? The resulting array could potentially be huge, and you are committing yourself to two arrays, one of strings and one of integers. Consider

            int read = br.read();
            while (read >= 0) {
                if (read != ' ') {
                    counts[read - '0']++;
                }

                read = br.read();
            }

This saves us two arrays and a string at the cost of one smaller array. If you are really space constrained, mixing input and generation like this is better than mixing generation and output.

Of course, it is quite possible that this is slower than your original. That's a common trade-off, speed for space.

Then with Java 8, you can use something like (from Stack Overflow):

            for (i = 0; i < counts.length; i++) {
                String value = Integer.toString(i);
                System.out.print(String.join(" ", Collections.nCopies(counts[i], value)));
            }
            System.out.println();

This will display with only four print statements.

Or if that uses too much space (it's unclear to me if it creates a temporary collection or not), stick to your original output method. That may be slow, but it uses very little space.

Remember though, that this kind of optimization is something you should do after you establish that you need it. Most of the time this is going to be unnecessary and it may even be counter-productive. E.g. if you're worrying about space constraints when you are actually time constrained.

Answer 2

The counting sort that you implemented is definitely the way to go. I would clean up the code a little bit, though.

Boxing elem as an Integer, then unboxing it back to an int, is unjustified.

Writing a switch statement, rather than an else if chain, produces slightly cleaner bytecode.

You've mingled the output logic with the sorting logic, which is bad practice. You should define a separate function to do the output, especially since the main() is responsible for reading the input. The sorting function should be named to suggest that it only handles 0, 1, 2 as input.

Each line of output will have a trailing space after the last number. That might cause your solution to fail some tests.

Since you call Integer.parseInt() so much, you might be better off using a Scanner.

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;

class GFG {
    private GFG() {}

    public static void sort012(int[] array) {
        int count0 = 0, count1 = 0, count2 = 0;
        for (int elem : array) {
            switch (elem) {
                case 0: count0++; break;
                case 1: count1++; break;
                case 2: count2++; break;
                default: throw new IllegalArgumentException("Not 0, 1, or 2");
            }
        }
        int i = 0;
        while (count0-- > 0) { array[i++] = 0; }
        while (count1-- > 0) { array[i++] = 1; }
        while (count2-- > 0) { array[i++] = 2; }
    }

    public static String toString(int[] array) {
        return Arrays.stream(array)
                     .mapToObj(String::valueOf)
                     .collect(Collectors.joining(" "));
    }

    public static void main (String[] args) {
        Scanner scan = new Scanner(System.in);
        int numTests = scan.nextInt(); scan.nextLine();
        while (numTests-- > 0) {
            int size = scan.nextInt(); scan.nextLine();
            String[] inputs = scan.nextLine().split(" ");

            int[] array = new int[size];
            for (int j = 0; j < size; j++) {
                array[j] = Integer.parseInt(inputs[j]);
            }

            sort012(array);
            System.out.println(toString(array));
        }
    }
}

Answer 3

That's the correct approach, and so I don't think time or space complexity can be improved significantly.

However, you could improve the re-usability of the function by using an array to store the counts, rather than individual variables.

private static void printSortedArray (int[] array, int maxElement) {
    int[] counts = new int[maxElement + 1];

    for (Integer element : array) {
        // You could check if 0 <= element < maxElement here
        counts[element]++;            
    }

    for(int i = 0; i < counts.length; i++) {
        for(; counts[i] > 0; counts[i]--) {
            System.out.print(i + " ");
        }
    }

    System.out.println();
}

Also, as changed above, there's no point to slightly abbreviating your variable and function names. The additional clarity is worth being two letters longer.

Additionally, a function like this would more typically either re-arrange the array in place, or return a separate sorted array, rather than sticking sorting and printing together. For this program it does what it needs to, but generally speaking it's good to separate your logic from your output.

Answer 4

I am a fan of concise and simple code. If Streams are already used for printing why not also do the sorting with them. In that way, converting from String to int and back is unnecessary. However, it does only work as long as you have solely single digits in the input. Another advantage is that you do not need the number of input elements 'N' separately as an input value before the actual data. That's why I am going to ignore it by putting a scan.nextLine(); at the beginning of the while loop.

This would be the complete code doing what you want then:

import static java.util.stream.Collectors.joining;
import java.util.Arrays;
import java.util.Scanner;

class GFG {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int numTests = scan.nextInt(); 
        scan.nextLine(); 
        while (numTests-- > 0) {
            scan.nextLine();
            String[] inputs = scan.nextLine().split(" ");
            System.out.println(Arrays.stream(inputs).sorted().collect(joining(" ")));
        }
        scan.close();
    }
}

Another remark: You should always close objects like the BufferedReader or the Scanner used in the other proposed solutions.

Answer 5

class GFG {
    private static void printSortedArr (int[] arr) {

"There are 2 hard problems in Computer Science: cache invalidation, naming, and off-by-1 errors." Poorly-chosen names can mislead the reader and cause bugs. It is important to use descriptive names that match the semantics and role of the underlying entities, within reason. What is GFG? Should arr already be sorted? If I just want to 3-way sort, can I do it without printing?

Keep functions simple. Functions should perform single logical operations. That enables your entities to be simpler to understand, test, and reuse.

---

            else {
                count2++;
            }
        // ...
        while (count2 != 0) {
            System.out.print(2 + " ");
            count2--;
        }

Is this true? Should an element that is neither 0 or 1 be defaulted to 2?

---

Is there a better way to solve this question? Can space and time complexity be further improved?

Depends on your use-case (measure!). Besides a 3-way counting sort, you can also 3-way partition (quicksort) that takes a pivot and partitions the array into a group that is less than, equal to, and greater than the pivot.

...
  public static void threeWayPartition(int[] array, int pivot) {
    int first = 0;
    int mid = 0;
    int last = array.length - 1;

    while (mid <= last) {
      if (array[mid] < pivot) {
        swap(array, first++, mid++);
      }
      else if (array[mid] > pivot) {
        swap(array, mid, end--);
      }
      else {
        ++mid;
      }
    }
  }

  public static void swap(int[] array, int i, int j) {
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
  }