Implementing Median of Median Selection Algorithm in Python

Question

Okay. I give up. I've been trying to implement the median of medians algorithm but I am continually given the wrong result. I know there is a lot of code below, but I can't find my error, and each chunk of code has a fairly process design. Quicksort is what I use to sort the medians I get from the median of medians pivot selection. Should be a straightforward quicksort implementation. getMean simply returns the mean of a given list.

getPivot is what I use to select the pivot. It runs through the list, taking 5 integers at a time, finding the mean of those integers, placing that mean into a list c, then finding the median of c. That is the pivot I use for the dSelect algorithm.

The dSelect algorithm is simple in theory. The base case returns an item when the list is 1 item long. Otherwise, much like in quickSort, I iterate over the list. If the number I am currently on, j, is less than the pivot, I move it to the left of the list, i, and increment i. If it is larger, I move it to the right of the list, i + 1, and do not increment i. After this loops through the entire list, I should have the pivot in its proper index, and print statements indicate that I do. At this point, I recurse to the left or the right depending on whether the pivot is greater than or less than the position I am trying to find.

I am not sure what other print statements to test at this point, so I'm turning to anyone dedicated enough to take a stab at this code. I know there are related topics, I know I could do more print statements, but believe me, I've tried. What should be a simple algo has got me quite stumped.

def quickSort(m, left, right):
    if right - left <= 1:
        return m
    pivot = m[left]
    i = left + 1
    j = left + 1
    for j in range(j, right):
        if m[j] < pivot:
            m[j], m[i] = m[i], m[j]
            i += 1
        elif m[j] == pivot:
            m[j], m[i] = m[i], m[j]
    print m
    m[left], m[i-1] = m[i-1], m[left]
    m = quickSort(m, left, i-1)
    m = quickSort(m, i, right)
    print m
    return m
def getMedian(list):
    length = len(list)
    if length <= 1:
        return list[0]
    elif length % 2 == 0:
        i = length/2
        return list[i]
    else:
        i = (length + 1)/2
        return list[i]
def getPivot(m):
    c = []
    i = 0
    while i <= len(m) - 1:
        tempList = []
        j = 0
        while j < 5 and i <= len(m) - 1:
            tempList.append(m[i])
            i = i + 1
            j = j + 1
        tempList = quickSort(tempList, 0, len(tempList) - 1)
        c.append(getMedian(tempList))
    c = quickSort(c, 0, len(c) - 1)
    medianOfMedians = getMedian(c)
    return medianOfMedians

def dSelect(m, position):
    pivot = getPivot(m)
    i = 0
    j = 0
    if len(m) <= 1:
        return m[0]
    for j in range(0, len(m)):
        if m[j] < pivot:
            m[j], m[i] = m[i], m[j]
            i += 1
        elif m[j] == pivot:
            m[j], m[i] = m[i], m[j]
        print "i: " + str(i)
        print "j: " + str(j)
    print "index of pivot: " + str(m.index(pivot))
    print "pivot: " + str(pivot) + " list: " + str(m)
    if m.index(pivot) == position:
        return pivot
    elif m.index(pivot) > position: 
        return dSelect(m[0:i], position)
    else:
        return dSelect(m[i:], position - i)

Ryan O'Neill · Accepted Answer · 2012-11-15 05:24:40Z

1

The biggest issue is with this line here:

i = (length + 1)/2

if list = [1, 2, 3, 4, 5, 6, 7] the answer should be 4 which is list[3]. Your version looks like the following:

i = (7 + 1) / 2

and so i is equal to 4 instead of 3. Similar problem with the even length list part although that shouldn't be as big of an issue.

answered Nov 15, 2012 at 5:24

Ryan O'Neill

3,75724 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user1427661 Over a year ago

Good point; forgot to take into consideration zero indexing. But it seems like subtracting one from both equations should fix that fairly trivially. Yet I still do not get an accurate result after that change...

Ryan O'Neill Over a year ago

Another item I notice right away is that your quickSort algorithm does not appear to work for sorting two elements: def quickSort(m, left, right): if right - left <= 1: return m if m = [2, 1], left = 0, and right = 1 it will just return m which is incorrect.

Collectives™ on Stack Overflow

Implementing Median of Median Selection Algorithm in Python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related