5. Quick Sort

In [1]:

import numpy as np
from random import randint
import statistics

import numpy as np from random import randint import statistics

In [2]:

unsorted_list =  np.arange(0, 10)
np.random.shuffle(unsorted_list)
print(unsorted_list)

unsorted_list = np.arange(0, 10) np.random.shuffle(unsorted_list) print(unsorted_list)

[0 4 6 8 7 1 5 3 9 2]

In [3]:

def quick_sort(arr):
    
    if len(arr) <= 1:
        return arr
    
    # step 1: identify pivot
    pivot = statistics.median([arr[0], arr[len(arr)//2], arr[-1]])
    
    # step 2: make left sub-array, pivot array and right sub-array
    left_subarray = [i for i in arr if i < pivot]
    median_array = [i for i in arr if i == pivot]
    right_subarray = [i for i in arr if i > pivot]
    
    # step 3: recurse quick sort on left and right sub-array
    # append all the arrays in sequence
    return quick_sort(left_subarray) + median_array + quick_sort(right_subarray)

def quick_sort(arr): if len(arr) <= 1: return arr # step 1: identify pivot pivot = statistics.median([arr[0], arr[len(arr)//2], arr[-1]]) # step 2: make left sub-array, pivot array and right sub-array left_subarray = [i for i in arr if i < pivot] median_array = [i for i in arr if i == pivot] right_subarray = [i for i in arr if i > pivot] # step 3: recurse quick sort on left and right sub-array # append all the arrays in sequence return quick_sort(left_subarray) + median_array + quick_sort(right_subarray)

In [4]:

quick_sort(unsorted_list)

quick_sort(unsorted_list)

Out[4]:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

In [ ]: