Saturday, April 20, 2013

Quick Sort Algorithm implementation using JAVA

Quick sort algorithm implementation in JAVA.

 * QuickSort
 * Best Case: o(nlogn)
 * Average Case: o(nlogn)
 * Worst Case: o(n^2)
 * Algorithm
 * QuickSort(A, StartIndex, EndIndex)
 * 1: if  StartIndex < EndIndex
 * 2: partitionIndex = partition(startIndex,endIndex);
 * 3: quickSort(startIndex,partitionIndex);
 * 4: quickSort(partitionIndex+1,A.length);
 * partition(startIndex, endIndex)
 * 1: pivotIndex = endIndex- 1;
 * 2: j = startIndex-1;
 * 3: for i=0 ;i *    3.1   if( i == endIndex -1)
 *    3.1.1 j = j+1;
 *    3.1.2 swap(i,j);
 *    3.2   else if(arrayToSort[i]<= arrayToSort[pivotIndex])
 *    3.2.1 j = j+1;
 *    3.2.2 swap(i,j);
 * 4: return j;
package org.itsvenkis.sorting.algorithms;

 * @author itsvenkis
public class QuickSort {

    private static int[] arrayToSort;

    public static int[] quickSort(int[] array) {
        arrayToSort = array;
        return arrayToSort;

    private static void quickSort(int startIndex, int endIndex) {
        if(startIndex < endIndex){
        int partitionIndex = partition(startIndex,endIndex);

    private static int partition(int startIndex, int endIndex) {
        int pivotIndex = endIndex- 1;
        int j = startIndex-1;
        for (int i = startIndex; i < endIndex; i++) {
            if( i == endIndex -1){
                j = j+1;
            }else if(arrayToSort[i]<= arrayToSort[pivotIndex]){
                j = j+1;
        return j;
    private static void swap(int from,int to){
        int tempValue = arrayToSort[from];
        arrayToSort[from] = arrayToSort[to];
        arrayToSort[to] = tempValue;

Friday, April 19, 2013

Java collection - Data structures

This post is a quick look at available list of data structures/collections available in JAVA
JAVA collections framework is a collection of different types of data structures. With this default collections one may never need to create their own data structure to support their project requirements. Enough said!!! lets jump into what collections framework is all about.
Collections api is a group of interfaces and implementations. Below are the interfaces and their implementations which are part of collections framework


List : ArrayList ,Vector, LinkedList

Now let us go through each interface and its implementations

List Interface : In simple words List is an ordered collection of objects

ArayList : One of the most famous and widely used collection is ArrayList. ArrayList implements a marker interface,to let us know that it supports faster random access of an object in its collection. It also provides faster iteration over its elements. This collection is unsorted and ordered.

Vector: Vector is an another variant of List. One main difference between ArrayList and Vector is thread
safety.  While Vector is thread safe ArrayList is not. Even vector implements RandomAccessInterface(Marker Interface).This collection is unsorted and ordered.
Note: By thread safe it is not meant that it is completely thread safe only few operations in this colelction are thread safe.

LinkedList: LinkedList supports faster insertions and deletions. So we can use this collection if we need faster insertions and deletions. This collection is unsorted and ordered.
Map Interface : By using Map data structure one can map a unique key object to a specific object. Noteworthy that it is mentioned as unique key. So objects used in Map should override and provide meaningful implementation of equals method.
HashMap: As mentioned above keys should be unique and objects are placed based on the hashcode computed. I strongly suggest you to have a good understanding of hashcode and its relation to equals method before using this collection. It is common practice to use string literals as Key to avoid the complex implementations of hashcode method.HashMap is not thread safe.This data structure is unordered and unsorted.
HashTable : It is thread safe version of Map interface and another difference between HashMap and Hashtable is the later does not allow any null values as keys whereas Hashmap will allow one null value as key. This data structure is unordered and unsorted.
LinkedHashMap: Linkedhashmap is an ordered collection where its order is maintained by the insertion order. Provides faster insertion and deletion. This collection is ordered and unsorted.
TreeMap: TreeMap is a sorted version of Map data structure. Sorting will be by natural order(Natural order for numbers will be 1,2,3...., for strings a,b,c.....) or we can use an comparable or comparator to influence the sort order.This collection is sorted and ordered. Any collection which is sorted will be obviously ordered collection also.

Set Interface: One key word we have to remember about Set interface is uniqueness. So this data structure will never contain duplicate elements. So it is very important to provide meaningful implementation for equals methods to the objects which will be used in this data structure.

HashSet: elements will inserted based on the hashcode computed. Use of this data structure will guarantee
uniqueness. This collection is unsorted and unordered
LinkedHshSet: will maintain insertion order. so insertions and deletions will be faster when compared to
TreeSet: TreeSet is an ordered and sorted data structure. Elements will be sorted based on its natural order or can be influenced by a comparator or comparable.

Queue Interface: Follows FIFO(First in first out) policy.

PriorityQueues: to indicate the priorities. Priorities will be maintained base on the natural order of the elements in this data structure. sort order can be influenced by use of comparator or comparable. This sort order will determine the priorities of the elements.