Algorithm_Sort_Insrtion sort

tags: Algorithms Sort python

def insertion_sort(input_array):
    """insertion sort
    input_array: list
                 list內的元素需為數值
                 
    return 
        由小大到排序後的list
    """
    if len(input_array) <= 1:
        return
    
    # 從第2個element開始處理
    for idx, idx_value in enumerate(input_array[1: ]):        
        # 內圈迴圈使用        
        inner_idx = idx        
        while inner_idx >= 0 and idx_value < input_array[inner_idx]:            
            # 這邊的idx剛好就是j-1的索引
            # 判斷兩值的大小，如果索引值(右)比前一個元素(左)小
            # 那就將前一個元素複製到索引處                                       
            input_array[inner_idx + 1] = input_array[inner_idx]                
            inner_idx -= 1            
        
        # 當兩個索引不同代表異動排序過
        if inner_idx != idx:                
            # 將原始索引值寫入最終停止的索引處            
            input_array[inner_idx + 1] = idx_value
    
    return input_array

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

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

Insertion sort	20000	40000	60000	80000	100000
l1	7ms	16ms	25ms	22ms	37ms
l2	1min 31s	5min 47s	13min 27s	24min 18s	37min 34s
l3	43.4s	2min 59s	6min 52s	12min 27s	20min 6s
l4	43.1s	3min 2s	6min 50s	13min 1s	19min 52s
l5	42.9s	2min 57s	6min 51s	12min 42s	19min 47s