Tuesday, December 8, 2015

Quick Sort

import java.util.Random;

public class QuickSort {
    int[] a;
    public QuickSort(int[] a) {
        this.a = a;
    }
    public int[] QSort()    {
        QSort(this.a, 0, this.a.length-1);
        return a;
    }
    private void QSort(int[] a, int startIndex, int endIndex)    {
        if(startIndex<endIndex)    {
            int PartionIndex = RandomizedPartition(startIndex, endIndex);
            QSort(a, startIndex, PartionIndex-1);
            QSort(a, PartionIndex+1, endIndex);
        }
    }
    private int RandomizedPartition(int startIndex, int endIndex)    {
        /* Worst Case of QuickSort is O(n^2)
        The possibility for WorstCase in QuickSort is very low
       
RandomizedPartition will help reducing the probability of the occurrence of worst case*/
        int PivotIndex=new Random().nextInt(endIndex-startIndex)+startIndex;
        swap(PivotIndex, endIndex);
        return Partition(startIndex, endIndex);
    }
    private int Partition(int startIndex, int endIndex)    {
        int Pivot=a[endIndex];
        int PivotIndex=startIndex;
        for(int i=startIndex; i<endIndex; i++)    {
            if(a[i]<=Pivot)    {
                swap(i, PivotIndex);
                PivotIndex++;
            }
        }
        swap(PivotIndex, endIndex);
        return PivotIndex;
    }
    private void swap(int IndexA, int IndexB)    {
        int temp=a[IndexA];
        a[IndexA]=a[IndexB];
        a[IndexB]=temp;
    }
}
UA-39217154-2