CODEWITHSUNDEEP
pythonquicksort
Hippity Hoopla
Hippity Hoopla

Reputation: 68

Quicksort python implementation

I am trying to write an implementation of quicksort where the pivot element is pseudo-random. I have looked at various posts online, many on SO but I am still having issues. Here is my code:

def quickSort(lst, a, b):
    if a < b:
        pivot = partition(lst, a, b)
        quickSort(lst, a, pivot-1)
        quickSort(lst, pivot+1, b)
    return lst



def partition(lst, a ,b):
    pivot = random.randint(a,b)
    for i in range(a,b):
        if lst[i] < lst[b]:
            lst[i],lst[pivot] = lst[pivot],lst[i]
            pivot += 1
    lst[pivot],lst[b] = lst[b],lst[pivot]
    return pivot

This code is practically identical to the code provided for the answer to this question: quick sort python recursion but instead of using the start element as the pivot, I am using random. I keep getting this error: 

 in partition
    lst[pivot],lst[b] = lst[b],lst[pivot]
IndexError: list index out of range

I have looked that up and I think it means that I am trying to reference an element of the list that doesn't exist or is out of the range of the list. Why is this happening?

I have also tried using the style of quicksort implemented in this link and I am getting the same error: Quicksort implementation in Python

Upvotes: 1

Views: 2843

Answers (1)

Blckknght
Blckknght

Reputation: 104712

I think you've misunderstood what the pivot value in partition means. It's not the index of the element that's being partitioned around. Not until the end of the function anyway. The actual pivot value is lst[b], the last element in the portion of the list being partitioned. That value gets moved to the pivot location on the next to last line of the function.

The pivot value is simply the index where the "high" values start. Picking a random initial value for pivot breaks the algorithm, since it may get incremented off the end of the list (consider what happens if random.randint(a, b) returns b).

If you want a random value to partition around, pick a random index and swap it's value with lst[b] before running the rest of the algorithm as normal (with the pivot index starting at a):

def partition(lst, a ,b):
    random_index = random.randint(a,b)  # pick random index, its value will be our pivot val
    lst[b], lst[random_index] = lst[random_index], lst[b]   # swap the value with lst[b]

    pivot = a        # run the rest of the partition code as it was in the original version
    for i in range(a,b):
        if lst[i] < lst[b]:
            lst[i],lst[pivot] = lst[pivot],lst[i]
            pivot += 1
    lst[pivot],lst[b] = lst[b],lst[pivot]
    return pivot

Upvotes: 1

Related Questions