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