QuickSort on an Array

Implement a QuickSort on an Array

public class QuickSort {

   

    int partition( int[] in ) {

        if ( in.length == 1) return 0;

   

        if ( in.length == 2 ) {

            if ( in[0] > in[1]) {

                swap(in , 0 ,1);

                return 1;

            }else if( in[0] == in[1])

                return 1;

            else return 0;

               

        }

       

        int pivot = in[0];

        int down = 1;

        int up = in.length - 1;

        int ele = -1;

       

        while ( up > down ) {

            // move down pointer

            while( in[down] <= pivot && down < in.length -1)

                ++down;

                   

            while( in[up] > pivot && up > 0)

                --up;

               

            if ( up > down) {

                swap(in, down, up);

                ele = down;

               

                ++down;

                --up;

            }

        }

        if ( in[up] > pivot) {

            swap(in, 0, ele);

        }else{

            swap(in, 0, up);

            ele = up;

        }

        return ele;

    }

   

    private void swap( int[] in, int lb, int ub ) {

        int tmp = in[lb];

        in[lb] = in[ub];

        in[ub] = tmp;

    }

   

    void print(int[] in) {

        for( int i: in )

            System.out.println(i);

    }

   

    public static void main( String[] args ) {

       

        int[] in = new int[] {57,25, 36, 69, 22, 99, 48, 98, 88, 79, 62 };

       

        int[] in1 = new int[] {25, 22, 21, 23, 24 };

       

        int[] in2 = new int[] { 21, 24, 26, 28, 49 };

       

        int[] in3 = new int[] { 25, 57, 48, 37, 12, 92, 86, 33};

       

        int[] in4 = new int[]{2,1,3,-2,0};

       

        int[] in5 = new int[]{2,1,0,6,-7};

       

        int[] in6 = new int[]{25,35,49,50,21,22,25};

       

        int[] in7 = new int[]  {2,1,2};

       

        int[] in8 = new int[]  {2,2};

       

        QuickSort sort = new QuickSort();

   

        System.out.println("--------------------");

       

        System.out.println(sort.partition(in));

        sort.print(in);

       

        System.out.println("-------------------------------");

        System.out.println(sort.partition(in1));

        sort.print(in1);

   

        System.out.println("-------------------------");

        System.out.println(sort.partition(in2));

        sort.print(in2);

       

        System.out.println("-------------------------------");

        System.out.println(sort.partition(in3));

        sort.print(in3);

       

        System.out.println("-------------------------------");

        System.out.println(sort.partition(in4));

        sort.print(in4);

       

        System.out.println("----------------------");

        System.out.println(sort.partition(in5));

        sort.print(in5);

       

        System.out.println("-------------------------");

        System.out.println(sort.partition(in6));

        sort.print(in6);

       

        System.out.println("---------------------------");

        System.out.println(sort.partition(in7));

        sort.print(in7);

       

        System.out.println("---------------------------");

        System.out.println(sort.partition(in8));

        sort.print(in8);

       

       

    }

}

implement a Queue from Two Stacks

Implement a Queue from Two Stacks

Below is a java program to Implement a Queue from two Stacks

public class QueueFromStack {

   

    Stack pushStack = new Stack();

    Stack otherStack = new Stack();

    int front = -1;

    int rear = -1;

   

    void queue(int val ) {

        pushStack.push(val);

    }

   

    boolean isEmpty() {

        return pushStack.isEmpty();

    }

   

    int dequeue() {

        int dequeuedVal = 0;

        boolean found = false;

        while( !pushStack.isEmpty()) {

            int val = pushStack.pop();

            otherStack.push(val);

        }

        if ( !otherStack.isEmpty() ) {

            found = true;

            dequeuedVal = otherStack.pop();

        }

        while ( !otherStack.isEmpty() ) {

            int val = otherStack.pop();

            pushStack.push( val );

        }

        if ( !found )

            throw new RuntimeException("Empty Queue");

       

        return dequeuedVal;           

    }

   

