新・アルゴリズムとデータ構造入門 Python編5:マージソートの実装

INF = 1000000001
count = 0


def print_array(a):
    print(*a)


def merge(a, left, mid, right):
    global count

    # それぞれの部分を新しい配列(リスト) l, r にコピー
    # 番兵を追加
    # lindex, rindex を 0 に初期化

    for i in range(left, right):
        # l と r の先頭要素のうち l の先頭要素が小さいなら
        if """""":
            # l の先頭要素を元の配列(リスト)に格納
            # l の先頭を 1 つ進める

            pass
        else:
            # r の先頭要素を元の配列(リスト)に格納
            # r の先頭を 1 つ進める
            count += 1


def merge_sort(a, left, right):
    # もし、left が right-1 以上なら終了

    # mid に (left+right)/2 を代入
    # merge_sort(a, left, mid) と merge_sort(a, mid, right) を呼び出す
    # merge(a, left, mid, right) を呼び出す

    pass


n = int(input())
a = [int(x) for x in input().split()]

merge_sort(a, 0, n)

print_array(a)
print(count)

INF = 1000000001
count = 0


def print_array(a):
    print(*a)


def merge(a, left, mid, right):
    global count

    # それぞれの部分を新しい配列(リスト) l, r にコピー
    # 番兵を追加
    # lindex, rindex を 0 に初期化

    for i in range(left, right):
        # l と r の先頭要素のうち l の先頭要素が小さいなら
        if """""":
            # l の先頭要素を元の配列(リスト)に格納
            # l の先頭を 1 つ進める

            pass
        else:
            # r の先頭要素を元の配列(リスト)に格納
            # r の先頭を 1 つ進める
            count += 1


def merge_sort(a, left, right):
    # もし、left が right-1 以上なら終了

    # mid に (left+right)/2 を代入
    # merge_sort(a, left, mid) と merge_sort(a, mid, right) を呼び出す
    # merge(a, left, mid, right) を呼び出す

    pass


n = int(input())
a = [int(x) for x in input().split()]

merge_sort(a, 0, n)

print_array(a)
print(count)

INF = 1000000001
count = 0


def print_array(a):
    print(*a)


def merge(a, left, mid, right):
    global count

    l = a[left:mid]
    r = a[mid:right]

    l.append(INF)
    r.append(INF)

    lindex, rindex = 0, 0
    for i in range(left, right):
        if l[lindex] < r[rindex]:
            a[i] = l[lindex]
            lindex += 1
        else:
            a[i] = r[rindex]
            rindex += 1
            count += 1


def merge_sort(a, left, right):
    if left >= right - 1:
        return
    
    mid = (left + right) // 2

    merge_sort(a, left, mid-1)
    merge_sort(a, mid, right-1)
    merge(a, left, mid, right)


n = int(input())
a = [int(x) for x in input().split()]

merge_sort(a, 0, n)

print_array(a)
print(count)

INF = 1000000001
count = 0


def print_array(a):
    print(*a)


def merge(a, left, mid, right):
    global count

    l = a[left:mid]
    r = a[mid:right]

    l.append(INF)
    r.append(INF)

    lindex, rindex = 0, 0
    for i in range(left, right):
        if l[lindex] < r[rindex]:
            a[i] = l[lindex]
            lindex += 1
        else:
            a[i] = r[rindex]
            rindex += 1
            count += 1


def merge_sort(a, left, right):
    if left >= right - 1:
        return
    
    mid = (left + right) // 2

    merge_sort(a, left, mid-1)
    merge_sort(a, mid, right-1)
    merge(a, left, mid, right)


n = int(input())
a = [int(x) for x in input().split()]

merge_sort(a, 0, n)

print_array(a)
print(count)

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

演習1

問題ログインすると模範解答や入力を見ることができます

演習課題「正しくマージソートを実装する」

整数nと要素数nの数列Aが与えられるので、この数列をマージソートでソートしてください。
右側のコードエリアに用意されているコードには誤りがあります。訂正し、問題を解くコードを完成させてください。

入力される値

4
8 1 3 2

標準入力からの値取得方法はこちらをご確認ください

期待する出力値

1 2 3 8
4

Tips

動画へ戻る

次のチャプターへ前のチャプターへ

※有料会員になるとこの動画をご利用いただけます

詳しい説明を読む

＃05:マージソートの実装

実際にマージソートを実装してみます。関数の再帰を使うので、丁寧に実装しましょう。

「マージソート」へのリンク

「マージソート」の問題を見る

入力される値

n
A_1 A_2 ... A_n

・入力はすべて整数
・ 1行目に、数列の要素数nが与えられます。
・ 2行目に、数列の要素A_1,A_2,...,A_nが半角スペース区切りで与えられます。

実行するコード

INF = 1000000001
count = 0


def print_array(a):
    print(*a)


def merge(a, left, mid, right):
    global count

    # それぞれの部分を新しい配列(リスト) l, r にコピー
    l = a[left:mid]
    r = a[mid:right]

    # 番兵を追加
    l.append(INF)
    r.append(INF)

    # lindex, rindex を 0 に初期化
    lindex, rindex = 0, 0
    for i in range(left, right):
        # l と r の先頭要素のうち l の先頭要素が小さいなら
        if l[lindex] < r[rindex]:
            # l の先頭要素を元の配列(リスト)に格納
            a[i] = l[lindex]
            # l の先頭を 1 つ進める
            lindex += 1
        else:
            # r の先頭要素を元の配列(リスト)に格納
            a[i] = r[rindex]
            # r の先頭を 1 つ進める
            rindex += 1
            count += 1


def merge_sort(a, left, right):
    # もし、left が right-1 以上なら終了
    if left >= right - 1:
        return

    # mid に (left+right)/2 を代入
    mid = (left + right) // 2

    # merge_sort(a, left, mid) と merge_sort(a, mid, right) を呼び出す
    merge_sort(a, left, mid)
    merge_sort(a, mid, right)

    # merge(a, left, mid, right) を呼び出す
    merge(a, left, mid, right)


n = int(input())
a = [int(x) for x in input().split()]

merge_sort(a, 0, n)

print_array(a)
print(count)

入力例-その1

4
8 1 3 2

入力例-その2

10
7 6 10 2 5 4 8 3 9 1

プログラミング学習 > Python3 > 新・アルゴリズムとデータ構造入門 Python編 > 新・アルゴリズムとデータ構造入門 Python編5: 効率的なソートアルゴリズム > マージソートの実装

1
2
INF = 1000000001
count = 0
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

コードの実行

有料会員になるとエンジニアに質問ができます

出力タイプ：

4
8 1 3 2