package Sorting;

public class WordQuickSorterThreeWay extends WordQuickSorter {
    
    public WordQuickSorterThreeWay(RandomWordFileReader reader) {
        super("quick sort (3-way partition)", reader);
    }

    @Override
    void quickSort(int lowIndex, int highIndex) {
        if (compare(lowIndex, highIndex)<0) {
            String pivot = words[highIndex];
            int lessThan = lowIndex;
            int greaterThan = highIndex;
            int i = greaterThan - 1;
            while(i >= lessThan) {
                int comp = compare(words[i], pivot);
                if(comp > 0) {
                    swap(words, i, greaterThan);
                    i--;
                    greaterThan--;
                } else if(comp < 0) {
                    swap(words, i, lessThan);
                    lessThan++;
                } else {
                    i--;
                }
            }
            quickSort(lowIndex, lessThan-1);
            quickSort(greaterThan+1, highIndex);
        }
    }


}