How to fix the Conquer step of this iterative quicksort implementation following Khan Academy's example?

Question

For educational purposes I am trying to learn the quick sort algorithm. Instead of checking out an implementation on the web or trying to implement directly from the pseudocode on wikipedia, I am trying a "hard way" approach.

I watched this lecture from CS50 https://www.youtube.com/watch?v=aQiWF4E8flQ&t=305s in order to understand how the numbers move while being "quick sorted". My implementation, which I will show bellow, works perfectly for the example provided on the video. The example on the video of an initial unsorted array is this:

That's my code in Python 3:

len_seq = int(input())

print("len_seq",len_seq)

seq_in = list(map(int,(input()).split()))

print("seq_in",seq_in)

def my_quick_sort(seq):

    wall_index = 0

    pivot_corect_final_index_list = [] 

    while wall_index<len_seq:

        pivot = seq[-1]
        print("pivot",pivot)

        print("wall_index",wall_index)

        for i in range(wall_index,len_seq):
            print ("seq[i]",seq[i])
            if seq[i]<pivot:
                print("before inside swap,", seq)
                seq[wall_index],seq[i]=seq[i],seq[wall_index]
                print("after inside swap,", seq)
                wall_index = wall_index + 1
                print ("wall_index",wall_index)

        print("before outside swap,", seq)

        seq[wall_index],seq[-1]=seq[-1],seq[wall_index]
        print("after outside swap,", seq)

        pivot_corect_final_index = wall_index
        print ("pivot correct final index",pivot_corect_final_index)

        pivot_corect_final_index_list.append(pivot_corect_final_index)
        print ("pivot_corect_final_index_list",pivot_corect_final_index_list)

        wall_index = wall_index + 1
        print ("wall_index",wall_index)


    return seq

print(my_quick_sort(seq_in))

To use harvard's CS50 example in my code you need to input this:

9
6 5 1 3 8 4 7 9 2

The algorithm works fine and returns the correct output:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Continuing my study, I tried to implement Khan Academy's example: https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/overview-of-quicksort

The unsorted list in this case is:

[9, 7, 5, 11, 12, 2, 14, 3, 10, 6]

You need to input the following in my code in order to run it:

10
9 7 5 11 12 2 14 3 10 6

Differently from the Harvard example, in this case my implementation does not work perfectly. It returns:

[5, 2, 3, 6, 7, 9, 10, 11, 12, 14]

As you see, all the numbers that I treated as pivots end in the correct position. However, some numbers behind the pivots are not right.

Reading khan academy's article it seems that my implementation is right on the partition step. However, it is not right on the conquer step. I am trying to avoid looking to a final solution. I am trying to improve what I have build so far. Not sure if this is the best method, but that's what I am trying right now.

How can I fix the conquer step? Is it necessary to introduce a recursive approach? How can I do that inside my iterative process going on? And should that step be introduced after successfully treating each pivot?

Thanks for the patience of reading this long post.

Answer 1

Can't comment, not enough reputation.

In the first pass of your algorithm, you correctly place all elements smaller than the pivot to the left of the pivot. However, since your value of wall_index increases (e.g. from 0 to 1), you ignore the leftmost element with index 0 (it might not be in the correct position, so it should not be ignored).

In the Khan academy test case, the number 5 gets placed at the leftmost index in the first pass, and then gets ignored by subsequent passes, thus it gets stuck on the left. Similarly, trying this modification of the harvard example

9
6 5 1 3 8 4 7 2 9

yields

[6, 5, 1, 3, 8, 4, 7, 2, 9]

After the first partitioning, you have to make sure to apply quicksort to both the arrays to the left and to the right of the pivot. For example, after the first pivot (6) is placed in the correct position for the Khan example (what you labeled as the outside swap),

[5, 2, 3, 6, 12, 7, 14, 9, 10, 11]
 <--1-->  p  <--------2--------->

you have to apply the same quicksort to both subarrays 1 and 2 in the diagram above. I suggest you try out the recursive implementation first, which will give you a good idea of the algorithm, then try to implement it iteratively.