Quick-sorting Partition: how to get Right Pivot, Right First and other Variations working

Question

I'm a student in APCS class in my highschool senior year studying for my midterms. My teacher said that below is the optimal way of coding "Ascending sorting - select right pivot and when partitioning look at the left first / Descending sorting - select left pivot and when partitioning look at the right first"

At first I couldn't understand why so I just tried all cases I've tried for Ascending Sorting

(1)selecting the right pivot / looking at the left first

(2)selecting the right pivot / looking at the right first

(3)selecting the left pivot / looking at the left first

(4)selecting the left pivot / looking at the right first

But I've only got the (1) type to work. There is some logical errors in the rest 3 versions. From experience I know that (2)~(4) is harder to code By experience and writing down on paper I know that if I use the right pivot and look at the right first there will be a problem using the normal way of QuickSort.

TO SUM UP: QUESTIONS [1] What is the exact reason version (2)~(4) is harder to code than (1)? [2] Can any one of you amazing coders help me complete (2)~(4)

here's code for version (1) working in java

///* MOST SIMPLE VERSION OF QUICKSORT. ASCENDING, END PIVOT, LEFT FIRST 
SWEEP, LEFT & RIGHT COMPARISON
    public static void endPivSortV1(int[] a, int start, int end) {
        if(start < end) {
            int pVal = a[end];
            int left = start;
            int right = end; 
            //QUESTION: right = end - 1 

            while(true) {
                while(a[left] <= pVal && left < right) //left, 
                    left++;

                while(a[right] >= pVal && left < right)
                    right--;

                if(left == right)
                    break;

                swap(a, left, right);
            }
            swap(a, left, end);

            endPivSortV1(a, start, left - 1);
            endPivSortV1(a, left + 1, end);
        }   
    } //*/

I've copy and pasted this code and changed just of bit of it to create versions (2)~(4) but they are not working.

public static void endPivSortV2(int[] a, int start, int end) {
        if(start < end) {
            int pVal = a[end];
            int left = start - 1;
            int right = end + 1;

            while(true) {
                while(a[right--] >= pVal && left < right);

                while(a[left++] <= pVal && left < right);

                if(left == right)
                    break;

                swap(a, left, right);
            }
            swap(a, left, end);

            endPivSortV2(a, start, left - 1);
            endPivSortV2(a, left + 1, end);
        }   
    }

This is the one where I try to look at the right first rather than left. (the while sentence for changing right is located in front of the one that changes left) I know that the code is super sloppy and is full of errors but cut me some slack as I've only coded very part time for 1 yr in highschool...

Thank you. This is my first post on here so don't go too hard on me :D

Answer 1

(1) and (4) are essentially the same, you can count on the scan to run into the pivot value as a way to stop a loop, without having to do a bounds check. For (1), ... < pivot will stop if it reaches the pivot on the right. For (4), ... > pivot will stop if it reaches the pivot on the left.

(2) and (3) require a check so the index for the scan does not go beyond the bounds of an array, or you can "cheat" by swapping the pivot to the other end of the array and using the logic from (1) or (4).

Note - all of these are variations of Lomuto partition scheme. There's also Hoare partition scheme, which normally chooses the middle value as pivot, and scans from both the left and right (using separate indexes for the two scans). The scans stop when the indexes cross each other.