    void print() {

        int bottom = pushStack.getBottom();

        int top = pushStack.top();

        while( bottom <= top )

        System.out.println( pushStack.get(bottom++) );

    }

   

    public static void main( String[] args ) {

        QueueFromStack qfs  = new QueueFromStack();

        qfs.queue(2);

        qfs.queue(3);

        qfs.queue(5);

       

        qfs.print();

       

        System.out.println("-------------------------");

        qfs.dequeue();

        qfs.dequeue();

               

        System.out.println("-------------------------");

        qfs.print();

    }

}

------------------------------------ Stack class --------------------------------------------------------

public class Stack {

    public int max_size = 20;
    private int[] stack = new int[max_size];
   
    int top = -1;
   
    void push( int val ) {
        if ( top == max_size )
            throw new RuntimeException("Stack_Overflow");
        stack[++top] = val;
    }
   
    int top() {
        return top;
    }
   
    int pop() {
        if ( top == -1)
            throw new RuntimeException( "stack_underflow" );
        return stack[top--];
    }
   
    boolean isEmpty() {
        return top == -1;
    }
   
    int peek() {
        return stack[top];
    }
   
    void clear() {
        top = -1;
    }
   
    int getBottom() {
        return 0;
    }
   
    int get( int i ) {
        return stack[i];
       
        }
}

Implement a Stack from Two Queues

Implement a Stack from Two Queues

Below is a java program to Implement a Stack from Two Queues

public class StackFromQueue {
   
    Queue pushQ = new Queue();
    Queue popQ = new Queue();
   
    void push( int val ) {
        pushQ.enqueue(val);
    }
   
    int pop() {
       
        if ( pushQ.isEmpty() )
            throw new RuntimeException("empty_queue");
       
        int front = pushQ.front();
        int rear = pushQ.rear();
       
        while ( front++ < rear ) {
            int val = pushQ.dequeue();
            popQ.enqueue(val);
        }
       
        int ret = pushQ.dequeue();
       
        Queue a = pushQ;
        pushQ = popQ;
        popQ = a;
       
        return ret;
    }
   
    void print() {
        if ( !pushQ.isEmpty() ) {
            int front = pushQ.front();
            int rear = pushQ.rear();
           
            while ( front <= rear ) {
                System.out.println( pushQ.get(front++));
            }
        }
    }
    public static void main( String[] args ) {
        StackFromQueue sfq = new StackFromQueue();
        sfq.push( 2 );
        sfq.push( 3);
        sfq.push(4);
       
        sfq.print();
       
        System.out.println("--------------------------");
       
        System.out.println(sfq.pop() );
        System.out.println(sfq.pop() );
       
        System.out.println("---------------------------");
       
        sfq.print();
       
    }

}

-------------------------------------- Queue class ------------------------------

public class Queue {
   
    final int max_size = 20;
    int[] queue = new int[ max_size];
   
    int front;
    int rear;
   
    public Queue() {
        init();
    }
   
    private void init() {
        front = 0;
        rear = -1;
    }
   
    void enqueue( int val ) {
        if ( rear == max_size - 1)
            throw new RuntimeException("overflow");
        queue[++rear] = val;
    }
   
    int dequeue() {
        if ( isEmpty() )
            throw new RuntimeException("underflow");
        int retVal =  queue[front++];
        if ( front > rear ) {
            init();
        }
        return retVal;
    }
   
    int front() {
     return front;
    }
   
    int rear() {
        return rear;
    }
   
    int get( int i ) {
        if ( i >= front && i <= rear ) {
            return queue[i];
        }
        throw new RuntimeException( "index_out_of_bounds" );
    }
   
    boolean isEmpty() {
        return rear == -1 && front == 0;
    }
   
    void print() {
        if ( !isEmpty() ) {
            int front = front();
            int rear = rear();
           
            while ( front <= rear ) {
                System.out.println( get(front++));
            }
        }
    }
   
    public static void main( String[] args ) {
        Queue q = new Queue();
        q.enqueue(2);
        q.enqueue(3);
       
        q.print();
       
        System.out.println("------------------");
       
        System.out.println(q.dequeue() );
        System.out.println(q.dequeue());
       
        System.out.println("-------------------");
       
        q.print();
       
    }

}

