Thursday 16 June 2016

Implementing a sorting algorithm in Jeliot tool

The sorting algorithm I chose implements Quicksort. The full program developed using the Jeliot Tool is below.

import jeliot.io.*;

public class QSort {
    private static int exchanges = 0;
    private static int array[] = {12,9,4,99,120,1,3,10,23,45,75,69,31,88,101,14,29,91,2,0,77};
    /**
     * @param args
     */
    public static void main(String[] args) {
           System.out.println("The list before sorting is:");
           printlist(array,array.length);
           qsort(array,0,array.length-1);
           System.out.println("\nThe list after sorting is:");
           printlist(array,array.length);
           System.out.println("\nThe number of exchanges is: " + exchanges);
    }
    
    public static void swap(int x,int y){
       int temp;
       temp = array[x];
       array[x] = array[y];
       array[y] = temp;
       exchanges++;
    }
   
    public static int getkeyposition(int i,int j ){
       return((i+j) /2);
    }
   
    public static void qsort(int list[],int m,int n){
       int key,i,j,k;
       if( m < n){
          k = getkeyposition(m,n);
          swap(m, k);
          key = list[m];
          i = m+1;
          j = n;
          while(i <= j){
             while((i <= n) && (list[i] <= key))
                    i++;
             while((j >= m) && (list[j] > key))
                    j--;
             if( i < j)
                    swap(i,j);
          }
          swap(m,j);
          qsort(list,m,j-1);
          qsort(list,j+1,n);
       }
    }

    public static void printlist(int list[],int n){
       for(int i=0;i<n;i++)
           System.out.print(list[i]+ "   ");
    }

}

Description:

Quicksort uses the simple strategy to take the element at the center of list as the pivot using the function.

int getkeyposition(int i, j){
   return(( i+j )/ 2);
}

In above algorithm, after the pivot is selected, the first element is swapped with the pivot so that it will be in the first position. After that, the pivot’s proper place in the list is obtained using function above. We track the two partitions using the values i and j, and traverse the elements until i becomes greater than j. When i becomes greater than j, we simply swap the elements at those positions. Finally we swap jth element with first element. This process is repeated recursively on the both sides of the pivot until the array gets sorted.

Quicksort is more efficient than Insertion Sort because we do not need to compare the adjacent elements in every pass. The use of pivots (or the divide and conquer strategy) reduces the number of comparisons between adjacent elements. This also removes the need to swap the elements a lot of times, and hence sorts data faster. 

This can be further justified by the fact that the number of exchanges in Quicksort was only 36 compared to 114 in Insertion Sort. And this value came as expected because Quicksort dramatically reduces the number of exchanges or swap operations to be done.

Asymptotic Analysis:

In an average case, the array gets split into two approximately equally sized sub-arrrays. If the size of a given array is n, it gets split into two sub-arrays of size approximately n/2. Each of these sub-arrays gets further split into two sub-arrays of size n/4, and this is continued until the size equals 1.

That is to say, at first, it requires ‘n’ iterations to go through n elements to select an appropriate pivot, and then it recursively sorts left and right sub-arrays (which is similar to working with binary trees). Hence, at average there are n*log n iterations. So, the average case complexity is O(n log n).

If we think of worst case, the first or the last element is always picked as the pivot, making one of the partitions empty. Hence, the advantage of binary tree-like form is lost. The algorithm performs similar to any simple sorting algorithm like Insertion Sort in such a case. Hence, the worst case complexity is O(n2).

Implementing Binary Search Tree in Jeliot tool

The full source code that you can run on Jeliot tool for the Binary Search Tree algorithm is below.

Source Code:

import jeliot.io.*;
import java.util.Scanner;

 /* Class BinarySearchTree */
 public class BinarySearchTree{
     public static void main(String[] args){                
        Scanner scan = new Scanner(System.in);
        /* Creating new Binary Search Tree */
        BST BSTree = new BST();
        System.out.println("Binary Search Tree\n");         
        int ch;
        do{
            System.out.println("Press 1 to Insert and 2 to Search: ");
            int choice = scan.nextInt();           
            switch (choice){
            case 1 :
                System.out.println("Enter element to Insert: ");
                BSTree.insert( scan.nextInt() );                    
                break;                                             
            case 2 :
                System.out.println("Enter element to Search: ");
                System.out.println("Element Found : "+ BSTree.search( scan.nextInt() ));
                break;                                            
            default :
                System.out.println("Invalid Choice!!");
                break;  
            }

            System.out.println("\nPress 1 to continue, anything else to exit: ");
            ch = Integer.parseInt(scan.nextLine());                       
        } while (ch == 1);    
    }
 }

 /* Class BST */
 class BST {
     private BSTNode root;
     int iterations = 0;
     /* Constructor */
     public BST(){
         root = null;
     }
     /* Function to check if tree is empty */
     public boolean isEmpty(){
         return root == null;
     }
     /* Functions to insert data */
     public void insert(int data){
         root = insert(root, data);
     }
     /* Function to insert data recursively */
     private BSTNode insert(BSTNode node, int data){
         if (node == null)
             node = new BSTNode(data);
         else{
             if (data <= node.getData())
                 node.left = insert(node.left, data);
             else
                 node.right = insert(node.right, data);
         }
         return node;
     }
   
     /* Functions to search for an element */
     public boolean search(int val){
         iterations = 0;
         return search(root, val);
     }
     /* Function to search for an element recursively */
     private boolean search(BSTNode r, int val){
         boolean found = false;
         while ((r != null) && !found){
             int rval = r.getData();
             if (val < rval)
                 r = r.getLeft();
             else if (val > rval)
                 r = r.getRight();
             else{
                 found = true;
                 break;
             }
             found = search(r, val);
             iterations++;
         }
         System.out.println("Number of iterations: " + iterations);
         return found;
     }
   
 }

 /* Class BSTNode */
 class BSTNode{
     BSTNode left, right;
     int data;

     /* No argument Constructor*/
     public BSTNode(){
         left = null;
         right = null;
         data = 0;
     }
     /* Constructor with data argument */
     public BSTNode(int n){
         left = null;
         right = null;
         data = n;
     }
     /* Function to set the left node */
     public void setLeft(BSTNode n){
         this.left = n;
     }
     /* Function to set the right node */
     public void setRight(BSTNode n){
         this.right = n;
     }
     /* Function to get the left node */
     public BSTNode getLeft(){
         return this.left;
     }
     /* Function to get the right node */
     public BSTNode getRight(){
         return this.right;
     }
     /* Function to set the data of a node */
     public void setData(int d){
         this.data = d;
     }
     /* Function to get node's data */
     public int getData(){
         return this.data;
     }    
 }

