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;
        quickSort(0,array.length);
        return arrayToSort;
    }

    private static void quickSort(int startIndex, int endIndex) {
        if(startIndex < endIndex){
        int partitionIndex = partition(startIndex,endIndex);
        quickSort(startIndex,partitionIndex);
        quickSort(partitionIndex+1,arrayToSort.length);
        }
    }

    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;
                swap(i,j);
            }else if(arrayToSort[i]<= arrayToSort[pivotIndex]){
                j = j+1;
                swap(i,j);
            }
        }
        return j;
    }
   
    private static void swap(int from,int to){
        int tempValue = arrayToSort[from];
        arrayToSort[from] = arrayToSort[to];
        arrayToSort[to] = tempValue;
    }
}

No comments:

Post a Comment