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