基本ソートアルゴリズム3つの実装

挿入ソート

トランプを並び替える時などに左から小さい順に並び替えたりする場合によく使われている方法に似ています．
一枚のカードを取り出し，それをすでにソート済みのカードの適切な位置に挿入するというのが挿入ソートの基本的な考え方です．
基本的な動作としては

先頭のものをソート済みとする
残っている未ソート部分がなくなるまで以下を繰り返す
1. 未ソート部分の先頭の要素xを一つ取り出す
2. ソート済み部分の後ろの要素とxの値の大小を比較し，xより要素が大きければリストの順番を入れ替える
3. 適切な位置に要素xを入れる

このソートアルゴリズムの計算量は最悪の場合O(n²)となります．
また，入力データがソートした時と真逆の状態の時に計算量は最大となり，その並び順が計算量に大きく響きます．
実装に関しては次のようになります．

def insertsort(num_list):
    sort_list = list(num_list)
    for i in range(len(num_list)):
        target = sort_list[i]
        j = i -1
        while j >= 0 and sort_list[j] > target:
            sort_list[j+1], sort_list[j] = sort_list[j], target
            j -=1
    return sort_list

num_list = list(range(1,20))
shuffle(num_list)
sorted_list =  insertsort(num_list)
print(num_list)
print(sorted_list)

途中の状態を確認したい場合はwhile文の後にsort_listをprintしてみてください．

バブルソート

バブルソートも挿入ソートと同様にソートしていく過程で未ソート部分とソート済み部分に分けられます．
基本的な動作としては

順番が逆担っている隣接容姿がなくなるまで次の処理を繰り返す
1. 配列の末尾から隣接する要素を順番に比べていき，正しい大小関係ならば逆に交換する．
  (ループを抜けると未ソート部分の中で一番小さな要素がソート済みに変わっていくイメージ)

バブルソートも挿入ソート同様オーダーはO(n²)となります．
実装に関しては次のようになります．

def bubblesort(num_list):
    i = 0
    sort_list = list(num_list)
    for i in range(len(num_list)-1):
        for j in range(len(num_list)-1, i, -1):
            if sort_list[j] < sort_list[j-1]:
                sort_list[j], sort_list[j-1] = sort_list[j-1], sort_list[j]            
    return sort_list

num_list = list(range(1,20))
shuffle(num_list)
sorted_list =  bubblesort(num_list)
print(num_list)
print(sorted_list)

選択ソート

選択ソートにおいても既出のソートアルゴリズム同様ソートしていく過程で未ソート部分とソート済み部分に分けられます．
動作はプログラムとして直感的に理解しやすい形になっていて，未ソート部分の中から一番小さな要素を見つけ出し未ソート部分の先頭の要素と入れ替えていくということを繰り返すことになります．
基本的な動作としては

次の処理をN-1回繰り返す
1. 未ソート部分から最小の要素xの位置を見つけ出す
2. 未ソート部分の先頭の要素の位置と最小の要素xの位置を入れ替える
3. 新しいxの要素の位置をソート済みとする

これまでのソートアルゴリズムと異なり，選択ソートは離れた要素同士の位置を入れ替えていくことを行うため，ソート後の結果が不安定になることがあります.
ソートが不安定な状態とは今回考えているのは一次元の配列なので問題はありませんが，テストの結果のように多次元の配列を考えた時に理想とするソート結果と実際のソート結果で差異が生まれてしまうことを言います．
ちなみに，選択ソートのオーダーに関してもO(n²)となります．
実装に関しては次のようになります．

def selectionsort(num_list):
    sort_list = list(num_list)
    for i in range(len(num_list)):
        minposi = i
        for j in range(i,len(num_list)):
            if sort_list[minposi] > sort_list[j]:
                minposi = j
        sort_list[i], sort_list[minposi] = sort_list[minposi], sort_list[i]
    return sort_list
                  
num_list = list(range(1,20))
shuffle(num_list)
sorted_list =  selectionsort(num_list)
print(num_list)
print(sorted_list)