アルゴリズムとデータ構造

バブルソート (Bubble Sort)

整数を要素とする配列 n 個が与えられた場合、これらを昇順に並べ替えたいとします。バブルソートは、そのためのもっともシンプルかつ有名なアルゴリズムの一つです（ただし決して高速ではありませんので、実際の開発では他の手法を使うことが多いです）。
Video preview
バブルソートでは、配列の中を何度も走査し、隣り合う要素同士を比較して順番が逆の場合に入れ替えを行います。つまり、もし ならば、この２つを入れ替えて、配列が昇順になるように調整していきます。
具体的には、最初に配列 a（例えば [4, 1, -1, 0, 2, 8]）を用意し、先頭の２つの要素を比較します。もし順番が逆であれば入れ替えます（今回の例では [1, 4, -1, 0, 2, 8] になります）。次に、次の２つの要素を比較し、逆ならば入れ替え（今回の例では [1, -1, 4, 0, 2, 8] ）。これを配列の末尾まで繰り返します（例としては [1, -1, 4, 0, 2, 8] → [1, -1, 0, 4, 2, 8] → [1, -1, 0, 2, 4, 8] → 最後は変化なし → 完了）。
一通り末尾まで処理が終わったら、再び先頭から同じ処理を繰り返します。今回の例では、再度 [1, -1, 0, 2, 4, 8] の先頭からペアを見ていき、必要ならば入れ替えていきます（例では [1, -1, 0, 2, 4, 8] → [-1, 1, 0, 2, 4, 8] → [-1, 0, 1, 2, 4, 8] → これ以上変化せず）。
この処理を、配列が完全に昇順になるまで繰り返します:
a = [...]
while True:                                 # 配列がソートされるまで実行
    is_sorted = True                        # 要素を入れ替えたら False にする
    for i in range(len(a) - 1):             # 0 から n-2 まで繰り返す
        if a[i] > a[i + 1]:                 # 順序が逆なら
            is_sorted = False               # ソート完了ではなかった
            a[i], a[i + 1] = a[i + 1], a[i] # a[i] と a[i+1] を入れ替え
    
    if is_sorted:                           # 配列がソート済みなら終了
        break
print(a)
ただし、無駄な繰り返しを減らすための最適化が一つあります:
  • 各ループが終わるたび、もっとも大きい要素が配列の末尾に固定されるため、k 回処理を行った時点で末尾の k 個の要素はすでに正しい位置にあることが保証されます。そのため、内側のループではその部分をスキップできます。
a = [...]
for u in range(len(a) - 1, 0, -1):          # u は内側ループの上限
    is_sorted = True
    for i in range(u):                      # 0 から u-1 まで繰り返す
        if a[i] > a[i + 1]:
            is_sorted = False
            a[i], a[i + 1] = a[i + 1], a[i]
    
    if is_sorted:
        break
print(a)
要素が完全に降順となっている場合（昇順と真逆の状態）がバブルソートの最悪ケースで、そうなると演算回数が に達します。これは計算量の大きい処理であり、後に紹介する高速なアルゴリズムとは比較にならないほど非効率的です。
いくつかの配列を用いて、このアルゴリズムの動きを追ってみましょう:
[4, 1, -1, 0, 2, 8]
  1. u = 5
    1. i = 0 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]
    2. i = 1 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8]
    3. i = 2 ⇒ swap ⇒ [1, -1, 0, 4, 2, 8]
    4. i = 3 ⇒ swap ⇒ [1, -1, 0, 2, 4, 8]
    5. i = 4 ⇒ do nothing
  1. i = 0 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]
    1. i = 0 ⇒ swap ⇒ [-1, 1, 0, 2, 4, 8]
    2. i = 1 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
    3. i = 2 ⇒ do nothing
    4. i = 3 ⇒ do nothing
  1. i = 1 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8]
    1. i = 0 ⇒ do nothing
    2. i = 1 ⇒ do nothing
    3. i = 2 ⇒ do nothing
    4. is_sorted is True ⇒ break
  1. i = 2 ⇒ swap ⇒ [1, -1, 0, 4, 2, 8]
