新・アルゴリズムとデータ構造入門 Python編5:クイックソートの実装

count = 0


def print_array(a):
    print(*a)


def quick_sort(a, left, right):
    global count

    # もし left が right-1 以上なら終了

    # pivot に a[right-1] を代入
    # cur_index を left で初期化
    for i in range(left, right-1):
        # もし a[i] が pivot より小さいなら
        if """""":
            # a[cur_index] と a[i] を交換
            # cur_index を 1 だけ増やす
            count += 1

    # pivot と a[cur_index] を交換

    # quick_sort(a, left, cur_index) を呼び出す
    # quick_sort(a, cur_index+1, right) を呼び出す


n = int(input())
a = [int(x) for x in input().split()]

quick_sort(a, 0, n)

print_array(a)
print(count)

count = 0


def print_array(a):
    print(*a)


def quick_sort(a, left, right):
    global count

    # もし left が right-1 以上なら終了

    # pivot に a[right-1] を代入
    # cur_index を left で初期化
    for i in range(left, right-1):
        # もし a[i] が pivot より小さいなら
        if """""":
            # a[cur_index] と a[i] を交換
            # cur_index を 1 だけ増やす
            count += 1

    # pivot と a[cur_index] を交換

    # quick_sort(a, left, cur_index) を呼び出す
    # quick_sort(a, cur_index+1, right) を呼び出す


n = int(input())
a = [int(x) for x in input().split()]

quick_sort(a, 0, n)

print_array(a)
print(count)

count = 0


def print_array(a):
    print(*a)


def quick_sort(a, left, right):
    global count

    if left >= right - 1:
        return

    pivot = a[right-1]
    cur_index = left
    for i in range(left, right-1):
        if a[i] < pivot:
            a[i], a[cur_index] = a[cur_index], a[i]
            cur_index += 1
            count += 1

    a[right-1], a[cur_index] = a[cur_index], pivot

    quick_sort(a, left, cur_index)
    quick_sort(a, cur_index, right)


n = int(input())
a = [int(x) for x in input().split()]

quick_sort(a, 0, n)

print_array(a)
print(count)

count = 0


def print_array(a):
    print(*a)


def quick_sort(a, left, right):
    global count

    if left >= right - 1:
        return

    pivot = a[right-1]
    cur_index = left
    for i in range(left, right-1):
        if a[i] < pivot:
            a[i], a[cur_index] = a[cur_index], a[i]
            cur_index += 1
            count += 1

    a[right-1], a[cur_index] = a[cur_index], pivot

    quick_sort(a, left, cur_index)
    quick_sort(a, cur_index, right)


n = int(input())
a = [int(x) for x in input().split()]

quick_sort(a, 0, n)

print_array(a)
print(count)

この動画を見るにはpaiza会員登録のうえ
有料会員登録が必要です

無料会員登録して始める

演習1

問題ログインすると模範解答や入力を見ることができます

演習課題「正しくクイックソートを実装する」

整数nと要素数nの数列Aが与えられるので、この数列をクイックソートでソートしてください。
右側のコードエリアに用意されているコードには誤りがあります。訂正し、問題を解くコードを完成させてください。

【制約】
・入力は全て整数
・ 1≦n≦10
・ 1≦(数列Aの各要素)≦100

入力される値

4
1 1 1 1

標準入力からの値取得方法はこちらをご確認ください

期待する出力値

1 1 1 1
0

Tips

動画へ戻る

次のレッスンへ前のチャプターへ

※有料会員になるとこの動画をご利用いただけます

詳しい説明を読む

＃07:クイックソートの実装

実際にクイックソートを実装してみます。そして、とても効率的にソートが行われていることを確認してみましょう。

「クイックソート」へのリンク

「クイックソート」の問題を見る

入力される値

n
A_1 A_2 ... A_n

・入力はすべて整数
・ 1行目に、数列の要素数nが与えられます。
・ 2行目に、数列の要素A_1,A_2,...,A_nが半角スペース区切りで与えられます。

実行するコード

count = 0


def print_array(a):
    print(*a)


def quick_sort(a, left, right):
    global count

    # もし left が right-1 以上なら終了
    if left >= right - 1:
        return

    # pivot に a[right-1] を代入
    pivot = a[right-1]

    # cur_index を left で初期化
    cur_index = left
    for i in range(left, right-1):
        # もし a[i] が pivot より小さいなら
        if a[i] < pivot:
            # a[cur_index] と a[i] を交換
            a[i], a[cur_index] = a[cur_index], a[i]

            # cur_index を 1 だけ増やす
            cur_index += 1
            count += 1

    # pivot と a[cur_index] を交換
    a[right-1], a[cur_index] = a[cur_index], pivot

    # quick_sort(a, left, cur_index) を呼び出す
    quick_sort(a, left, cur_index)
    # quick_sort(a, cur_index+1, right) を呼び出す
    quick_sort(a, cur_index+1, right)


n = int(input())
a = [int(x) for x in input().split()]

quick_sort(a, 0, n)

print_array(a)
print(count)