Calculating median of a sorted array using Quicksort, Quickselect method and Selection Sort Python

Issue

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

Solution

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.

Answered By – AboAmmar

This Answer collected from stackoverflow, is licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0

Leave a Reply

(*) Required, Your email will not be published