Implementing the quick sort with median of three

Question

I've stumbled upon the quick sort algorithm in "Problem Solving with Algorithms and Data Structures", by Brad Miller and David Ranum (http://interactivepython.org/runestone/static/pythonds/SortSearch/sorting.html#the-quick-sort).

The quick sort algorithm that is presented there, takes the first value in a list to be a pivot value. Exercise is to modify a program to choose pivot value as median of three. Here's the original script:

def quickSort(alist):
   quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
   if first<last:

       splitpoint = partition(alist,first,last)

       quickSortHelper(alist,first,splitpoint-1)
       quickSortHelper(alist,splitpoint+1,last)


def partition(alist,first,last):
   pivotvalue = alist[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

       while leftmark <= rightmark and \
               alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and \
               rightmark >= leftmark:
           rightmark = rightmark -1

       if rightmark < leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp


   return rightmark

And I modified it a bit, first added median() function:

def median(data):
    sd = sorted(data)
    N = len(data) - 1
    a = sd[N // 2]
    b = sd[(N + 1) // 2]
    return (a+b) // 2

Then, in partition() function, modified pivotvalue to be:

pivotvalue = median([alist[0]] + [alist[len(alist)-1]] + [alist[len(alist)//2]])

And changed leftmark to start with index 0, not 1:

leftmark = first

Instead of:

leftmark = first+1

And then changed steps to be executed when finally done == True, as to correctly exchange rightmark and pivot value:

temp = pivotvalue
alist[alist.index(pivotvalue)] = alist[rightmark]
alist[rightmark] = temp

But when invoked with:

alist = [77,26,93,17,54,31,44,55,20]
quickSort(alist)
print(alist)

I'm getting the:

Traceback (most recent call last):
  File "/home/reloader/Templates/Exercises/quick_sort.py", line 52, in <module>
    quickSort(alist)
  File "/home/reloader/Templates/Exercises/quick_sort.py", line 9, in quickSort
    quickSortHelper(alist,0,len(alist)-1)
  File "/home/reloader/Templates/Exercises/quick_sort.py", line 17, in quickSortHelper
    quickSortHelper(alist,splitpoint+1,last)
  File "/home/reloader/Templates/Exercises/quick_sort.py", line 17, in quickSortHelper
    quickSortHelper(alist,splitpoint+1,last)
  File "/home/reloader/Templates/Exercises/quick_sort.py", line 17, in quickSortHelper
    quickSortHelper(alist,splitpoint+1,last)
  File "/home/reloader/Templates/Exercises/quick_sort.py", line 17, in quickSortHelper
    quickSortHelper(alist,splitpoint+1,last)
  File "/home/reloader/Templates/Exercises/quick_sort.py", line 17, in quickSortHelper
    quickSortHelper(alist,splitpoint+1,last)
  File "/home/reloader/Templates/Exercises/quick_sort.py", line 17, in quickSortHelper
  .......
  RuntimeError: maximum recursion depth exceeded in comparison

As I find this algorithm to be a bit complicated (and with a bit too much steps to execute), I really don't know what to change in order for this to work, and what I did broke with my modifications. I just set the pivot value to be value from the middle of the list. Should something else, which I cannot see at the moment, be modified as well?

Thanks.

Edit:

If I leave leftmark's initial value to be firstmark + 1 (that is, index 1 of the list), I'm not getting the infinite recursion error, but the list is not properly sorted as well:

[55, 26, 31, 44, 17, 77, 54, 20, 93]

Answer 1

You must pick the median from the subarray that's being partitioned:

Replace this:

pivotvalue = alist[first]

with

pivotindex = median(alist, first, last, (first + last) // 2)
alist[first], alist[pivotindex] = alist[pivotindex], alist[first]
pivotvalue = alist[first]

and the median finder doesn't have to be so convoluted.

def median(a, i, j, k):
  if a[i] < a[j]:
    return i if a[k] < a[i] else k if a[k] < a[j] else j
  else:
    return j if a[k] < a[j] else k if a[k] < a[i] else i