Friday, August 5, 2016

Optimized quick sort

In the previous article we discussed about quick sort algorithm. In this article we are going to discuss about further optimizing quick sort.

The optimized version of quick sort algorithm we are going to use is known as QuickIn Sort. QuickIn Sort is significantly faster in practice than other O (n log n) algorithms.


Previous article explains how quick sort works. As described in it, quick sort do the real sorting in it's partitioning step. Every time when the recursive function is called, the size of the partition gets smaller. 


Even for a very large data set, the recursive function call occur till the partition size is the smallest possible. When this partitioning occur, there is a threshold size of partition after which, the partitioning costs more than other O (N^2) algorithms. This is an inefficiency of quick sort algorithm.




where A, B, k and c are constants , N is the number of elements in the data set.


The L.H.S of the inequality gives the time complexity of quick sort while R.H.S gives the time complexity of other sorting algorithms.


Insertion sort is an algorithm which has an average time complexity of O (N^2). But the time efficiency of insertion sort depends on how sorted the data set is.


For small N values above inequality becomes true.


eg:






The quickIn sort algorithm use insertion sort for partitions of size less than the threshold value. The threshold value needs to be determined by testing.

Following is an implementation of quickInSort function


The partition function will be the same as in normal quick sort algorithm. Please refer previous article for the partition function. 

Following is an implementation of insertion sort function 

You can find the complete implementation of QuickIn Sort algorithm with tests on github here.

Tuesday, August 2, 2016

Learn Quick Sort

Quick Sort


Quick Sort is a divide and conquer recursive algorithm used in sorting a data set. It is one of the fastest sorting algorithms with an average time complexity of O(Nlog(N)) and a worst case time complexity of O(N²).


Algorithm

  • Pick a pivot ( element of the data set in the range)
  • Iterate through the data set once and re-arrange data so that all the elements larger than the pivot are on the right side of the pivot and elements smaller than the pivot are on the left. 
  • Apply the same re-arranging method recursively to the left and the right parts of the data set separated by the pivot.


Picking the pivot


The pivot can be any element of the data set within the range of the partition. But the pivot will decide the running time of the sorting process. Because if you choose the smallest/largest element of the data set every time, the partitioning will be useless and hence running time will be O(N²). Therefore spending some time to pick a good pivot won't be a waste. 

As mentioned above, choosing left-most element, right-most element or the element at middle as the pivot may lead to time inefficiency as the arrangement of the data set is not known. Choosing a random element also has the same risk. The best pivot will be the median of the data set. But finding it would not be wise considering the time efficiency. 

The easiest way to choose a pivot which is not a corner element is, picking the median element of the first, middle and the last element of the data set. This will ensure that you are not at the worst case every time. 

Advantages

  • No additional memory required. ( Sort in place )
  • Very fast sorting for average case

Disadvantage

  • Worst-case complexity is O(N²)
  • Sorting time not guaranteed.


Following is an implementation of quick sort algorithm in C



Partition function which does the sorting



Here is the complete implementation of quick sort algorithm with example tests on github. 

Saturday, July 16, 2016

Vert.x example - Http Server

Vert.x is a toolkit for building reactive applications on the JVM. 
For more information about vert.x please read the previous article from here

Following is a simple http Server implemented using vert.x to understand the nature of vert.x applications.


The code is self explanatory. 

To run the above http server, you need vert.x installed and setup properly. 

To start the server, open a terminal or a command promt and run the following command. 

vertx run Server.java

After you run the above command you will get a message saying 'Succeeded in deploying verticle'. 

If you get any errors, please check your vert.x installation. 

Now your server is running and waiting for requests to come.  

Note that the above server is implemented to handle GET requests only. It listens to the port 8500.

As line 28 needs a parameter called "name", our GET request should include a name parameter. 

Now open your browser, paste the below url and hit enter. For 'yourname', you can give anything.

http://localhost:8500/?name=yourname



Now you've used successfully used vert.x to build a server. 

This server can handle multiple clients at the same time although in the code we never do anything about it. And we don't have to worry about synchronization or deadlocks. 
This is the speciality of vert.x. 

This same server can be built using javaScript, ruby Groovy or Python to run on JVM. 
More examples can be found in the official github repository of vert.x.

Getting Started with Vert.x

What is Vert.x ?