[10, 5, 1, -1, -2, -7]
  1. u = 5
    1. i = 0 ⇒ swap ⇒ [5, 10, 1, -1, -2, -7]
    2. i = 1 ⇒ swap ⇒ [5, 1, 10, -1, -2, -7]
    3. i = 2 ⇒ swap ⇒ [5, 1, -1, 10, -2, -7]
    4. i = 3 ⇒ swap ⇒ [5, 1, -1, -2, 10, -7]
    5. i = 4 ⇒ swap ⇒ [5, 1, -1, -2, -7, 10]
  1. i = 0 ⇒ swap ⇒ [5, 10, 1, -1, -2, -7]
    1. i = 0 ⇒ swap ⇒ [1, 5, -1, -2, -7, 10]
    2. i = 1 ⇒ swap ⇒ [1, -1, 5, -2, -7, 10]
    3. i = 2 ⇒ swap ⇒ [1, -1, -2, 5, -7, 10]
    4. i = 3 ⇒ swap ⇒ [1, -1, -2, -7, 5, 10]
  1. i = 1 ⇒ swap ⇒ [5, 1, 10, -1, -2, -7]
    1. i = 0 ⇒ swap ⇒ [-1, 1, -2, -7, 5, 10]
    2. i = 1 ⇒ swap ⇒ [-1, -2, 1, -7, 5, 10]
    3. i = 2 ⇒ swap ⇒ [-1, -2, -7, 1, 5, 10]
  1. i = 2 ⇒ swap ⇒ [5, 1, -1, 10, -2, -7]
    1. i = 0 ⇒ swap ⇒ [-2, -1, -7, 1, 5, 10]
    2. i = 1 ⇒ swap ⇒ [-2, -7, -1, 1, 5, 10]
  1. i = 3 ⇒ swap ⇒ [5, 1, -1, -2, 10, -7]
    1. i = 0 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 4 ⇒ swap ⇒ [5, 1, -1, -2, -7, 10]
[1, 2, 3, 4, 5]
  1. u = 5
    1. i = 0 ⇒ do nothing
    2. i = 1 ⇒ do nothing
    3. i = 2 ⇒ do nothing
    4. i = 3 ⇒ do nothing
    5. i = 4 ⇒ do nothing
    6. is_sorted is True ⇒ break
  1. i = 0 ⇒ do nothing
課外トピック（面白い動画）
Lines That Connect という方が制作した、バブルソートのアルゴリズムをより深く掘り下げ、アルゴリズムの作り出す曲線の直感的理解を解説する素晴らしい動画があります。
Video preview
Video by Lines That Connect - The Bubble Sort Curve.

チャレンジ

n 人が参加する競技会があり、それぞれの身長を昇順に整列させる必要があります。あなたは、隣り合った参加者2人に交代してもらう操作だけを使って並び替えを行うことを許されており、できるだけ効率よくこの操作を進めたいと考えています。
そこで、どのインデックスの2人が入れ替わるかを出力するプログラムを書くことにしました。インデックスは 0 から始まります。

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 1000).
The next line contains n space-separated integers ( ≤ ≤ ) the heights of participants.

Output

The program should print the pairs of indices of participants that need to switch positions. Each pair needs to be printed on a separate line. In case of multiple optimal answers, any configuration is acceptable.

Examples

入力
出力
5 1 4 8 2 -1
2 3 3 4 1 2 2 3 1 2 0 1

Explanation

  1. 2 ↔ 3 ⇒ 1 4 2 8 -1
  1. 3 ↔ 4 ⇒ 1 4 2 -1 8
  1. 1 ↔ 2 ⇒ 1 2 4 -1 8
  1. 2 ↔ 3 ⇒ 1 2 -1 4 8
  1. 1 ↔ 2 ⇒ 1 -1 2 4 8
  1. 0 ↔ 1 ⇒ -1 1 2 4 8
 

Constraints

Time limit: 1.98 seconds

Memory limit: 512 MB

Output limit: 10 MB

To check your solution you need to sign in
Sign in to continue