Algorithm_Sort_Quick sort

tags: Algorithms Sort python

import random
def quick_sort(input_array, is_random=False):
    """Quick Sort
    parameters:
        input_array: 輸入的未排序陣列
        is_random: 是否隨機取pivot point
             預設情況下是取陣列最後一個元素做pivot point      
    
    在worst case的情況下(資料已排序過)，如果沒有亂數取pivot無法成功執行
    """
    # print(f'input array: {input_array}')
    array_size = len(input_array)
    if array_size < 2:
        # 不處理
        return input_array
    
    # 取得pivot
    if is_random:
        pivot_point = random.randint(0, array_size - 1)
    else:
        pivot_point = array_size - 1
    
    pivot = input_array.pop(pivot_point)
    # print(f'pivot: {pivot}, pivot_point: {pivot_point}')
        
    # 寫入比pivot大以及小的資料
    greater_pivot = [element for element in input_array if element > pivot]
    # print(f'greater_pivot: {greater_pivot}')
    lesser_pivot = [element for element in input_array if element < pivot]
    # print(f'lesser_pivot: {lesser_pivot}')
    # print(f'total: {lesser_pivot} + {[pivot]} + {greater_pivot}')
    # 利用python list相加的特性做遞迴處理
    return quick_sort(lesser_pivot, is_random) + [pivot] + quick_sort(greater_pivot, is_random)

下面給出五個資料集在不同資料量下的結果，其中

• l1: 已經排序好的，由小到大
• l2: 已經排序好的，但是逆排序，由大到小
• l3: 亂數生成
• l4: 亂數生成
• l5: 亂數生成

Quick Sort(no random)	20000	40000	60000	80000	100000
l1	–	–	–	–	–
l2	–	–	–	–	–
l3	89 ms	172 ms	238 ms	438 ms	434 ms
l4	130 ms	153 ms	248 ms	330 ms	416 ms
l5	81 ms	154 ms	256 ms	335 ms	439 ms

Quick Sort(random)	20000	40000	60000	80000	100000
l1	154 ms	219 ms	315 ms	468 ms	583 ms
l2	107 ms	225 ms	333 ms	475 ms	539 ms
l3	103 ms	241 ms	370 ms	526 ms	592 ms
l4	121 ms	246 ms	349 ms	511 ms	656 ms
l5	111 ms	226 ms	403 ms	503 ms	627 ms