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;
}
}
No comments:
Post a Comment