トップページ -> AOJの解答例 -> ALDS1_2の解答例

ALDS1_2の解答例(Python)

並び替えに関する問題です．アルゴリズムについて詳しく知りたい方は参考文献などをご覧ください．

1. ALDS1_2_A: Bubble Sort

バブルソートに関する問題です．問題文に載っている疑似コードの通りに書きました．

バブルソートについて

右側の要素から隣接する要素との大きさを比べることで「どこまで浮かび上がってこれるか」を考えます．入力例の5,3,2,4,1についてどのような入れ替えが起こるかです． 1回目のループ．5,3,2,4,1 → 5,3,2,1,4 → 5,3,1,2,4 → 5,1,3,2,4 → 1,5,3,2,4 2回目のループ．1,5,3,2,4 → 1,5,2,3,4 → 1,2,5,3,4 3回目のループ．1,2,5,3,4 → 1,2,3,5,4 4回目のループ．1,2,3,5,4 → 1,2,3,4,5


# ALDS1_2_A
def bubble_sort(A,N):
    flag = 1
    cnt = 0 # 要素の交換が行われた回数
    while flag:
        flag = 0
        for j in range(N-1):
            j = N-1-j # 逆順なので j = N-1-j 
            if A[j] < A[j-1]:
                # A[j]とA[j-1]の交換
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp
                flag = 1
                cnt += 1
                
    return cnt
                
N = int(input())
A = list(map(int,input().split(" ")))

swap_cnt = bubble_sort(A,N)
print(*A)
print(swap_cnt)

2. ALDS1_1_B: Selection Sort

選択ソートに関する問題です．問題文に載っている疑似コードの通りに書きました．

選択ソート

リストLを昇順に並べることを考えるときに
Lの0からN-1までの最小値を0番目にしたものを L0
L0の1からN-1までの最小値を1番目にしたものを L1
L1の2からN-1までの最小値を2番目にしたものを L2
のように各ステップで最小値を見つけて調べた区間の先頭に持ってきます．
入力例5,6,4,2,1,3は以下のようになります．
i=0の場合: [5,6,4,2,1,3]に関して0からN-1までだとminj=4なので0番目と4番目を入れ替えて[1,6,4,2,5,3]
i=1の場合: [1,6,4,2,5,3]に関して1からN-1までだとminj=3なので1番目と3番目を入れ替えて[1,2,4,6,5,3]
i=2の場合: [1,2,4,6,5,3]に関して2からN-1までだとminj=5なので2番目と5番目を入れ替えて[1,2,3,6,5,4]
i=3の場合: [1,2,3,6,5,4]に関して3からN-1までだとminj=5なので3番目と5番目を入れ替えて[1,2,3,4,5,6]
i=4の場合: [1,2,3,4,5,6]に関して4からN-1までだとminj=4なので4番目と4番目を入れ替えて(この場合は実際には入れ替えが起こりません) [1,2,3,4,5,6]


# ALDS1_2_B
def selection_sort(A,N):
    cnt = 0 
    for i in range(N):
        minj = i
        for j in range(i,N):
            if A[j] < A[minj]:
                minj = j
        
        if i != minj:
            tmp = A[i]
            A[i] = A[minj]
            A[minj] = tmp
            cnt += 1 # 交換が行われた回数をカウントする
        
    return cnt

N = int(input())
A = list(map(int,input().split(" ")))

swap_cnt = selection_sort(A,N)
print(*A)
print(swap_cnt)

3. ALDS1_2_C: Stable Sort

トランプのカードの整列をバブルソート，選択ソートを使って行う問題です．同じ数字を持つカードが複数ある場合それらが入力に出現する順序で出力されることを、「安定な出力」と呼ぶことにしたときに，出力が安定か否かを判定します．バブルソートは安定なソートであるので，選択ソートが安定かどうかをバブルソートの結果と比較することで判定しています．


# ALDS1_2_C
def bubble_sort(A,N):
    flag = 1
    cnt = 0 # 要素の交換が行われた回数
    while flag:
        flag = 0
        for j in range(N-1):
            j = N-1-j # 逆順なので j = N-1-j 
            # トランプ仕様に変更した
            value0 = int(A[j][1:])
            value1 = int(A[j-1][1:])
            if value0 < value1:
                # A[j]とA[j-1]の交換
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp
                flag = 1
                cnt += 1
                
    return cnt

def selection_sort(A,N):
    cnt = 0 
    for i in range(N):
        minj = i
        for j in range(i,N):
            # トランプ仕様に変更した
            value0 = int(A[j][1:])
            value1 = int(A[minj][1:])
            if value0 < value1:
                minj = j
        
        if i != minj:
            tmp = A[i]
            A[i] = A[minj]
            A[minj] = tmp
            cnt += 1 # 交換が行われた回数をカウントする
        
    return cnt

N = int(input())
A = input().split(" ")

bubble_A = A[:]
bubble_sort(bubble_A,N)
print(*bubble_A)
# バブルソートは安定なソートであるので Stable
print("Stable")

selection_sort(A,N)
print(*A)
# 選択ソートが安定かどうかはバブルソートの結果と一致するかを調べればいい
if bubble_A == A:
    print("Stable")
else:
    print("Not stable")

4. ALDS1_2_D: Shell Sort

シェルソートに関する問題です．交換回数はグローバル変数で管理しました．間隔の決め方と動作例についてはウィキペディアの記事を見てください．【外部サイト】シェルソート Wikipedia


# ALDS1_2_D
cnt = 0

# 挿入ソート
def insertion_sort(A,n,g):
    global cnt
    for i in range(g,n):
        v = A[i]
        j = i-g
        while j >= 0 and A[j]> v:
            A[j+g] = A[j]
            j = j-g
            cnt += 1
        A[j+g] = v

# シェルソート
def shell_sort(A,n):
    global cnt
    cnt = 0
    G = [1]
    for i in range(2,n):
        if (3**i-1)//2 > n:
            break
        G.append((3**i-1)//2)
        
    G.sort(reverse=True)
            
    for i in range(len(G)):
        insertion_sort(A,n,G[i])
        
    return G
        
N = int(input())
# 並べ替えるリストを受け取る
A = []
for i in range(N):
    num = int(input())
    A.append(num)

G = shell_sort(A,N)
print(len(G)) # Gの長さ
print(*G) # Gの要素
    
print(cnt) # 入れ替えの回数
# 並べ替え後の要素
for a in A:
    print(a)

<- 前へ戻る【目次に戻る】次へ進む ->