Writing a Quicksort with one loop

Question

My brother wants me to optimize my code by only having one loop. I don't see how a Quicksort can only have one loop and work. (He told me to remove the inner loop)

public class QuickSort {
public static void Quick(int[] target, int lo, int hi) {
    if (lo >= hi) {
        return;
      }
    Random numberGenerator = new Random();
    int pivot = numberGenerator.nextInt(hi-lo)+lo;
    int pivotValue = target[pivot];
    target[pivot]=target[hi];
    target[hi]=pivotValue;
    pivot=hi;
    int counter;
    for(counter=lo; counter<pivot ; counter++){
        while(target[counter]>target[pivot]){ 
            if(pivot-counter==1){
                int temp=target[counter];
                target[counter]=target[pivot];
                target[pivot]=temp;
                //return; //possibly the problem
            }
            else{
                int temp1 = target[pivot-1];
                int temp2 = target[pivot];
                target[pivot]=target[counter];
                target[pivot-1]=temp2;
                target[counter]=temp1;
                pivot=pivot-1;
            }
        }
    }
    Quick(target, lo, counter-1);
    Quick(target, counter, hi); 
}

public static void main(String[] args) {
    int sizeOfArray = 10;
    int numberOfTests = 1000;

    int numFailed = 0;
    for (int i = 0; i < numberOfTests; i++)
    {
        int[] iNeedSorting = new int[sizeOfArray];
        populateArrayWithRandomNums(iNeedSorting);
        //System.out.printf("Test #%d\n", i);
        //System.out.printf("Original Array: %s\n", intArrayToString(iNeedSorting));
        Quick(iNeedSorting, 0, iNeedSorting.length-1);

        if (!isSorted(iNeedSorting)) {numFailed++;}
        //System.out.printf("New Array: %s\n\n", intArrayToString(iNeedSorting));
    }
    System.out.printf("%d test failed\n\n", numFailed);
}

}

Answer 1

According to the academics (or at least the quicksort algorithm that I studied and I also made a quick check to the data structures and algorithms book), quicksort is about recursion. Partitioning the dataset (which needs a loop) and then recursively sorting the left and right sides of it.

Answer 2

It is possible to do the partitioning step in one loop. Check out the Dutch National Flag problem for three colours.

Related: http://stackoverflow.com/questions/1759171/whats-wrong-with-my-dutch-national-flag-algorithm

Answer 3

Quicksort is conceptually two loops: an inner partitioning loop that iterates over the whole array, and an outer division loop usually expressed through recursion. Here, you have the division part done in the classical way, but your partitioning is a little complicated.

Your outer for loop moves the counter one step to the left (assuming you write your array from left to right). Your inner for loop moves the pivot one step to the right (except in the special case where the counter has almost reached the pivot and you do a final swap). There's nothing that moves the counter back towards the right or the pivot back towards the left. So you're not doing extra work because of the two loops, it's a matter of clarity rather than efficiency.

A common way to write partitioning is to use a single loop with two counters instead of one. One counter is the one you used: everything to the left of it is less than the pivot. The other counter plays a symmetric role: everything to the right of it is less than the pivot. The loop body does the following:

• if both target[left_counter] and target[right_counter] are out-of-place, swap them; after this both target[left_counter] and target[right_counter] are on the desired side of the array, so increment left_counter and decrement right_counter;

• otherwise: if target[left_counter] is on the desired side, increment left_counter; if target[right_counter] is on the desired side, decrement right_counter.

The loop terminates when the counters cross over. It will eventually terminate because at least one of the counters moves at each iteration.