Showing posts with label Array. Show all posts
Showing posts with label Array. 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 

Friday, December 27, 2013

Given an array of integers(+ve,-ve,0 or duplicates). Find n print all triplets such that a+b+c=0

/**
   * Given an array of integers(+ve,-ve,0 or duplicates). Find n print all triplets such that a+b+c=0.
   * e.g. Let A = -1 0 9 5 -5 2 3
   * Answer = {0 5 -5} {-5 2 3}.
   * Expected : Time O(n2) Space O(1)
 */
public class Prob3Sum {

    public void find3Sum(int A[]){
        for(int i=0; i<A.length; i++){
            int l = i+1;
            int r = A.length - 1;
            while(l<r){
                if(A[i] + A[l] + A[r] == 0){
                    System.out.println("Sum: " + A[i] + " " + A[l] + " " + A[r]);
                }
                if(A[i] + A[l] + A[r] > 0)
                    r--;
                else
                    l++;
            }
        }
    }
   
    public static void main(String args[]){
        QuickSort sort = new QuickSort();
        sort.A = new int[]{-1, 0, 9, 5, -5, 2, 3};
        sort.quickSort(sort.A, 0, sort.A.length-1);
        sort.printArr();
       
        Prob3Sum ps = new Prob3Sum();
        ps.find3Sum(sort.A);
       
    }
}

#output
Sorted: -5, -1, 0, 2, 3, 5, 9, 
Sum: -5 0 5
Sum: -5 2 3

Saturday, December 21, 2013

Stack using Array

public class Stack {
    int stack[] = new int[100];
    int top = 0;
    //int ssize = 0;
   
     public void printPop(){
         System.out.println("Poppoed " + this.pop());
     }
   
    public static void main(String args[]){
        Stack s = new Stack();
        s.push(10);
        s.push(15);
        s.push(20);
        s.push(25);
        s.printStack();
        s.printPop();
        s.printPop();
        s.push(19);
        s.push(24);
        s.printStack();
        s.printPop();
        s.printPop();
        s.printPop();
        s.printPop();
        s.printStack();
    }
   
    public void push(int p){
        if(top < stack.length){
            stack[top++] = p;
        }
        //System.out.println("Top: " + top);
    }
   
    public int pop(){
        int p = -99999;
        if(top > 0)
            p = stack[--top];
        //System.out.println("Top: " + top);
        return p;
    }
   
    public void printStack(){
        System.out.print("Stack [LIFO order]: ");
        for(int i=this.top-1; i>=0; i--){
            System.out.print(stack[i] + " ");
        }
        System.out.println();
    }
}