Quick sorting algorithm states using middle element as pivot

Question

I need help understanding exactly how the quick sort algorithm works. I've been watching teaching videos and still fail to really grasp it completely.

I have an unsorted list: 1, 2, 9, 5, 6, 4, 7, 8, 3 And I have to quick sort it using 6 as the pivot. I need to see the state of the list after each partition procedure.

My main problem is understanding what the order of the elements are before and after the pivot. So in this case if we made 6 the pivot, I know the numbers 1 - 5 will be before 6 and 7 - 9 will go after that. But what will the order of the numbers 1 - 5 be and 7 - 9 be in the first partition given my list above?

Here is the partition algorithm that I want to use (bear in my I'm using the middle element as my initial pivot):

1. Determine the pivot, and swap the pivot with the first element of the list.

Suppose that the index smallIndex points to the last element smaller than the pivot. The index smallIndex is initialized to the first element of the list.

2. For the remaining elements in the list (starting at the second element) If the current element is smaller than the pivot

   a. Increment smallIndex b. Swap the current element with the array element pointed to by smallIndex.

3. Swap the first element, that is the pivot, with the array element pointed to by smallIndex.

It would be amazing if anyone could show the list after each single little change that occurs to the list in the algorithm.

Answer 1

It doesn't matter.

All that matters - all that the partitioning process asserts - is that, after it has been run, there are no values on the left-hand side of the center point that emerges that are greater than the pivot and that there are no values on the right-hand side that are less than the pivot value.

The internal order of the two partitions is then handled in the subsequent recursive calls for each half.