Home



2020/02 - DS&A #10: Quick Sort

Hey folks,

The last sorting algorithm we'll be looking at the now in this series is the Quick Sort. The quick sort is another divide and conquer algorithm, but this time we iterate over the array repeatedly, picking a "pivot" element every iteration. We rearrange the surrounding elements such that every value to the left is lower and every value to the right is higher, but do not actually sort the left or right sides other than making sure that each of  said sides elements are higher/lower than the pivot value.

 

public class QuickSort {

    int[] valuesToSort;
    int timesTakenToSort = 0;
    
    public QuickSort(int size) {
        valuesToSort = new int[size];
    }

The above is boilerplate. In a rare occurence, I seem to have not started with the main method when I wrote this code...

 

    public void sort() {
        for(int i = valuesToSort.length/2, t = valuesToSort.length/2; t != 0 && i != valuesToSort.length - 1;) {
            if(i < valuesToSort.length - 1) {
                i++;
                this.rearrange(i);
            }
            if(t > 0) {
                t--;
                this.rearrange(t);
            }
        }
        
    }
    

Above we have the iteration through the array. t and i iterate in opposing directions, just so we're clear on what's happening.

 

    public void rearrange(int indexToArrangeFrom) {
        
        int[] lowerValues = new int[valuesToSort.length];
        int[] equalValues = new int[valuesToSort.length];
        int[] higherValues = new int[valuesToSort.length];
        
        int lowerValueIndex = 0;
        int equalValueIndex = 0;
        int higherValueIndex = 0;
            
        for(int i = 0; i < valuesToSort.length; i++) {
            if(valuesToSort[i] < valuesToSort[indexToArrangeFrom]) {
                lowerValues[lowerValueIndex] = valuesToSort[i];
                lowerValueIndex++;                
            }
            else if(valuesToSort[i] == valuesToSort[indexToArrangeFrom]) {
                equalValues[equalValueIndex] = valuesToSort[i];
                equalValueIndex++;
            }
            else {
                higherValues[higherValueIndex] = valuesToSort[i];
                higherValueIndex++;
            }
        }
        
        int valuesIndex = 0;
        
        for(int i = 0 ; i < lowerValueIndex ; i++) {
            valuesToSort[valuesIndex] = lowerValues[i];
            valuesIndex++;
        }
        
        for(int i = 0 ; i < equalValueIndex ; i++) {
            valuesToSort[valuesIndex] = equalValues[i];
            valuesIndex++;
        }
        
        for(int i = 0 ; i < higherValueIndex ; i++) {
            valuesToSort[valuesIndex] = higherValues[i];
            valuesIndex++;
        }        
    }
    

We first iterate the array checking the value of each element relative to the indexToArrangeFrom variables element value,separating values into three arrays, one containing values higher than the pivot, one containing equal values and another containing higher values. We then iterate these arrays and place their values back into the valuesToSort array, rebuilding and sorting (for one pass) the array.

 

    public static void main(String[] args) {
        QuickSort sq = new QuickSort(args.length);
        
        for(int i = 0 ; i < args.length; i++) {
            sq.valuesToSort[i] = Integer.valueOf(args[i]);
        }        
        sq.sort();
        for(int i = 0 ; i < sq.valuesToSort.length; i++) {
            System.out.print(sq.valuesToSort[i]+",");
        }
        System.out.print("***");
    }
    

Above we have more boilerplate that also allows you to run this program from the command line.

 

 

    public boolean isInOrder() {
        boolean inOrder = true;
        
        for(int i = 1; i < valuesToSort.length; i++) {
            if(valuesToSort[i] > valuesToSort[i-1]) {
                inOrder = false;
            }
        }
        
        return inOrder;
    }
}

Finally we have a method that allows us to check whether the array is in sorted order or not.

And that's a wrap! Quick sort is an efficient algorithm that isn't crazy complicated and performs pretty well. 

Good luck!

Marc