import random

# qsort関数が行った繰り返し処理の回数
loop_count = 0

# 配列aを昇順にクイックソートする関数
def qsort(a):
  global loop_count

  # 配列aが空なら、空の配列を返す
  if len(a) == 0:
    return []
  
  # 先頭の要素を取り出して基準値とする
  pivot = a.pop(0)

  # 空の配列bと配列ｃを用意する
  b = []
  c = []
  
  # 配列aの残りの要素を配列bと配列cにグループ分けする
  for e in a:
    # 基準値より小さい要素を配列bに追加する
    if e < pivot:
      b.append(e)
    # そうでない要素を配列cに追加する
    else:
      c.append(e)
    # 繰り返し処理の回数をカウントアップする
    loop_count += 1

  # 配列aをソートした結果を返す（再帰呼び出し）
  return qsort(b) + [pivot] + qsort(c)

# メイン関数
def main():
  result = qsort([3, 10, 7, 2, 5, 8, 4, 1, 6, 9])
  print(f"ソートした結果：{result}")
  print(f"繰り返し処理の回数:{loop_count}")

# プログラムの起動時にmain関数を呼び出す
if __name__ == "__main__":
  main()
