I solved that using Quickselect algorithm. Now i want to implement this using Quicksort and Selection sort algorithm.

CodePudding user response：

#implementation with a randomly chosen pivot

import random

def select_nth(n, items):
    pivot = random.choice(items)

    lesser = [item for item in items if item < pivot]
    if len(lesser) > n:
        return select_nth(n, lesser)
    n -= len(lesser)

    numequal = items.count(pivot)
    if numequal > n:
        return pivot
    n -= numequal

    greater = [item for item in items if item > pivot]
    return select_nth(n, greater)

#now trivially turns this into a methods to finds medians

def median(items):
    if len(items) % 2:
        return select_nth(len(items)//2, items)

    else:
        left  = select_nth((len(items)-1) // 2, items)
        right = select_nth((len(items) 1) // 2, items)

        return (left   right) / 2

CodePudding user response：

So, all you want is two implementations of sorting and applying median?

def selection_sort(arr):
    for i in range(len(arr)):
        smallest_ind = i
        for j in range(i   1, len(arr)):
            if arr[j] < arr[smallest_ind]:
                smallest_ind = j
        arr[i], arr[smallest_ind] = arr[smallest_ind], arr[i]

def quick_sort(arr):
    if len(arr) <= 1:
       return arr
    pivot = arr[0]
    i = 0
    for j in range(len(arr)-1):
        if arr[j 1] < pivot:
           arr[j 1],arr[i 1] = arr[i 1],arr[j 1]
           i  = 1
    arr[0],arr[i] = arr[i],arr[0]
    left = quick_sort(arr[:i])
    right = quick_sort(arr[i 1:])
    left.append(arr[i])
    return left   right

def median(arr):
    n = len(arr)
    return (arr[n//2]   arr[(n-1)//2]) / 2

Now test the functions:

nums = [5, 8, 4, 1, 2, 5]
quick_sorted = quick_sort(nums)
selection_sorted = nums.copy()
selection_sort(selection_sorted)

median_quicksort = median(quick_sorted)
median_selection_sort = median(selection_sorted)

Both of them give the expected result 4.5.