merge sort, bubble sort, selection sort, quick sortをpythonで実装した。

#merge sort
備忘録に。

def merge_sort(array):
    if len(array) == 1:
        return array
    left_array = merge_sort(array[:len(array) // 2])
    right_array = merge_sort(array[len(array) // 2:])
    sorted_array = []
    while left_array and right_array:
        print(left_array, right_array)
        if left_array[0] < right_array[0]:
            sorted_array.append(left_array.pop(0))
        else:
            sorted_array.append(right_array.pop(0))
    sorted_array.extend(right_array)
    sorted_array.extend(left_array)
    return sorted_array

再帰関数を使うとシンプルにかける。 array.append(right.pop(0))を使うとrightの右端の要素をrightから取り除くと同時に、arrayに持ってこれる。

#bubble sort

input_list = [2, 3, 10, 9, 4, 6, 7, 5, 8, 1]

def bubble_sort(input_list):
    total_number = len(input_list)
    flag = True
    finished = 0

    while flag:
        flag = False
        for i in range(total_number-1-finished):
            if input_list[i] > input_list[i+1]:
                input_list[i], input_list[i+1] = input_list[i+1], input_list[i]
                flag = True
        finished += 1

print(input_list)

結果はこうなる。

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

例えば、この例では、

1. 2と3を比較→右<左なのでそのまま
2. 3と10を比較→右<左なのでそのまま
3. 10と9を比較→左<右なので入れ替え→10と4を比較→左<右なので入れ替え→10と6を比較→
   左<右なので入れ替え....と行って、10は右端まで持っていく、という流れだ。
   これを繰り返すと、sortができている。

コメントを受けて、変更しました。flagをwhileの最初でTrueにしておいて、一個でもfor文の中のifで引っかかったら(つまりsortが完全でなかったら)flagをTrueにするやり方を初めて知りました！

selection sort

for i in range(len(array)-1):
    min=i
    for j in range(i+1, len(array)):
        if array[j] < array[min]: 
            min = j
    array[i], array[min] = array[min], array[i]

quick sort

def quick_sort(array):
    print(array)
    if len(array) <= 1:
        return array
    left = []
    right = []
    criterion_cnt = 0
    criterion = array[0]
    for i in range(len(array)):
        if array[i] < criterion:
            left.append(array[i])
        elif array[i] > criterion:
            right.append(array[i])
        elif array[i] == criterion:
            criterion_cnt += 1
    return quick_sort(left) + [criterion] * criterion_cnt + quick_sort(right)

criterionはleftかrightのどちらかに含ませればいいのでは？と思ったが、それだとうまくいかない。criterionが配列の最小値を取得し続け、無限ループになってしまうことがありうる。