CODEWITHSUNDEEP
pythonalgorithmsortingquicksort
Hunter Mitchell
Hunter Mitchell

Reputation: 7293

QuickSort with Pivot Function issue?

I have been looking at this for the past couple hours and can still not understand where I have messed up. I keep getting Index out of bounds errors like below:

enter image description here

Each small edit or change i have done, has run me into another error, then i end back up here after trying to simplify my code.

def quickSort(alist):
    firstList = []
    secondList = []
    thirdList = []

    if(len(alist) > 1):
        #pivot = pivot_leftmost(alist)
        #pivot = pivot_best_of_three(alist)
        pivot = pivot_ninther(alist)
        #pivot = pivot_random(alist)

        for item in alist:
            if(item < pivot):
                firstList.append(item)
            if(item == pivot):
                secondList.append(item)
            if(item > pivot):
                thirdList.append(item)
        sortedList = quickSort(firstList) + secondList + quickSort(thirdList)
        return sortedList
    else:
        print("list:", alist)
        print("sorted, nothing to do") #debug
        print("") #debug
        return alist

def pivot_ninther(alist):
    listLength = int(len(alist))
    third = int(listLength / 3)

    leftList = alist[:third]
    midlist = alist[third:(third * 2)]
    lastlist = alist[(third * 2):(third * 3)]

    leftBest = pivot_best_of_three(leftList)
    midBest = pivot_best_of_three(midlist)
    lastBest = pivot_best_of_three(lastlist)

    pivots = [leftBest, midBest, lastBest]

    return pivot_best_of_three(pivots)

I am pretty sure a fresh pair of eyes can easily find it, but i have been lookig at it for hours. Thanks!

UPDATE: (My Best_of_three function)

def pivot_best_of_three(alist):
    leftmost = 0
    middle = int(len(alist) / 2)
    rightmost = len(alist) - 1

    if (alist[leftmost] <= alist[middle] <= alist[rightmost] or alist[rightmost] <= alist[middle] <= alist[leftmost]):
        return alist[middle]
    elif (alist[middle] <= alist[leftmost] <= alist[rightmost] or alist[rightmost] <= alist[leftmost] <= alist[middle]):
        return alist[leftmost]
    else:
        return alist[rightmost]

Upvotes: 1

Views: 111

Answers (2)

rcgldr
rcgldr

Reputation: 28911

Try a smaller count (<= 20) and check to see what happens in pivot_ninther() when third == 0 (at the deepest level of recursion)? Seems like it would create empty arrays and then try to index them.

The code should check to make sure length >= 9 before calling pivot_ninther(), then >= 3 if calling ...best_of_three(). If just one or two items, pick one.

Suggestion, after you get the quicksort to work, back up the source code and rather than make new arrays, the pivot function should work with the original array and first / middle / last indexes.

You can use swaps to simplify finding the median of 3. This will help in cases like starting with a reversed order array.

    // median of 3
    i = lo, j = (lo + hi)/2, k = hi;
    if (a[k] < a[i])
        swap(a[k], a[i]);
    if (a[j] < a[i])
        swap(a[j], a[i]);
    if (a[k] < a[j])
        swap(a[k], a[j]);
    pivot = a[j];

wiki article:

http://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot

Upvotes: 0

PM 2Ring
PM 2Ring

Reputation: 55489

The IndexError occurs when pivot_best_of_three tries to find the rightmost member of a list of zero items. The simple way to fix that is to simply not pass it such lists. :)

Here are slightly modified versions of those functions. I've tested these versions with lists of various lengths, down to length zero, and they appear to function correctly.

def pivot_ninther(alist):
    listLength = len(alist)
    if listLength < 3:
        return alist[0]

    third = listLength // 3
    leftList = alist[:third]
    midlist = alist[third:-third]
    lastlist = alist[-third:]

    leftBest = pivot_best_of_three(leftList)
    midBest = pivot_best_of_three(midlist)
    lastBest = pivot_best_of_three(lastlist)

    pivots = [leftBest, midBest, lastBest]

    return pivot_best_of_three(pivots)

def pivot_best_of_three(alist):
    leftmost = alist[0]
    middle = alist[len(alist) // 2]
    rightmost = alist[-1]

    if (leftmost <= middle <= rightmost) or (rightmost <= middle <= leftmost):
        return middle
    elif (middle <= leftmost <= rightmost) or (rightmost <= leftmost <= middle):
        return leftmost
    else:
        return rightmost

As you can see, I've simplified pivot_best_of_three so it doesn't index alist multiple times for the same value.

But it can be simplified further by using a simple sorting network:

def sort3(a, b, c):
    if c < b: b, c = c, b
    if b < a: a, b = b, a
    if c < b: b, c = c, b
    return a, b, c

def pivot_best_of_three(alist):
    leftmost = alist[0]
    middle = alist[len(alist) // 2]
    rightmost = alist[-1]
    return sort3(leftmost, middle, rightmost)[1]

Upvotes: 2

Related Questions