package Sorting;

/**
 * an implementation of quick sort with three-way partitioning
 */

public class NumberQuickSorterThreeWay extends NumberQuickSorter{

    public NumberQuickSorterThreeWay(RandomNumberFileReader reader){
        super("quick sort (3-way partition)", reader);
    }
    
    @Override
    void quickSort(int lowIndex, int highIndex){
        if(compare(lowIndex,highIndex)<0){
            int pivot=numbers[highIndex];
            int lessThan = lowIndex;
            int greaterThan = highIndex;
            int i = greaterThan-1;
            while(i>=lessThan){
                int comp = compare(numbers[i], pivot);
                if(comp>0){
                    swap(i, greaterThan);
                    i--;
                    greaterThan--;
                }
                else if(comp<0){
                    swap(i, lessThan);
                    lessThan++;
                }
                else{
                    i--;
                }
            }
             quickSort(lowIndex, lessThan-1);
             quickSort(greaterThan+1, highIndex);
        }
     }

   
}