1
$\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$
4
  • $\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$
    – artemis
    Oct 12, 2018 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$
    – John L.
    Oct 12, 2018 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$
    – artemis
    Oct 12, 2018 at 1:22
  • $\begingroup$ I dont see an answer posted, did I miss it? @Apass.Jack $\endgroup$
    – artemis
    Oct 12, 2018 at 3:10

2 Answers 2

1
$\begingroup$

Please run your code with four more lines of printing statements, as shown below. 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 + ": ");  // add this line
printArray(arr);  // add this line

    // 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 + ": ");  // add this line
printArray(arr);  // add this line

Aside from the question proper, what you needed most is an Integrated 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 different recommendations. Once you are able to use that machinery, you will be able to answer others' 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$
5
  • $\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$
    – artemis
    Oct 12, 2018 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$
    – John L.
    Oct 12, 2018 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$
    – John L.
    Oct 12, 2018 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$
    – artemis
    Oct 12, 2018 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$
    – John L.
    Oct 13, 2018 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$
2
  • $\begingroup$ I assume you meant "You start looking for items smaller than or equal to the pivot from the left." $\endgroup$
    – John L.
    Oct 12, 2018 at 13:09
  • $\begingroup$ Just to say I did not downvote. In fact, I appreciate that you went to the point straightforwardly. If you reply to my message, I will upvote. $\endgroup$
    – John L.
    Apr 18, 2020 at 0:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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