Merge Two Sorted Link Lists into a Third Sorted List

Merge two Sorted Linked List into a Third Linked List

Java program to Merge two sorted lists into a third list. Below program has, both a recursive and iterative version methods

public class MergeLinkList {

    private Link mergeRecursive( Link l1, Link l2 ) {

        if ( l1 == null) return l2;

        if ( l2 == null ) return l1;

       

        Link mergedhead = null;

       

        if ( l1.value() < l2.value() ) {

            mergedhead = l1;

            mergedhead.next = mergeRecursive(l1.next, l2);

        }else {

            mergedhead = l2;

            mergedhead.next = mergeRecursive(l1, l2.next);

        }

        return mergedhead;

    }

   

    private Link mergeInterative( Link  l1, Link l2 ) {

        if ( l1 == null) return l1;

        if ( l2 == null ) return l2;

       

        Link p1 = l1;

        Link p2 = l2;

       

        Link mergedHead= null;

        Link last = mergedHead;

       

        while ( p1!= null && p2 != null ) {

        if ( p1.value() < p2.value() ) {

          if ( last == null ) {

              last = new Link(p1.value());

              mergedHead = last;

          }else {

              last.next = new Link( p1.value());

              last = last.next;

          }

         p1 = p1.next;

        }else {

             if ( last == null ) {

                  last = new Link(p2.value());

                  mergedHead = last;

              }else {

                  last.next = new Link( p2.value());

                  last = last.next;

              }

             p2 = p2.next;

        }               

        }

        if ( p1 != null ) {

            insertAll( p1, last );

        }else

            insertAll( p2, last );

       

        return mergedHead;

    }

   

    private void insertAll( Link p1, Link last ) {

        do {

            last.next = new Link(p1.value());

            p1 = p1.next;

        }while ( p1 != null );

    }

   

public static void main( String[] args ) {

       

        /*

          * .................n..........n.............n.........n.............n.......................n............n..........        ---> Number line for Array1, has 8 numbers in ascend

         * .....n...n...........n......... n...n..........n.........n.................................................................... 

             * */

       

            int[] ar1 = new int[] { 45, 56, 77, 89, 150, 187, 198};

            int len1 = 7;

           

            int[] ar2 = new int[] { 23, 29, 47, 59, 67, 80, 106 };

            int len2 = 7;

           

            Link l1 = Link.build( ar1 );

            Link l2 = Link.build(ar2);

           

            MergeLinkList merge = new MergeLinkList();

            Link mergedIter = merge.mergeInterative(l1, l2);

            mergedIter.print(mergedIter);

           

            System.out.println("Prining recursively");

           

            Link mergedRecursive = merge.mergeRecursive(l1, l2);

            mergedRecursive.print(mergedRecursive);

           

           

    }

}

Sort a given List using Insertion Sort

Sort a Linked List using Insertion Sort

C++ Code to sort a given list

 

void Sort(ListNode** pHead) {
if(pHead == NULL || *pHead == NULL)
return;

ListNode* pToBeSorted = pLastSorted->m_pNext;
while(pToBeSorted != NULL) {
if(pToBeSorted->m_nValue < (*pHead)->m_nValue) {
pLastSorted->m_pNext = pToBeSorted->m_pNext;
pToBeSorted->m_pNext = *pHead;
*pHead = pToBeSorted;
}
else {
ListNode* pNode = *pHead;
while(pNode != pLastSorted
&& pNode->m_pNext->m_nValue < pToBeSorted->m_nValue) {
pNode = pNode->m_pNext;
}
if(pNode != pLastSorted) {
pLastSorted->m_pNext = pToBeSorted->m_pNext;
pToBeSorted->m_pNext = pNode->m_pNext;
pNode->m_pNext = pToBeSorted;
}
else
pLastSorted = pLastSorted->m_pNext;
}
pToBeSorted = pLastSorted->m_pNext;
}
}