Quick Sort in Java

Quick sort is one of the coolest algorithms available in sorting and its performance is measured most of the time in O(nlogn), although the worst case sorting times of bubble sort and this are equal.
Inspite its worst case time, this always performs superiorly when the input is completely shuffled/randomized. This is one of the modest sorts available :).

Quick sort is an example of in-place sort. No extra space is needed as in merge sort where we have to use one full extra array to hold all the merged values. The only space that quick sort uses may be the counter variables and the extra space required for swapping.

Below is a pictorial representation of how this quick sort works,

I ran this sort for a well randomized data of million elements again and again and it beats the Merge sort hands down having a 75% quicker speed. Its always advisable to have shuffle the data upfront before running this algorithm.
Here is the source code for the same,

package dsa.sorting;

/**
 * A wonderful inplace sorting technique
 * @author Braga
 */
public class QuickSort {
 
 public static int SIZE = 1000000;

 public int[] sort(int[] input) {
  quickSort(input, 0, input.length-1);
  return input;
 }
 
 public static void main(String args[]){
  int[] a = new int[SIZE];
  for(int i=0;i<SIZE;i++){
   a[i] = (int)(Math.random()*SIZE);
  }
  QuickSort mNew = new QuickSort();
  long start = System.currentTimeMillis();
  mNew.sort(a);
  long end = System.currentTimeMillis();
  System.out.println("Time taken to sort a million elements : "+(end-start)+" milliseconds");
 }
 
 public void print(int[] inputData) {
  for(int i:inputData){
   System.out.print(i+" ");
  }
  System.out.println();
 }
 
 private void quickSort(int arr[], int left, int right) {
  int index = partition(arr, left, right);
  if (left < index - 1)
   quickSort(arr, left, index - 1);
  if (index < right)
   quickSort(arr, index, right);
 }
 
 private int partition(int arr[], int left, int right) {
  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];
  while (i <= j) {
   while (arr[i] < pivot)
    i++;
   while (arr[j] > pivot)
    j--;
   if (i <= j) {
    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
    i++;
    j--;
   }
  }
  return i;
 }
}
//Time taken to sort a million elements : 156 milliseconds

Pros:
1) Efficient average case compared to any algorithm.
2) Recursive definition and popularity because of its high efficiency.

Cons:
1) Worst case scenario sucks.

As we discussed the worst case can be easily overcome by deliberately shuffling the input. I would rate quick sort as one of the best techniques available in sorting till date.

More sorting methods yet to come.
Cheers,
Bragaadeesh.

Merge Sort in Java

Now that we've examined one of the most simplest and inefficient sorting algorithms (Bubble Sort), lets have a look at O(nlogn) sorts. To start with, we shall look into Merge Sort.
Merge Sort follows divide and conquer technique. The following is a simple pictorial illustration of the same.

There will be two parts in this sort. One would be halving the input numbers O(logn) and the other would be merging them back O(n) which results in a comprehensive O(nlogn) time. Wait till you see the running version of this sort technique and the time taken to sort a million entries.

First for the code part,

package dsa.sorting;

public class MergeSortOptimized
{

    public static int SIZE = 1000000;

    public static void main(String args[])
    {
        int[] a = new int[SIZE];
        for (int i = 0; i < SIZE; i++) {
            a[i] = (int) (Math.random() * SIZE);
        }
        long start = System.currentTimeMillis();
        MergeSortOptimized mNew = new MergeSortOptimized();
        mNew.sort(a);
        long end = System.currentTimeMillis();
        System.out.println("Time taken to sort a million elements : "
                + (end - start) + " milliseconds");
    }

    public int[] sort(int[] input)
    {
        int[] temp = new int[input.length];
        mergeSort(input, temp, 0, input.length - 1);
        return input;
    }

    public void mergeSort(int[] fromArray, int[] toArray, int left, int right)
    {
        if (left < right) {
            int center = (left + right) / 2;
            mergeSort(fromArray, toArray, left, center);
            mergeSort(fromArray, toArray, center + 1, right);
            merge(fromArray, toArray, left, center + 1, right);
        }
    }

    public void merge(int[] fromArray, int[] toArray, int leftPos,
            int rightPos, int rightEnd)
    {
        int leftEnd = rightPos - 1;
        int tempPos = leftPos;

        int numElements = rightEnd - leftPos + 1;

        while (leftPos <= leftEnd && rightPos <= rightEnd) {
            if (fromArray[leftPos] < fromArray[rightPos]) {
                toArray[tempPos++] = fromArray[leftPos++];
            }
            else {
                toArray[tempPos++] = fromArray[rightPos++];
            }
        }

        while (leftPos <= leftEnd) {
            toArray[tempPos++] = fromArray[leftPos++];
        }
        while (rightPos <= rightEnd) {
            toArray[tempPos++] = fromArray[rightPos++];
        }

        for (int i = 0; i < numElements; i++, rightEnd--) {
            fromArray[rightEnd] = toArray[rightEnd];
        }

    }

}
// Time taken to sort a million elements : 247 milliseconds

As you may observe, the above technique just took 247 milliseconds to sort a million elements whereas the bubble sort tooks almost 28 seconds to sort a hundred thousand elements!!!!! This is due to the logarithmic order of the sort.

