Challenge: Sort Three Colours

Lab Java Intermediate 20 points

A row of balls is coloured 0 (red), 1 (white) or 2 (blue). Sort them in one pass without counting and without a sort method: keep a low pointer for the next red spot, a high pointer for the next blue spot, and a mid pointer that walks.

Input

Line 1: n. Line 2: n numbers, each 0, 1 or 2.

Output

The sorted numbers.

Example

Input

6
2 0 2 1 1 0

Output

0 0 1 1 2 2

Sample input available Sample output available

Editor

Java

Hints

0 → swap with low, move low and mid. 1 → just move mid. 2 → swap with high, move high only.

Loop while mid <= high.

Solution explanation

This is the “Dutch national flag” algorithm: O(n) time, O(1) memory, one pass.

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        int low = 0, mid = 0, high = n - 1;
        while (mid <= high) {
            if (a[mid] == 0) {
                int t = a[low]; a[low] = a[mid]; a[mid] = t;
                low++;
                mid++;
            } else if (a[mid] == 1) {
                mid++;
            } else {
                int t = a[high]; a[high] = a[mid]; a[mid] = t;
                high--;            // don't move mid: the swapped-in ball is unchecked
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) sb.append(i > 0 ? " " : "").append(a[i]);
        System.out.println(sb);
    }
}

Output

Answer