SortArrayWith123.java

import java.util.Arrays;
import java.util.List;

/**
 * Sort an array of 0s, 1s and 2s in a single pass
 * (1,0,2,1,0,2,1,0,2);
 * (0,1,2,1,0,2,1,0,2);
 *
 */
public class SortArrayWith123 {

    static void sortArray(List<Integer> input){
        int count1 = 0;
        int count0 = 0;
        int count2 = 0;
        for (Integer integer : input) {
            if (integer == 0) {
                count0++;
            } else if (integer == 1) {
                count1++;
            } else if (integer == 2) {
                count2++;
            }
        }
        for (int i = 0; i < count0; i++) {
            input.set(i, 0);
        }
        for (int i = count0; i < count1+count0; i++) {
            input.set(i, 1);
        }
        for (int i = count0+count1; i < count1+count0+count2; i++) {
            input.set(i, 2);
        }
        for (int i =0; i<input.size();i++){
            System.out.print(input.get(i)+" ");
        }
    }
    static void sortSingleLoop(List<Integer> input){
        int low = 0;
        int mid = 0;
        int high = input.size() - 1;
        // Single loop pass using Dutch National Flag algorithm
        while (mid <= high) {
            if (input.get(mid) == 0) {
                // Swap arr[low] and arr[mid]
                swap(input, low, mid);
                low++;
                mid++;
            } else if (input.get(mid) == 1) {
                mid++;
            } else if (input.get(mid) == 2) {
                // Swap arr[mid] and arr[high]
                swap(input, mid, high);
                high--;
            }
        }
        for (Integer integer : input) {
            System.out.print(integer + " ");
        }
    }
    private static void swap(List<Integer> input, int i, int j) {
        int temp = input.get(i);
        input.set(i, input.get(j));
        input.set(j, temp);
    }
    public static void main(String[] args){
        List<Integer> list = Arrays.asList(1,0,2,1,0,2,1,0,2);
//        sortArray(list);
        sortSingleLoop(list);
    }
}