Pros:
1) Works in O(nlogn) time.
2) Worst case of merge sort is equal to best case of a quick sort! (We shall discuss more about in the coming sections).

Cons:
1) Consumes extra space.
2) Due to the recursive nature of the algorithm, may eat up stack.

Thanks for reading my post. We shall explore more sorting techniques in the coming days. Till then, bye for now from,
Bragaadeesh.

Bubble Sort in Java

Bubble sort is the most simplest form of sorts available. In real lives, the bubbles formed under water tend to come up to the surface. Larger the bubble, faster it will come up. Same way in this sorting technique, we would try to push the larger value up in case of descending or vice versa.

Pros:
1. Simple to implement.
2. Very easy to understand.

Cons:
1. Runs in O(n²) complexity.
2. Severe performance issues if the sample size increases.

The java code for this sorting technique is as follows,

package dsa.sorting;

public class BubbleSort {

 public static int SIZE = 100000;

 public static void main(String args[]) {
  int[] a = new int[SIZE];
  for (int i = 0; i < SIZE; i++) {
   a[i] = (int) (Math.random() * SIZE);
  }
  long start = System.currentTimeMillis();
  BubbleSort mNew = new BubbleSort();
  mNew.sort(a);
  long end = System.currentTimeMillis();
  System.out.println("Time taken to sort a 100000 elements : "
    + (end - start) + " milliseconds");
 }

 public int[] sort(int[] input) {
  int temp;
  for (int i = 0; i < input.length; i++) {
   for (int j = i; j < input.length; j++) {
    if (input[i] > input[j]) {
     temp = input[i];
     input[i] = input[j];
     input[j] = temp;
    }
   }
  }
  return input;
 }
}
// Time taken to sort a 100000 elements : 28554 milliseconds

You may see from the above example that it takes insanely higher time for sorting only a hundred thousand elements. 29 seconds is a very poor outcome. We will look into O(nlogn) sort types on why and how it reduces this running time.

Cheers,
Bragaadeesh.

Java Sorting techniques

I thought i would start exploring the Sorting mechanisms in Data Structures and try to comprehensively implement them in Java.

We have many types of sorting techniques readily available and there are numerous amount of resources in the net with ready made coding in all the common languages. What I have done here is, did some research on each of the sorting techniques and tried to present the most commonly used sorting techniques with its pros and cons. I have not dealt or dug deep into 'alternate' techniques but have provided a sufficient overview with running code.

Today I will present two of the most familiar sorting techniques namely bubble sort and merge sort and discuss its pros and cons in the following posts.

Cheers,
Bragaadeesh

Free Mini project in C++ using LinkedLists

Folks,

This is one of the oldest mini projects that I did way back in 2004/05 in C++. Its a Medical database management using Indexed Sequential Sorting technique. Its 100% free to use and distribute. Its very old in terms of UI since it uses the classical DOS platform but surely its worth a learn. Free project report too included.

Project Report can be found here
Source Code can be found here

Just an abstract overview of the project follows

Maintaining Purchase and Sale Details for any company is a tedious job; hence we need an alternative in the field of Stock maintenance. Our Software will satisfy all the current needs for maintaining Stock details, Printing out bills, Statistical details with graphs.

The goods purchased are for selling. If the goods are not sold out fully a part of the total goods purchased is kept with the trader until it is sold out. It is said to be Stock. If there is Stock at the end of the accounting year it is said to be a Closing stock. This closing stock at the year end will be the Opening stock for the subsequent year.

At present Purchase and Sale Details are maintained separately. In order to know Stock information both has to be referred. At the end of an accounting year, any change in initial data (at the beginning of the year) will result in entire change of data which is a tedious job and time consuming.

The Purchase details are entered by the User and in turn stock details are manipulated and maintained by the System. The user has an option of entering details in any order. If the details are entered in different orders of date, they are sorted automatically by the system. Here changes can be made without any difficulties in a short time. The user can view the Stock details, Sale details and Statistics (by month, by year etc.,) as per his requirements. In addition to this, Purchase and Sale Details with Cash Details can be viewed with all above mentioned features. There is no need to enter the sale details as we have an automated billing system built-in with the software.


We have a lot of features in this project. Because we chose an efficient data structure i.e., indexed insertion sort, indexed sequential search, bucketing technique of handling files etc.,

We constructed a very strong basic data structure which is highly complex to implement, but highly efficient in case of memory management. After that strong foundation we were able to add features easily.

Also we completely used this in text mode. In text mode itself, we’ll be handling charts. Since we have used bucketing technique of handling files, a minimum of 32MB RAM is well sufficient to run our program. A computer of just rs.5000 and a dot matrix printer are all the investments if a medical shop is going to have this software. A DOS platform is sufficient enough to run this software.


Features at a glance.

• Efficient memory handling.
• Very low minimum requirements: only an old Pentium machine with 32MB of RAM and 1GB hard disk with a dot matrix are more than enough.
• Efficient storage management achieved through bucketing.
• High speed search achieved using Indexed sequential search.
• Simplicity in entering, deleting and editing details of medicines. Data can be entered in any order.
• Viewing past sales and purchase details is possible in both statistical and graphical mode.
• Warnings whenever a medicine expires in the current stock.
• Intelligent Billing system.

Cheers,
Bragaadeesh.