Kursy Online

Lekcja – quick select

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))

Rozwiązanie

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))