Python 3.2.5 (default, May 15 2013, 23:07:10) [MSC v.1500 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
>>> lst = [10, 400, 5, -10, 55, 1, 80]
#denote by n the size of lst.
# sort_select function creates a new sorted list in O(nlogn) time complexity
# and then returns in O(1) time the item in index k-1
# Overall complexity: O(nlogn)
#returns the smallest element in lst
>>> sort_select(lst, 1)
-10
#returns the 3-rd smallest element in lst
>>> sort_select(lst, 3)
5
#select function is a recursive function that solves the problem.
# It implements a randomized algorithm for select
# Best case is O(n) - happens when we draw the k-smallest element as the first pivot by chance
# Worst case is O(n**2) - can happen when we want the smallest element (1-select) but we keep drawing the largest element
# A fact (without any proof): The average case is O(n)
# As in quicksort, we draw a random element as pivot and create a list of
# all the elements that are smaller than pivot and a list of all elements that are larger than pivot.
#if k is smaller or equal to the number of elements smaller than pivot(that is, the pivot is larger than the k-smallest element)
# recursively search for the k-smallest element in the list of smaller elements.
#Else, if k is larger than the number of elements that are smaller or equal to pivot larger than pivot
# recursively search in the list of elements larger than pivot.
# Note that for the recursive call we need to update k in this case: we know that all elements
#smaller than pivot or equal to pivot (which is exactly n minus the number of elements greater than pivot) is less than k.
# the new k for the recursive call is the current value of k minus the number of elements smaller or equal to pivot.
#Else, the pivot is the k-smallest
Example:
>>> select(lst, 3)
L = [10, 400, 5, -10, 55, 1, 80] ; k = 3
pivot = 400
(
the list small is [10, 5, -10, 55, 1, 80]
the list large is []
3 <= len(small), therefore the recursive call is:
select ([10, 5, -10, 55, 1, 80], 3)
)
L = [10, 5, -10, 55, 1, 80] ; k = 3
pivot = 10
(
the list small is [5, -10, 1]
the list large is [55, 80]
3 <= len(small), therefore the recursive call is:
select ([5, -10, 1], 3)
)
L = [5, -10, 1] ; k = 3
pivot = 1
(
the list small is [-10]
the list large is [5]
3 > 2 therefore the recursive call is:
select ([5], 1)
)
L = [5] ; k = 1
pivot = 5
5
#Another run:
>>> select(lst, 3)
L = [10, 400, 5, -10, 55, 1, 80] ; k = 3
pivot = 80
(
the list small is [10, 5, -10, 55, 1]
the list large is [400]
3 <= len(small), therefore the recursive call is:
select ([10, 5, -10, 55, 1], 3)
)
L = [10, 5, -10, 55, 1] ; k = 3
pivot = -10
(
the list small is []
the list large is [10, 5, 55, 1]
3 > 5-4, therefore the recursive call is:
select ([10, 5, 55, 1], 3-(5-4))
)
L = [10, 5, 55, 1] ; k = 2
pivot = 1
(
the list small is [1]
the list large is [10, 5, 55]
2 > 4-3, therefore the recursive call is:
select ([10, 5, 55], 2-(4-3))
)
L = [10, 5, 55] ; k = 1
pivot = 55
(
the list small is [10,5]
the list large is []
1 <= 2, therefore the recursive call is:
select ([10, 55], 1)
)
L = [10, 5] ; k = 1
pivot = 10
(
the list small is [5]
the list large is []
1 <= 1, therefore the recursive call is:
select ([5], 1)
)
L = [5] ; k = 1
pivot = 5
5