def divide(list, start, end): i = start border_value = list[end] for j in range(start, end): if list[j] <= border_value: list[i], list[j] = list[j], list[i] i += 1 list[i], list[end] = list[end], list[i] return i def quick_select(list, start, end, k_th): print(f'DEBUG: {list}') if k_th >= len(list): return None if start <= end: border_index = divide(list, start, end) if border_index == k_th: print(f'DEBUG: {list} - found: {list[border_index]}') return list[border_index] elif border_index > k_th: return quick_select(list, start, border_index -1, k_th) else: return quick_select(list, border_index + 1, end, k_th) list = [77, 32, 100, 40, 92, 17, 74, 58, 63] print(quick_select(list, 0, len(list)-1, 7))
def divide(list, start, end): i = start border_value = list[end] for j in range(start, end): if list[j] <= border_value: list[i], list[j] = list[j], list[i] i += 1 list[i], list[end] = list[end], list[i] return i def quick_select(list, start, end, k_th): print(f'DEBUG: {list}') if k_th >= len(list): return None if start <= end: border_index = divide(list, start, end) if border_index == k_th: print(f'DEBUG: {list} - found: {list[border_index]}') return list[border_index] elif border_index > k_th: return quick_select(list, start, border_index -1, k_th) else: return quick_select(list, border_index + 1, end, k_th) def median(list): if len(list) %2 == 1: return quick_select(list, 0, len(list)-1, len(list)//2 ) else: m1 = quick_select(list, 0, len(list)-1, len(list)//2-1 ) m2 = quick_select(list, 0, len(list)-1, len(list)//2 ) return (m1 + m2) / 2 list_even = [1000,2,30,6,4,70,800,90,1,50] print(median(list_even)) list_odd = [1000,2,30,6,4,70,800,90,1] print(median(list_odd))