Description of the algorithm:

This is a linked implementation of a Binary Search Tree.

The main class, BinarySearchTree, is the only class that is executable in this and it asks for two options: Insert and Search an element.

The class BST implements the two functions for insertion and searching. The search function recursively searches for an input value and counts the number of iterations required and displays the iteration count when each iteration gets completed. When an element is found, it returns true, otherwise it simply returns false to show that there is no such element in the tree.

BST class depends on BSTNode class which defines the structure of a single node of the Binary Search Tree. The getters and setters for defining the node structure and inserting/retrieving data into node are defined in the BSTNode class. 

Asymptotic analysis of the Search Function:

     /* Function to search for an element recursively */
     private boolean search(BSTNode r, int val){
         boolean found = false;
         while ((r != null) && !found){
             int rval = r.getData();
             if (val < rval)
                 r = r.getLeft();
             else if (val > rval)
                 r = r.getRight();
             else{
                 found = true;
                 break;
             }
             found = search(r, val);
             iterations++;
         }
         System.out.println("Number of iterations: " + iterations);
         return found;
     }

As we can see, the search function only searches a single-half of the tree depending on the search value. If the value is equal to root, it is simply returned. Otherwise, the only right sub-tree is searched for value larger than root and only left sub-tree is searched for value smaller than root. All of this is recursive i.e. the same policy applies to sub-trees of the current node until the value is found or the whole tree is traversed. Hence, the time taken to access nth node is equivalent to log n. Here too, the number of iterations to find ‘9’, which was the 11th item inserted, is 3 log 11 = 3.459 (*Note that base of log here is 2 as it is a binary search).


Therefore, the complexity of Binary Search is O(log n)

Implenting Stack in Jeliot tool

The full source code that you can run on Jeliot tool for the Stack algorithm is below.

Source Code:

import jeliot.io.*;

public class Stack {
    //top of the stack initially -1 signifying an empty stack
    public static int tos = -1;
    //array to implement the stack of size 3
    public static int stack[] = new int[3]; 
   
    public static void main() {
        // Pushing three items into the stack
        push(2);
        push(1);
        push(0); //vehicle begins the line
       
        //Popping three items out of the stack
        pop(); //First Testing Station
        pop(); //Second Testing Station
        pop(); //Third Testing Station
    }
    public static void push(int a){//method for push operation
        if(tos>=2){//checking if the stack is full
            System.out.println("Stack overflow");
            return;
        }
        //increasing top of the stack by 1
        tos++;
        //inserting an item to the top of the stack
        stack[tos] = a;
    }
   
    public static void pop(){//method for pop operation
        if(tos<=-1){//checking if the stack is empty
            System.out.println("Stack underflow");
            return;
        }
        //displaying the item being popped
        System.out.println("Item popped: " + stack[tos]);
        tos--; //decreasing the top of stack by 1
    }
}

Description of the algorithm:

This is an array implementation of a Stack.

The algorithm starts with initialization of the ‘tos’ variable which represents top of the stack. It is initially set to -1 to denote an empty stack. Keeping it -1 makes it easier to use with an array because the first element is stored in the position 0 in an array.

In the main method, we simply push three items 2, 1 and 0 one by one. As suggested in the manufacturing assembly line assumption, 0 is pushed last into the stack. Then we pop the elements once by one to represent different stages of assembly line.

The push method checks if the stack is full or not first. If it is full, it simply displays “Stack overflow” and returns. And if there is space, it inserts the element into top of the stack and increases ‘tos’ by 1 to denote the new top of the stack..

Likewise, the pop method checks if the stack is empty or not first. If it is empty, it simply displays “Stack underflow” and returns. And if there are elements, it displays the popped item into console and decreases ‘tos’ by 1 to denote the new top of the stack.

It should be noted that the popped element is not erased. Since the new ‘tos’ is now less that the index of the popped element, it will be overwritten when any element is pushed in future. So, just leaving the element as it is makes our approach more efficient by decreasing the number of operations.

Asymptotic analysis of the algorithm:

Pushing an item into top of the stack is a trivial operation which requires just writing the item into array and incrementing ‘tos’ by 1. So, it always has 2 operations, and its complexity is hence O(1).

Note that normally pushing 'n' items into Stack has complexity of O(n) in Worst Case but since we always push only three items in this implementation, it has complexity of constant time i.e. O(1).

In the same way, popping an item has just one operation of decreasing ‘tos’ by 1. So, its complexity is also O(1).

As we can see in the algorithm, we push 3 items and pop 3 items making it total of
2*3 + 3 = 9 operations

And it will always have same operations no matter the values pushed or popped. That is to say, this algorithm always runs in “Constant Time”. Thus, the complexity of this algorithm in terms of Big-O notation is O(1).