quickSelect HW in Python

Question

I've been given the following pseudo-code for the quickSelect algorithm. Im a little confused about a few things, when I call the quickSelect method what am I sending in for 'k'. Also, because I need to declare count = 0 at the beginning of the method, it will always get set back to 0 in the recursive call of quickSelect which is not what I need to happen Thanks for the help, i've included the Pseudo-code as well as my code below;

Function quickSelect(aList, k):
If aList is not empty:
    pivot <- Choose the element at position (len(alist)//2)
    smallerList <- All elements of aList smaller than pivot
    largerList <- All elements of aList larger than pivot
    count <- the number of occurences of pivot value in aList
    m <- the size of smallerList
    if k >= m and k < m + count then:
        return pivot
    if m > k:
        return quickSelect(smallerList,k)
    else:
        return quickSelect(largerlist, k-m-count)

This is what i've come up with:

def quickSelect(aList, k):
   pivot = aList[len(aList)//2]
   smallerList = aList[:pivot]
   largerList = aList[pivot:]
   m = len(smallerList)
   count = 0

   for i in aList:
      if i == pivot:
        count = count + 1

   if k >= m and k < m + count:
      return pivot
   if m > k:
      return quickSelect(smallerList, k)
   else:
      return quickSelect(largerList, k-m-count)

In what way is your code not working? (Could you provide some examples of its output alongside the desired output?) — David Robinson, Oct 17 '12 at 01:32

score 6 · Answer 1 · edited Oct 17 '12 at 15:37

First of all, you have smallerList and largerList taking the content from either side of the pivot based on their indices, NOT their value. Pivot is supposed to divide the numbers by the contents of the index, not the position of the index (say if index is 5, all entries less than the number 5 need to be assigned to smallerList, and all numbers larger need to be assigned to largerList that are larger than 5.

This can be done by a simple for loop:

if len(aList)!=0:
pivot=aList[(len(aList)//2)]
smallerList = []
for i in aList:
    if i<pivot:
        smallerList.append(i)
largerList=[]
for i in aList:
    if i>pivot:
        largerList.append(i)
m=len(smallerList)
count=len(aList)-len(smallerList)-len(largerList)

smallerList and largerList will /not/ include pivot, therefore count (the number of times pivot occurs) would be the length of the main list minus the combined lengths of the smaller and larger list.

Now if k (the kth smallest number) is greater than or equal to m, the length of the smaller list, AND k is less than the length of the smaller list + the count of pivot, you need to return pivot, because it is the kth smallest number that you were looking for.

if k >= m and k<m + count:
    return pivot

Or, if the length of the smaller list is greater than k, run quick select again using only the smallerList, and not the full list.

elif m > k:
    return quickSelect(smallerList,k)

Otherwise, run quick select again using the larger list, not the full list, and look for k - length of smaller list - count of pivot

else:
    return quickSelect(largerList, k - m - count)

This function will run itself over and over (much faster than linear sort) and will give you the return the pivot once satisfied. Pivot in this case would be the median.

Hope this helps!

quickSelect HW in Python

1 Answers1

Linked