QuickSort

最も有名なソートアルゴリズムの一つに QuickSort があります。これは分割統治法を用いており、配列からピボット（pivot）要素を選び、そのピボットより「小さい」「等しい」「大きい」という3つの領域に分割します。そして、すべての要素が整列されるまで同じ処理を繰り返します。

各繰り返しで行うことは次の通りです:

配列からピボット要素を選ぶ
ピボットより小さい要素を左側に移動する
ピボットより大きい要素を右側に移動する
ピボットと等しい要素を真ん中にまとめる
左側と右側の部分それぞれに対して同じプロセスを繰り返す

def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = a[len(a) // 2]
    left = [x for x in a if x < pivot]
    middle = [x for x in a if x == pivot]
    right = [x for x in a if x > pivot]
    return quicksort(left) + middle + quicksort(right)

この QuickSort の実装では、left・middle・right 用に追加の配列を使っていますが、インデックスを使って配列を直接並べ替えることでインプレース (in place) に書き換えることもできます。

def quicksort(a, start, end):
    if start >= end:                    # ソートする要素がありません
        return

    pivot = a[start]                    # ピボットを選びます
    l, r = start + 1, end               # a[start+1 ... end]の範囲をソートします
    while l <= r:                       # まだ範囲内に要素がある間は繰り返します
        if a[l] < pivot:                # a[l] < pivot の場合 -> a[i]はそのまま
            l += 1                      # 左ポインタを進める
        else:                           # それ以外の場合は a[l] を末尾へ移動
            a[l], a[r] = a[r], a[l]     # a[l] と a[r] を入れ替え (末尾へ移動)
            r -= 1                      # 右ポインタを減らす

    a[start], a[r] = a[r], a[start]     # pivot を a[r] と入れ替える
    quicksort(a, start, r - 1)          # a[start ... r-1] をソート
    quicksort(a, r + 1, end)            # a[r+1 ... end] をソート

2つの実装を見てわかるように、ピボットをどこから選ぶかは QuickSort で制約されていません。選択方法はいくつかあり、以下が例です:

先頭要素: a[start]（上の2番目の実装）
末尾要素: a[end]
中央要素: a[(start + end + 1) // 2]
ランダム要素: a[start ... end] のどれか
区間の中央値: 今の部分配列の要素の中央値を選ぶ。分割後の「小さい部分」と「大きい部分」が常に同じ大きさになる利点はありますが、実装はより複雑になります。

それでは、いくつかの配列に対してアルゴリズムをシミュレーションしてみましょう。

[4, 1, -1, 0, 2, 8]

quicksort(a, 0, 5) → pivot = 4
[4, 1, -1, 0, 2, 8]
1. l=1, r=5 ⇒ a[l] = 1 < pivot ⇒ l += 1
2. l=2, r=5 ⇒ a[l] = -1 < pivot ⇒ l += 1
3. l=3, r=5 ⇒ a[l] = 0 < pivot ⇒ l += 1
4. l=4, r=5 ⇒ a[l] = 2 < pivot ⇒ l += 1
5. l=5, r=5 ⇒ a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
6. swap a[start] and a[r] ⇒ [2, 1, -1, 0, 4, 8]
7. quicksort(a, 0, 3) and quicksort(a, 5, 5)
quicksort(a, 0, 3) → pivot = 2
[2, 1, -1, 0, 4, 8]
1. l=1, r=3 ⇒ a[l] = 1 < pivot ⇒ l += 1
2. l=2, r=3 ⇒ a[l] = -1 < pivot ⇒ l += 1
3. l=3, r=3 ⇒ a[l] = 0 < pivot ⇒ l += 1
4. swap a[start] and a[r] ⇒ [0, 1, -1, 2, 4, 8]
5. quicksort(a, 0, 2) and quicksort(a, 3, 3)
quicksort(a, 0, 2) → pivot = 0
[0, 1, -1, 2, 4, 8]
1. l=1, r=2 ⇒ a[l] = 1 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [0, -1, 1, 2, 4, 8]
2. l=1, r=1 ⇒ a[l] = -1 < pivot ⇒ l += 1
3. swap a[start] and a[r] ⇒ [-1, 0, 1, 2, 4, 8]
4. quicksort(a, 0, 0) and quicksort(a, 2, 2)
[-1, 0, 1, 2, 4, 8]

[4, 5, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, -1]

quicksort(a, 0, 12) → pivot = 4
[4, 5, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, -1]
1. l=1, r=12 ⇒ a[l] = 5 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [4, 5, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, -1]
2. l=1, r=11 ⇒ a[l] = -1 < pivot ⇒ l += 1
3. l=2, r=11 ⇒ a[l] = 3 < pivot ⇒ l += 1
4. l=3, r=11 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [4, -1, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, 5]
5. l=3, r=10 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [4, -1, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, 5]
6. l=3, r=9 ⇒ a[l] = 7 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [4, -1, 3, 7, 4, 8, 4, 1, 2, 9, 4, 4, 5]
7. l=3, r=8 ⇒ a[l] = 9 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [4, -1, 3, 9, 4, 8, 4, 1, 2, 7, 4, 4, 5]
8. l=3, r=7 ⇒ a[l] = 2 < pivot ⇒ l += 1
9. l=4, r=7 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [4, -1, 3, 2, 4, 8, 4, 1, 9, 7, 4, 4, 5]
10. l=4, r=6 ⇒ a[l] = 1 < pivot ⇒ l += 1
11. l=5, r=6 ⇒ a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [4, -1, 3, 2, 1, 8, 4, 4, 9, 7, 4, 4, 5]
12. l=5, r=5 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [4, -1, 3, 2, 1, 4, 8, 4, 9, 7, 4, 4, 5]
13. swap a[start] and a[r] ⇒ [1, -1, 3, 2, 4, 4, 8, 4, 9, 7, 4, 4, 5]
14. quicksort(a, 0, 3) and quicksort(a, 5, 12)
quicksort(a, 0, 3) → pivot = 1
[1, -1, 3, 2, 4, 4, 8, 4, 9, 7, 4, 4, 5]
1. l=1, r=3 ⇒ a[l] = -1 < pivot ⇒ l += 1
2. l=2, r=3 ⇒ a[l] = 3 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [1, -1, 3, 2, 4, 4, 8, 4, 9, 7, 4, 4, 5]
3. l=2, r=2 ⇒ a[l] = 2 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [1, -1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
4. swap a[start] and a[r] ⇒ [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
5. quicksort(a, 0, 0) and quicksort(a, 2, 3)
quicksort(a, 2, 3) → pivot = 2
[-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
1. l=3, r=3 ⇒ a[l] = 3 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
2. swap a[start] and a[r] ⇒ [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
3. quicksort(a, 2, 1) and quicksort(a, 3, 3)
quicksort(a, 5, 12) → pivot = 4
[-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
1. l=6, r=12 ⇒ a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
2. l=6, r=11 ⇒ a[l] = 5 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [-1, 1, 2, 3, 4, 4, 5, 4, 9, 7, 4, 4, 8]
3. l=6, r=10 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [-1, 1, 2, 3, 4, 4, 4, 4, 9, 7, 4, 5, 8]
4. l=6, r=9 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [-1, 1, 2, 3, 4, 4, 4, 4, 9, 7, 4, 5, 8]
5. l=6, r=8 ⇒ a[l] = 7 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [-1, 1, 2, 3, 4, 4, 7, 4, 9, 4, 4, 5, 8]
6. l=6, r=7 ⇒ a[l] = 9 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [-1, 1, 2, 3, 4, 4, 9, 4, 7, 4, 4, 5, 8]
7. l=6, r=6 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [-1, 1, 2, 3, 4, 4, 4, 9, 7, 4, 4, 5, 8]
8. swap a[start] and a[r] ⇒ [-1, 1, 2, 3, 4, 4, 4, 9, 7, 4, 4, 5, 8]
9. quicksort(a, 5, 4) and quicksort(a, 6, 12)
quicksort(a, 6, 12) → pivot = 4
[-1, 1, 2, 3, 4, 4, 4, 9, 7, 4, 4, 5, 8]
1. l=7, r=12 ⇒ a[l] = 9 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [-1, 1, 2, 3, 4, 4, 4, 9, 7, 4, 4, 5, 8]
2. l=7, r=11 ⇒ a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [-1, 1, 2, 3, 4, 4, 4, 8, 7, 4, 4, 5, 9]
3. l=7, r=10 ⇒ a[l] = 5 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [-1, 1, 2, 3, 4, 4, 4, 5, 7, 4, 4, 8, 9]
4. l=7, r=9 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [-1, 1, 2, 3, 4, 4, 4, 4, 7, 4, 5, 8, 9]
5. l=7, r=8 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [-1, 1, 2, 3, 4, 4, 4, 4, 7, 4, 5, 8, 9]
6. l=7, r=7 ⇒ a[l] = 7 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 8, 9]
7. swap a[start] and a[r] ⇒ [-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 8, 9]
8. quicksort(a, 6, 5) and quicksort(a, 7, 12)
quicksort(a, 7, 12) → pivot = 7
[-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 8, 9]
1. l=8, r=12 ⇒ a[l] = 4 < pivot ⇒ l += 1
2. l=9, r=12 ⇒ a[l] = 4 < pivot ⇒ l += 1
3. l=10, r=12 ⇒ a[l] = 5 < pivot ⇒ l += 1
4. l=11, r=12 ⇒ a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 8, 9]
5. l=11, r=11 ⇒ a[l] = 9 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 9, 8]
6. swap a[start] and a[r] ⇒ [-1, 1, 2, 3, 4, 4, 4, 5, 4, 4, 7, 9, 8]
7. quicksort(a, 7, 9) and quicksort(a, 11, 12)
quicksort(a, 7, 9) → pivot = 5
[-1, 1, 2, 3, 4, 4, 4, 5, 4, 4, 7, 9, 8]
1. l=8, r=9 ⇒ a[l] = 4 < pivot ⇒ l += 1
2. l=9, r=9 ⇒ a[l] = 4 < pivot ⇒ l += 1
3. swap a[start] and a[r] ⇒ [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
4. quicksort(a, 7, 8) and quicksort(a, 10, 9)
quicksort(a, 7, 8) → pivot = 4
[-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
1. l=8, r=8 ⇒ a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
  [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
2. swap a[start] and a[r] ⇒ [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
3. quicksort(a, 7, 6) and quicksort(a, 8, 8)
quicksort(a, 11, 12) → pivot = 9
[-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
1. l=12, r=12 ⇒ a[l] = 8 < pivot ⇒ l += 1
2. swap a[start] and a[r] ⇒ [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 8, 9]
3. quicksort(a, 11, 11) and quicksort(a, 13, 12)
[-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 8, 9]

QuickSort の平均実行時間はですが、ピボットの選び方によってはの計算量になる場合があります。

🤔 もし毎回 start の要素をピボットとして選ぶとしたら、どのような入力例での動きになるでしょうか？

Challenge

与えられた n 個の整数のリストと q 個のピボットについて、それぞれのピボットを基準に、ピボットより小さい要素を左側、ピボットより大きい要素を右側に移動させます。また、ピボットと等しい要素は互いに隣接させ、小さい要素群と大きい要素群の間に位置させてください。

入力

最初の行に整数 n (1 ≤ n ≤ 100 000) が与えられます。

次の行には、n 個のスペース区切り整数 ( ≤ ≤ ) が与えられます。

3行目には整数 q (1 ≤ q ≤ 10) が与えられます。

4行目には、q 個のスペース区切り整数 (1 ≤ ≤ n) が与えられ、これはピボット要素のインデックスを表します。

出力

それぞれのピボットについて、再配置を行った後の配列を出力してください。複数の正解がある場合はそのうちのどれを出力しても構いません。

Examples

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

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 10 MB

QuickSort

Challenge

入力

出力

Examples

Constraints

To check your solution you need to sign in

Sign in to continue