Pythonでソートをする。ついでにアルゴリズムを考えてみる。

メソッド、組み込み関数でのソート

まずは以下のリストについてソートすることを考えてみる。

data = [5, 3, 2, 4, 1, 6]

Pythonでリスト型を昇順または降順にソートするにはsort()とsorted()の二種類が存在する。
- リスト型のメソッドであるsort():そのリスト自体をソート
- 組み込み関数sorted():ソートされたリストを新しく戻り値として返す

リスト型のメソッドsort()

もとのリスト自体を書き換える。

data.sort()
print(data)
# [1, 2, 3, 4, 5, 6]

デフォルトでは昇順のソートになっている。降順にソートするためには引数reverseをTrueにする。

data.sort(reverse = True)
print(data)
# [6, 5, 4, 3, 2, 1]

注意が必要なことはsort()では戻り値はNoneである。

x = data.sort()
print(x)
# None

組み込み関数sorted()

　引数にソートしたいリストを指定すると、ソートされたリストを新たに生成し戻り値として返す。

new_data1 = sorted(data)
print(new_data1)
# [1, 2, 3, 4, 5, 6]

sorted()もsort()と同様にデフォルトでは昇順になっている。降順にソートするためには引数reverseをTrueにする。

new_data2 = sorted(data, reverse = True)
print(new_data2)
# [6, 5, 4, 3, 2, 1]

ソートのアルゴリズム

　3つのソートアルゴリズムについてまとめてみる。
　まとめて見るだけなので、速度、メモリ使用量などは気にしない。
　デフォルトでは昇順、コメントに変更することで降順になる。

考えるソートアルゴリズム

• バブルソート
• 挿入ソート
• マージソート

バブルソート

　隣り合う2つの値を比較し、条件に応じて並び替えることを繰り返す。

bubble_sort

for i in range(len(data)):
    for j in range(len(data) - 1):
        if data[j] > data[j+1]: # data[j] < data[j+1]
            data[j], data[j+1] = data[j+1], data[j]
print(data)
# [1, 2, 3, 4, 5, 6]

挿入ソート

　整列してあるデータに対して、対象を適切な位置に入れる(挿入する)。
　今回は2分探索は用いない。

insert_sort

for i in range(1, len(data)):
    j = i - 1
    target = data[i]
    while data[j] > target and j >= 0: # data[j] < target
        data[j + 1] = data[j]
        j -= 1
    data[j + 1] = target
print(data)
# [1, 2, 3, 4, 5, 6]

マージソート

　リストを小さな単位に分け、2つのリストの先頭を比較し、一つにする。

merge_sort

import math

def merge(x,y):
    m = []
    i = 0
    while i < len(x):
        i += 1
        j = 1
        while j < len(x):
            if x[j-1] > x[j]: # x[j-1] < x[j]
                x[j-1] , x[j] = x[j] , x[j-1]
            j += 1
    i = 0
    while i < len(y):
        i += 1
        j = 1
        while j < len(x):
            if x[j-1] > x[j]: # x[j-1] < x[j]
                x[j-1] , x[j] = x[j] , x[j-1]
            j += 1

    while x != [] and y != []:
        if x[0] < y[0]: # x[0] > y[0]
            m.append(x.pop(0))
        else:
            m.append(y.pop(0))
    if x == []:
        m += y
    else:
        m += x
    return m

data=[7,4,2,8,1,5,3,9,6]
n = 0
i = math.log2(len(data))
while n < i+1:
    tmp = []
    k=0
    while k < len(data):
        tmp = tmp
        m=merge(data[k:k+2**n],data[k+2**n:k+2**(n+1)])
        tmp += m
        k += 2**(n+1)
    data.clear()
    data += tmp
    n += n+1

print(data)
# [1, 2, 3, 4, 5, 6]

終わりに

　Qiita初投稿なので至らない点多くあると思いますので、ご指摘をお願いします。
　バブルソートと挿入ソートに関しては比較的すぐにできたが、マージソートについては結構時間がかかった。