0
$\begingroup$

I am having a hard time understanding the quick sort partition operation. I understand what partition is supposed to do, I just don't understand how partition does it. Specifically, I don't understand how the two subarrays (q-1, q+1) are constructed. I have looked at various other SE articles, such as:

I understand the notion of:
1. Select a pivot (typically the last item in the array, at least in simplified methods)
2. Create one subarray to the left of items smaller than the pivot
3. Create one subarray to the right of items larger than the pivot
4. Recursively call partition on each of the subarrays

However, in the following example, is where I get lost

8 1 9 3 5 7 6

Here, 6 is my pivot

7 is larger than 6, so my array now looks like:

8 1 9 3 5 6 7

Here is where I get lost. Does the rest of my sequencing look like:

8 1 3 5 6 9 7
1 3 5 6 8 9 7

Where:
1 3 5 is my smaller array and
8 9 7 is my larger array (where each then get partition recursively called?)

I am most confused by the proper construction of the larger and smaller arrays and in which order to put the numbers in. Any help is appreciated. I am happy to edit my post for clarity if I am unclear.

EDIT:
I tried using some base code from this address, and edited it slightly to create more print statements, but still don't understand why it would sort to:
1 3 5 6 9 7 8 and not 1 3 5 6 8 9 7 initially

Here is the code:

class QuickSort 
{ 
    /* This function takes last element as pivot, 
       places the pivot element at its correct 
       position in sorted array, and places all 
       smaller (smaller than pivot) to left of 
       pivot and all greater elements to right 
       of pivot */
    int partition(int arr[], int low, int high) 
    { 
        int pivot = arr[high];  
        int i = (low-1); // index of smaller element 
        for (int j=low; j<high; j++) 
        { 
            // If current element is smaller than or 
            // equal to pivot 
            if (arr[j] <= pivot) 
            { 
                i++; 

                // swap arr[i] and arr[j] 
                int temp = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = temp; 
            } 
        } 

        // swap arr[i+1] and arr[high] (or pivot) 
        int temp = arr[i+1]; 
        arr[i+1] = arr[high]; 
        arr[high] = temp; 

        return i+1; 
    } 


    /* The main function that implements QuickSort() 
      arr[] --> Array to be sorted, 
      low  --> Starting index, 
      high  --> Ending index */
    void sort(int arr[], int low, int high) 
    {

        printArray(arr);

        if (low < high) 
        { 
            /* pi is partitioning index, arr[pi] is  
              now at right place */
            int pi = partition(arr, low, high); 

            // Recursively sort elements before 
            // partition and after partition 
            sort(arr, low, pi-1); 
            sort(arr, pi+1, high); 
        } 
    } 

    /* A utility function to print array of size n */
    static void printArray(int arr[]) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i]+" "); 
        System.out.println(); 
    } 

    // Driver program 
    public static void main(String args[]) 
    { 
        int arr[] = {8, 1, 9, 3, 5, 7, 6}; 
        int n = arr.length; 

        QuickSort ob = new QuickSort(); 
        ob.sort(arr, 0, n-1); 

        System.out.println("sorted array"); 
        printArray(arr); 
    } 
} 
/*This code is contributed by Rajat Mishra */
$\endgroup$
  • $\begingroup$ I guess the generic. I am referencing regular PARTITION in CLRS, not RANDOMIZED or HOARE. Sorry, I don't know if generic is the right term, but the most basic one covered in CLRS $\endgroup$ – wundermahn Oct 12 '18 at 1:03
  • $\begingroup$ Aside from the question proper, I believe what you needed most is an IDE where you can trace code execution and check the values of all relevant variables step by step. Once you are able to use that machinery, I guarantee that you will be able to answer other's questions such as this one just like I am answering your question right now. $\endgroup$ – Apass.Jack Oct 12 '18 at 1:12
  • $\begingroup$ Hi @Apass.Jack I have actually tried doing that using command line and some java code I borrowed from an external resource. I will edit my question. $\endgroup$ – wundermahn Oct 12 '18 at 1:22
  • $\begingroup$ I dont see an answer posted, did I miss it? @Apass.Jack $\endgroup$ – wundermahn Oct 12 '18 at 3:10
1
$\begingroup$

Please run your code with four more lines of printing statements at https://repl.it/repls/RadiantFinancialAstronomy. Once you have seen the output, it will be immediate for you see what is happening. Basically, given the sequence 8 1 9 3 5 7 6, the partition routine rearranges it to 1 3 5 8 9 7 6 at first. Then it exchanges 6 with 8, the first element beyond the end of elements not larger than 6. So the sequence becomes 1 3 5 6 9 7 8.

System.out.print("Pivot with " + pivot + ": "); 
printArray(arr); 

    // swap arr[i+1] and arr[high] (or pivot) 
    int temp = arr[i+1]; 
    arr[i+1] = arr[high]; 
    arr[high] = temp; 

System.out.print("Exchange   " + pivot + ": ");
printArray(arr); 

Aside from the question proper, what you needed most is an Integrate Development Environment (IDE) where you can trace code execution and check the values of all relevant variables step by step easily. Using the command line can only serve as a temporary measure. I recommend Intellij Community Edition; others might have a different recommendation. Once you are able to use that machinery, you will be able to answer other's questions such as this one just like I have answered your question. Well, as long as you will program in java, an IDE is a must unless you do not mind lagging behind other by a factor of 2 to 10. Just a bit of unsolicited advice that I offer to everyone of my local students. It is entirely up to you what to do, of course.

$\endgroup$
  • $\begingroup$ It is not clear why 6 and 8 exchange locations instead of 6 and 7. 7 is also greater than 6, so why do I exchange locations with 8? $\endgroup$ – wundermahn Oct 12 '18 at 20:10
  • $\begingroup$ That is what the code says. Are you able to run the code repl.it/repls/RadiantFinancialAstronomy? Just click that URL and then hit the "run" button. $\endgroup$ – Apass.Jack Oct 12 '18 at 20:14
  • $\begingroup$ @JerryM. You can add print statement after each line of code of the partition routine in QuickSort.java. You will see what is happening. $\endgroup$ – Apass.Jack Oct 12 '18 at 20:57
  • $\begingroup$ yes, I ran your code there and added additional print statements. I see WHAT is happening. Simply showing the movements does not explain WHY it is happening. $\endgroup$ – wundermahn Oct 12 '18 at 22:13
  • $\begingroup$ Yes, I agree what is happening is not why it is happening. Are you able to correlate what is happening with the code line by line now? Are you able to use an IDE such as IntelliJ to trace step by step now? $\endgroup$ – Apass.Jack Oct 13 '18 at 0:40
-1
$\begingroup$

“7 is larger than 6...”

Stop right there. You start looking for items larger than the pivot from the left. So you process 8, then you process 9.

$\endgroup$
  • $\begingroup$ I assume you meant "You start looking for items smaller than or equal to the pivot from the left." $\endgroup$ – Apass.Jack Oct 12 '18 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.