k_media.py

import datetime as dt

def wikipedia_partition(list_set, left_end_index, right_end_index, pivot_index):
  pivot_val = list_set[pivot_index]
  list_set[pivot_index],  list_set[right_end_index] = list_set[right_end_index], list_set[pivot_index]
  temp_index = left_end_index
  for i in range(left_end_index, right_end_index-1):
    if pivot_val > list_set[i]:
      list_set[temp_index], list_set[i] = list_set[i], list_set[temp_index]
      temp_index += 1
  list_set[right_end_index], list_set[temp_index] = list_set[temp_index], list_set[right_end_index]
  return (list_set, temp_index)

def wikipedia_select(list_set, left_end_index, right_end_index, k_mean):
  pass


'''
  partition into chunks of size 5 + maximum 1 of size len(list_set) mod 5
'''
def partition(list_set):
  result = []
  if(len(list_set) > 1):
    i = 0
    temp_list_list_set = []
    while(i < len(list_set)):
      j = i
      temp_list_set = []
      while(j < (i+5) and j < len(list_set)):
        temp_list_set.append(list_set[j])
        #print temp_list_set
        j += 1
      temp_list_list_set.append(temp_list_set)
      i += 5
    result = temp_list_list_set
    return result
  else:
    return list_set

def select(B, k):
  '''
  if(k > len(B) - 1):
    return "Geht nicht"
  else:
  '''    
  if(len(B) <= 5):
    B.sort()
    #print "B: % s" % B[k-1]
    return B[k-1]
  else:
    p_list_set = partition(B)
    #print p_list_set
    median_list_set = []
    for lst in p_list_set:
      lst.sort()
      length = len(lst)
      index = length/2
      #print "lst(sorted): %s index: %s value: %s" % (lst, index, lst[index])
      median_list_set.append(lst[index])
    #print "median_set: %s " % median_list_set
    subset_one = []
    subset_two = []
    x = select(median_list_set, ((len(median_list_set)+1)/2))
    for h in B:
      if(h <= x):
        subset_one.append(h)
      else:
        subset_two.append(h)
    if(k <= len(subset_one)):
      return select(subset_one, k)
    else:
      return select(subset_two, (k-len(subset_one)))


"""
  Ab 10^6 Elementen beginnt der Rechner längere Zeit zu rechnen (2+sekunden)
"""
test_len = 1000000
B = [x for x in range(test_len)]
del(B[0])
B.sort()
#print B
k = 10
"""print partition(B)"""
print "________________________________________________________"
#print select(B, k)
start = dt.datetime.now()
print "ret: %s" % select(B, k)
end = dt.datetime.now()
print "end %s" % (end-start)