Friday, 4 May 2012

QuickSort

It's been quite some time since I have blogged, frankly because I did not know what to blog. Yesterday my friend calls me up and asks me how to implement a quicksort algorithm. So here goes....

Quicksort is a sorting algorithm that is a little bit more complicated that a bubble sort or an insertion sort. To put it mathematically on average case a quicksort algorithm can make O(n log n) comparisons to sort n number of items, to keep things simple if an algorithm can make O(n log n) comparisons it means it is fast. The worst case is O(n2) which means it is not good. But let's leave the complex maths there and focus on how we can implement a quick sort algorithm.

Sort algorithms are the processing of ordering of elements in an array in a predefined order, it can be either ascending, descenting or it can be a specific pattern! Quicksort is a divide and conquer algorithm. It means the if there are a set of numbers in an array, it first divides the array, sorts it individually and then combine it.

Lets assume the below given is an array of 9 numbers.  

23
14
98
1
61
32
56
71
48


Now if we want to sort the above array using quicksort, first of all the algorithm who we can call as Saddy, will first select the value of the middle element in the algorithm, in this case it is 61. Then from there, Saddy will split the array and all the elements which are smaller that the middle element and these numbers placed on the left side and all the numbers which are greater than the middle element are placed on the right side, after that Saddy will combine the array and we now have a sorted array!!!

Well let the coding begin...



package quicksort;

public class QuickSort 
{
    private int[] numbers;
    private int num;

    public void checker(int [] values)
    {
        if(values==null || values.length==0)
            return;
        numbers=values;
        QuickSort(0, numbers.length-1);
    }
    //The checker function checks if the array is empty or not

    private void QuickSort(int low, int high)
    {
        int i=low,j=high;
        //This is where we get the middle number.
        int mid= numbers[low+(high-low)/2];
        //Dividing the list into two parts
        while(i<=j)
        {
            //Sorting on the left side
            while(numbers[i]<mid)
                i++;
            //Sorting on the right side
            while(numbers[j]>mid)
                j--;
            //This is to check if the the value in the left list is greater than the mid value or
            //the value in the right list is lesser that the mid value.
            //Then we exchange the values and then increment i and decrement j.
            if(i<=j)
            {
                exchange(i,j);
                i++;
                j--;
            }
        }
        if(low<j)
            QuickSort(low, j);
        if(i<high)
            QuickSort(i, high);
    }
    //Swaps numbers
    private void exchange(int i,int j)
    {
        int temp=numbers[i];
        numbers[i]=numbers[j];
        numbers[j]=temp;
    }
}

After the implementation is over we would like to see if the implementation actually works. I have made some test cases in jUnit.
package quicksort;

import org.junit.*;

public class QuickSortTest 
{
    private int[] numbers;
    @Test
    public void testNull() 
    {
        QuickSort sorter = new QuickSort();
        sorter.checker(null);
    }
    @Test
    public void testChecker() 
    {
        System.out.println("checker");
        int [] arg={23,34,5,54,67,31,65,365732,3064,13,1,860,};
        QuickSort sorter = new QuickSort();
        sorter.checker(arg);
        numberPrinter(arg);
            if(!validate(arg))
                fail("Error");
        printResult(arg);
    }
    private boolean validate(int[] numbers)
    {
        for (int i=0;i<numbers.length-1;i++) 
        {
            if (numbers[i]>numbers[i+1])
            return false;
        }
        return true;
    }
    private void numberPrinter(int[] numbers)
    {
        for (int i = 0; i < numbers.length; i++) 
            System.out.print(numbers[i]+",");
        System.out.println();
    }
    public void printResult(int[] numbers)
    {
        for (int i = 0; i < numbers.length; i++)
            System.out.print(numbers[i]+",");
        System.out.println();
    }
}
X8DGBKBVB4Z3

No comments:

Post a Comment