Creating a Single Argument Quicksort Function - Python

Question

I'm trying to learn how to create a standalone recursive quicksort function in Python but I'm having trouble. I'm tasked with accepting a single argument, the unsorted list, and partitioning the list for recursion within the same quicksort function.

def quicksort(copyLyst):
    low = len(copyLyst) - len(copyLyst)   
    high = len(copyLyst) - 1              

    # Base Case
    if high <= low:
        return 

    center = low + (high - low) // 2
    pivot = copyLyst[center]

    first = low
    last = high

    # Partitioning
    done = False
    while not done:
        while copyLyst[first] < pivot:
            first = first + 1
        while pivot < copyLyst[last]:
            last = last - 1
        if first >= last:
            done = True
        else:
            swap = copyLyst[first]
            copyLyst[first] = copyLyst[last]
            copyLyst[last] = swap
            first = first + 1
            last = last - 1

    leftCopy = copyLyst[low:last + 1]
    quicksort(leftCopy)

    rightCopy = copyLyst[last + 1:high]
    quicksort(rightCopy)

I'm hoping to keep much of my original code as I can, because I'm still learning about data structures and I think that would help me the best conceptually.

I've tried adjusting the range on the left and right recursive calls, I tried rewriting the entire function in new variables, I've double checked that the index locations don't conflict.

I've gone through everything compared to my textbook. I don't know what I did wrong.

ela16 · Answer

Your code has major flaws and you have some unnecessary steps and complications in your implementations. Let's look at what's wrong first.

Your low is always 0, so you don't need to compute it or include it in the center computation.

The second, and the most important part, is that you're keeping the pivot in its original place, but you are not accounting for that. So at some point, either your first or last index will point to the pivot, and your code treats it as the rest of the numbers. Take a look at the example below to better understand this:

copyLyst = [5, 3, 7, 4, 1]
pivot = 7
first = 5
last = 1

first(5) < pivot(7): # 5 stays, first points to the next element(3)
[5, 3, 7, 4, 1]
first(3) < pivot(7): # 3 stays, first points to the next element(7)
[5, 3, 7, 4, 1]
## now we are at the pivot, but the code doesn't know that
first(7) not < pivot(7): #we now look at the right side starting from last
[5, 3, 7, 4, 1]
last(1) < pivot(7): # 1 needs to move, based on your code, we swap it with the first, and what's the first here? It's the pivot. The list now looks like this:
[5, 3, 1, 4, 7]
# the last index now points at 4 and the first points at 1, and since 1 is before 4,
# your while loop terminates, but the list is not partitioned correctly

Your code structure is problematic, and I suspect that you're trying to follow some pseudocode that you have quite literally. So it might not be possible to preserve much of your current code while keeping it clean and simple.

You can expand the base case. The high is never less than low since low is always zero. And you can base it on the length of the list:

if len(copyLyst) <= 1:
        return

You should probably keep the pivot out of your way when you're performing the partitioning part. The easiest way is to place it at the very end, such as:

pivot = copyLyst[center]
# swap the pivot with the last element
copyLyst[center] = copyLyst[high]
copyLyst[high] = pivot
# move the last element pointer to the left (since it's pointing at the pivot)
high = high - 1

The while loops that you have can cause you a lot of headaches to deal with, so instead of having two while loops that approach each other from different ends, you can iterate once and place any number smaller than the pivot at the beginning of the list (look at the example here https://www.geeksforgeeks.org/python-program-for-quicksort/).

I think you now have enough feedback to work with on solving your problem. Good luck.

Creating a Single Argument Quicksort Function - Python

1 Answers