Pages

Tuesday, June 10, 2014

Sort array containing only 0, 1 & 2 in Complexity O(n)

Java Implementation -
public class SortArrayContaining012Only {

    public static void main(String[] args) {
        int arr[] = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 };
        int arr_size = arr.length;
        sort012(arr, arr_size);
        System.out.println("Sorting done");
    }

    private static void sort012(int a[], int arr_size) {
        int lo = 0;
        int hi = arr_size - 1;
        int mid = 0;

        while (mid <= hi) {
            switch (a[mid]) {
            // swap lo and mid
            case 0:
                int temp = a[mid];
                a[mid] = a[lo];
                a[lo] = temp;
                lo++;
                mid++;
                break;
            case 1:
                mid++;
                break;
            // swap mid and high
            case 2:

                temp = a[mid];
                a[mid] = a[hi];
                a[hi] = temp;
                hi--;
                break;
            }
        }
    }
}