# Understanding how quicksort operates

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 */

• 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 – wundermahn Oct 12 '18 at 1:03
• 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. – John L. Oct 12 '18 at 1:12
• 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. – wundermahn Oct 12 '18 at 1:22
• I dont see an answer posted, did I miss it? @Apass.Jack – wundermahn Oct 12 '18 at 3:10

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

// 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


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.

• 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? – wundermahn Oct 12 '18 at 20:10
• 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. – John L. Oct 12 '18 at 20:14
• @JerryM. You can add print statement after each line of code of the partition routine in QuickSort.java. You will see what is happening. – John L. Oct 12 '18 at 20:57
• 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. – wundermahn Oct 12 '18 at 22:13
• 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? – John L. Oct 13 '18 at 0:40

“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.

• I assume you meant "You start looking for items smaller than or equal to the pivot from the left." – John L. Oct 12 '18 at 13:09
• 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. – John L. Apr 18 '20 at 0:27