Bubble Sort

Pythonで「バブルソート（Bubble Sort）」

はじめに

ここでは「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」の中で取り上げられている「AOJ (Aizu Online Judge」)の問題を自分で解いた際に学んだことや、こう考えれば分かりやすいと感じたことなどを自分への整理も兼ねてまとめています。
このテキストはC++で書かれているので、私のようにpythonで勉強をされている初学者の方の参考になれば幸いです。また私自身も初学者ゆえ、至らない点が多々あると思いますので、ご指摘・ご助言頂ければ喜びます。よろしくお願いします。

問題詳細

ALDS1_2_A; Bubble Sort
バブルソートで昇順に並べ替える問題です。
問題詳細は上記リンクをご参考ください

考え方

●順番が逆になっている隣接要素が無くなるまで、次の処理を繰り返します
1. 配列の末尾から隣接する要素を比べていき、大小関係が逆なら交換

pythonコード

def BubbleSort(A, N):
    cnt = 0     # 隣接要素の交換回数
    for i in range(N):      # iは未ソートの部分列の先頭のインデックス
        for j in range(N-1, i, -1):     # 隣接要素を比較するのは未ソート部分列の末尾から先頭まで
            if A[j-1] > A[j]:           # 隣接要素を比較
                A[j-1], A[j] = A[j], A[j-1]     # 大小関係が逆の場合、交換
                cnt += 1        
    return A, cnt

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

ans, cnt = BubbleSort(A,N)
print(*ans)    # リストの中身を値で取り出す
print(cnt)

ポイント

1. 末尾から順番に隣接要素の大小を比較していきますが、既に大小関係が正しい場合には交換は行わず、そのまま次の隣接要素の比較に移っていきます（同じループ内）。

2. 各計算ステップにおいて、配列は「ソート済みの部分列（i-1番目まで）」と「未ソートの部分列（i番目以降）」に分かれていると考える事ができます。そのため、隣接要素の比較はi番目の要素までで行えばよいことになります。

3. jの範囲についてですが、まずN-1は未ソート部分列の末尾のインデックスです。

一方で、

for j in range(N-1, i, -1):

において、rangeは第２引数の手前までが範囲となるため、この場合j=i+1までになっています。しかしこれは、隣接要素の比較時にj-1番目とj番目を比較していることから、きちんとi番目の要素（未ソート部分列の先頭）を考慮できています。

まとめ

以上となります。いかがでしたでしょうか。
間違いや改善点などございましたら、よろしくお願いいたします。