Showing posts with label 2-way Partitioning. Show all posts
Showing posts with label 2-way Partitioning. Show all posts

Monday, December 30, 2013

Sort an array of 0s, 1s or 2-way Partitioning

/*
 * Sort an array of 0s, 1s
 * reference: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
 */
public class Partition2Way {
    int numArr[] = null;
   
    public Partition2Way(){
        numArr = null;
    }
   
    public Partition2Way(int n){
        numArr = new int[n];
    }
   
    public void sort2Way(int a[]){
        int low = 0;
        int mid = 0;
        int high = a.length-1;
        while(mid <= high){
            switch(a[mid]){
                case 0:
                    int t = a[low];
                    a[low] = a[mid];
                    a[mid] = t;
                    low++;
                    mid++;
                    break;
                case 1:
                    mid++;
                    break;
            }
        }
        this.numArr = a;
    }
   
    public void printArr(int a[]){
        System.out.print("Sorted List: ");
        for(int i=0; i<a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }
   
    public static void main(String args[]){
        int a[] = {0,1,1,1,0,0,1,1,0,1};
        Partition2Way pw = new Partition2Way(a.length);
        pw.sort2Way(a);
        pw.printArr(pw.numArr);
    }
}

#output:
Sorted List: 0 0 0 0 1 1 1 1 1 1