【Python】選択ソート、挿入ソートの実装

選択ソート

配列から最小・最大値を探し，先頭要素と交換することを繰り返すことで整列を行う方法。 未整列部分の値を全て確認するので、等差数列的に計算数が加算され、時間計算量は0(n²)必要になる。

def selection_sort(arr):
    # 結果を出力するリスト
    result = arr

    for i in range(len(result)):
        # 未整列部分の中から最小値を探す
        for j in range(i + 1, len(result)):
            if result[i] > result[j]:
                tmp = result[i]
                result[i] = result[j]
                result[j] = tmp

    return result

挿入ソート

配列を「整列済み」と「未整列」の2種類に分け、未整列配列から整列済み配列の適切な場所に要素を挿入する方法。 ソート前に配列が整列されている部分が多いと計算量はO(n)になる。全く整列されていない場合はO(n²)になる。

def insert_sort(arr):
    if len(arr) < 1:return arr
    # 結果返却用
    result = arr

    # ソート前は先頭のみを整列済みとして扱う
    for i in range(1,len(result)):
        current_value = result[i]
        for j in range(i-1,-1,-1):
            print(i, j)
            if current_value < result[j]:
                result[j + 1] = result[j]
                result[j] = current_value
            else:
                break

    return result