Vert.x is a toolkit for writing scalable, polyglot, reactive applications which run on the JVM. Vert.x is similar to Node.js as both provide an asynchronous API and as it is event-driven. 

Polyglot


Vert.x is written in Java, but we can use it with many languages like Java, Groovy, Ruby, Python, and even JavaScript. You can even mix and match languages. 

Reactive


Vert.x is asynchronous. It can be used to create highly concurrent applications. Vert.x allows to create multiple threads based on the number of CPU cores while only one process is executed. It handles the multi-threading so users can focus on implementing business logic. Developer won't have to worry about synchronization, deadlocks or data races.

Verticles


Verticles are building blocks of vert.x application. They are units which operate independently. It can simply said that running a vert.x application means running one or more verticles. Verticles communicate with each other using event bus. Vert.x has some command line tool which enable the developer to simply run the program without compiling it. 

How to install vert.x ?


Vert.x can be installed linux, Windows or OSX. Before installing, you need to have JDK 1.7.0 or later installed and JAVA_HOME added to the PATH variable. 

Linux

  • Download the latest version of vert.x from here.
  • Extract it to a place where it will stay permanent. (Extracted directory shouldn't be moved since path will be set accordingly).
  • Add vert.x/bin to PATH variable. Open a terminal and run the following command 
                          export PATH=$PATH:/path

      where
          path = absolute path to the bin directory of your vert.x extract

     eg:
                          export PATH=$PATH:/home/user/Vertx/bin


      If you are having trouble changing the PATH variable, see this.

  • Verify your installation by running the command 
                         vertx version

Windows

  • Download the latest version of vert.x from here.
  • Extract it to a place where it will stay permanent. (Extracted directory shouldn't be moved since path will be set accordingly).
  • Search for 'View Advanced System Settings' and select 'Environment Variables'
  • From 'System Variables' section, highlight 'Path' and click on 'Edit'
  • For windows 7 and 8 
          append ;path to the existing 'Variable Value'
          where
          path = absolute path to the bin directory of your vert.x extract

           eg:
                          ;C:\Users\User\Vertx\bin

  • For Windows 10 click 'New' and add the path with no semicolon. 
             eg:
                          C:\Users\User\Vertx\bin


Running Vert.x programs


Vert.x programs can be simply run using vert.x command line tools. 

eg: 
        vertx run myprogram.java
        vertx run myprogram.js
    


Java - Standard input and output in competitive programming

Java provides several classes for taking standard input and printing to standard output.


For input
  • Scanner class
  • BufferedReader and InputStreamReader classes
  • DataInputStream class
  • Console class
For output
  • PrintStream class (System.out.print)
  • BufferedWriter and OutputStreamWriter classes
  • PrintWriter class
We can use any of the above classes to interact with std in/out. But the performance of the above classes differ with the way they are implemented.

Sometimes the time taken to get user input or the time taken to print back to the user becomes important. One such occasion is competitive programming.

Competitive programming websites like hackerrank.com or codeforces.com sets timouts to run the solutions. These timeouts are generally set to check whether the competitor has solved the problem using an efficient algorithm.

But sometimes although the competitor has used an efficient algorithm, timeouts may occur. This is due to inefficiency in taking input or printing the output. Below is an implementation of a java class which can be easily used take input and print output efficiently. 

   

Saturday, May 28, 2016

Binary Search Tree Data Structure

Graph

A graph ‘G’ is defined as G = (V, E) Where V is a set of all vertices and E is a set of all edges in the graph.

Example
graph
In the above example, ab, ac, cd, and bd are the edges of the graph. Similarly, a, b, c, and d are the vertices of the graph.

Tree

A connected acyclic graph is called a tree. In other words, a connected graph with no cycles is called a tree.
Tree 












Binary Tree

Binary tree is a tree in which every node has a maximum of two nodes connected.

 


Binary Search Tree

Binary Search tree is a binary tree with the following properties.


• The left subtree of a node contains only nodes with keys less than the node’s key.

• The right subtree of a node contains only nodes with keys greater than the node’s key.


• Both the left and right subtrees must also be binary search trees. 



BST




Binary search tree should be implemented considering the above properties.

BST.h file implements the data structure and functions of Binary Search Tree.
Please find a link on github to this same implementation at the bottom.

[code]
#ifndef _BST_
#define _BST_

#include <stdlib.h>
#include <limits.h>

/*data structure binary search tree*/
typedef struct bst_node
{
    int data;
    struct bst_node* left;
    struct bst_node* right;   
}bst;

/*
  allocate memory for a single
  node
  return the node
*/
bst* createBST();

/*
  add the given data to the
  given tree
*/
void addBST(bst* tree, int data);

/*
  print the tree in sorted
  order
*/
void printOrderedList(bst* tree);

/*
  free the memory allocated
  for the bst
*/
void destroyBST(bst* tree);

/*
  Delete the node with
  the given value from
  given bst
*/
bst* deleteBST(bst* tree, int data);

/*
  return 1 if given data is
  present in the given bst
  0 otherwise
*/
int findBST(bst* tree, int data);

/*
  copy the bst given in tree
  to bst given as copy
*/
void copyBST(bst* tree, bst* copy);

/*
  find the node with min value
  and return it
*/
bst* minValueNode(bst* tree);


/*Implementations*/

/**********************/
bst* createBST()
{
    bst* tree = malloc(sizeof(bst)); // allocate memory
    tree -> data = INT_MIN;
    tree -> left = NULL;
    tree -> right = NULL;
    return tree;
}

/**************************/
void destroyBST(bst* tree)
{
    if(tree == NULL)
        return;

    if(tree -> left != NULL)    
        destroyBST(tree -> left);
   
    if(tree -> right != NULL)
        destroyBST(tree -> right);
   
    free(tree);
}

/*********************************/
void copyBST(bst* tree, bst* copy)
{
    if(tree == NULL)
        return;
   
    addBST(copy, tree -> data);

    if(tree -> left != NULL)
        copyBST(tree -> left, copy);

    if(tree -> right != NULL)
        copyBST(tree -> right, copy);

   
}

/*******************************/
void addBST(bst* tree, int data)
{
    bst* node = malloc(sizeof(bst));
    node -> data = data;
    node -> right = NULL;
    node -> left = NULL;   

    if(tree -> data == INT_MIN) // if root is not entered yet
    {
        tree -> data = data;
        return;
    }

    if( (tree -> data) <= data) // if data should go to left
    {
        if( tree -> right == NULL)
        {
            tree -> right = node;
        }   
        else
            addBST(tree -> right, data);
    }
    else
    {
        if( tree -> left == NULL)
        {
            tree -> left = node;
        }   
        else
            addBST(tree -> left, data);
    }
   
   
}

/*********************************/
bst* deleteBST(bst* tree, int data)
{
    bst* tmp;
    if(tree == NULL)
        return tree;

    if(tree -> data > data)
        deleteBST(tree -> left, data);
    else if(tree -> data < data)
        deleteBST(tree -> right, data);
    else
    {
        if(tree -> left == NULL)
        {
            tmp = tree -> right;
            free(tree);
            return tmp;
        }
        else if(tree -> right == NULL)
        {
            tmp = tree -> left;
            free(tree);
            return tmp;
        }
        tmp = minValueNode(tree -> right); // find min node from right children
        tree -> data = tmp -> data;

        tree -> right = deleteBST(tree -> right, tmp -> data);//remove min node from right children
    }
    return tree;
}

/*********************************/
int findBST(bst* tree, int data)
{
    if(tree == NULL)
        return;

    if(tree -> left != NULL)
    {   
        if(findBST(tree -> left, data))
            return 1;
    }
   
    if(tree -> right != NULL)
    {
        if(findBST(tree -> right, data))
            return 1;
    }

    if(tree -> data == data)
    {
        return 1;
    }
    else
        return 0;
}

/************************/
int findMax(bst* tree)
{
    bst* tmp = tree;
    int val;

    while(tmp != NULL)
    {
        val = tmp -> data;
        tmp = tmp -> right;
    }
    return val;
}

/************************/
int findMin(bst* tree)
{
    bst* tmp = tree;
    int val;

    while(tmp != NULL)
    {
        val = tmp -> data;
        tmp = tmp -> left;
    }
    return val;
}

/*******************************/
void printOrderedList(bst* tree)
{
    if(tree == NULL)
        return;
    if(tree -> left == NULL && tree -> right == NULL)
    {
        printf("%d ",tree -> data);
        return;
    }
   
    if(tree -> left != NULL)
        printOrderedList(tree -> left);

    printf("%d ",tree -> data);
    if(tree -> right != NULL)
        printOrderedList(tree -> right);
   
}

/***************************/
bst* minValueNode(bst* tree)
{
    bst* tmp = tree;

    while (tmp -> left != NULL)
        tmp = tmp -> left;

    return tmp;
}


#endif
[/code]

test.c file demonstrate the functionalities of the BST implemented in BST.h file.

[code]
#include <stdio.h>
#include "BST.h"

void printArray(int arr[30]);
void populate(bst* tree, int arr[30]);

/*********/
int main()
{
    int randomNos[30];
    int num;
    bst* tree = createBST();
    bst* copy = createBST();
   
    printf("Adding random numbers to BST\n");
    populate(tree, randomNos);   

    printf("Populated order..\n");
    printArray(randomNos);

    printf("Printing ordered list from tree\n");
    printOrderedList(tree);
    printf("\n");
    printf("\n");
   
    printf("Copying BST to another BST..\n Printing it..\n");
    copyBST(tree, copy);
    printOrderedList(copy);
    printf("\n");
    printf("\n");

    printf("Max in the tree : %d \n",findMax(tree));
    printf("Min in the tree : %d \n",findMin(tree));
    printf("\n");

    printf("Enter a number find in the tree : \n");
    scanf("%d",&num);
   
    if(findBST(tree, num))
        printf("%d is in the tree\n",num);
    else
        printf("%d is not in the tree\n",num);

    printf("\n");

    printf("Removing %d from the tree..\n",randomNos[5]);
    tree = deleteBST(tree, randomNos[5]);
    printf("After removal\n");
    printOrderedList(tree);
    printf("\n");
   
    printf("Destroying BST...\n");
    destroyBST(tree);

    printf("\nPrinting tree after destroy..\n\n");
    printOrderedList(tree);
   

    return 0;
}

/************************************/
void populate(bst* tree, int arr[30])
{
    int i;
    srand(time(NULL));

    for(i = 0; i<30; i++)
    {
        arr[i] = rand()%50;
        addBST(tree, arr[i]);
    }
}

/****************************/
void printArray(int arr[30])
{
    int i;
   
    for(i = 0; i<30; i++)
        printf("%d ",arr[i]);
    printf("\n");
}

[/code]

Please visit here to view the code in github.

Sunday, February 14, 2016

Binary search of an ordered list of integers

Binary search is a fundamental algorithm in computer science. It is used to find the position of a given integer in a sorted list of integers. We don't have to iterate through the whole list, if we use this algorithm. Therefore it is an efficient algorithm for searching. The complexity of binary search algorithm is O(logN). 

http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html

If N elements are there in the list, 
you will have to halve the list x times to find an element. (Halve the list until 1 element is left)

 1 = N / 2x
 2x = N
 x = log2 N

Therefore time complexity - O(logN)

[code]
#include <stdio.h>

int main()
{
    int arr[100];
    int n, i, el;

    printf("Enter the number of elements: ");
    scanf("%d",&n);

    printf("Enter the elements\n");
    for(i = 0; i<n; i++)
    {
        scanf("%d",&arr[i]);
        if(i != 0 && arr[i-1]>arr[i])
        {
            printf("Please enter a sorted list!\n");
            return 0;
        }
    }

    printf("Enter the element to search\n");
    scanf("%d",&el);

    int position = binarySearch(arr,n,el);
   
    if(position != -1)
        printf("The element is at %d.\n",position);
    else
        printf("Element not found!\n");

    return 0;
}

/*Binary search function
  Arguments - integer array
          size of the array
          element to search for
  Return the position if successful
 
*/
int binarySearch(int arr[], int size, int el)
{
    int low = 0, high = size-1;
    int mid = (high + low)/2;

    while(arr[mid] != el)
    {
        if(arr[mid] > el)
            high = mid;
        else
            low = mid;

        if(high == low+1)
        {
            if(arr[high] == el)
                return high;
            else if(arr[low] == el)
                return low;
            else
                return -1;
        }
        mid = (low + high)/2;
    }
    return mid+1;
}[/code]

Optimized quick sort

In the previous article  we discussed about quick sort algorithm. In this article we are going to discuss about further optimizing quick sor...