【アルゴリズム】Pythonでクイックソートを実装しアルゴリズムを理解する

あい

今回はpythonで
クイックソートを
実装しアルゴリズム
を理解します

[R]※本サイトにはプロモーションが含まれています

1 ソートとは
2 クイックソート実装
3 参考文献

ソートとは

データを一定の規則に従って並び替える処理

データの並び変え処理には主に

昇順, 降順がある

昇順 : 小さな数から大きな数へ

降順 :大きな数から小さな数へ

以下データを並び替える

昇順

降順

# 初期データ
data = [8, 6, 5, 3, 6, 10, 4]

# 昇順に並べ替え
ascending_data = sorted(data)
print("昇順:", ascending_data)

# 降順に並べ替え
descending_data = sorted(data, reverse=True)
print("降順:", descending_data)

実行結果

クイックソート実装

データを昇順にソートするクイックソートを

pythonを利用して実装します

data = [8,6,5,3,6,10,4]
n = len(data) 
print(f"要素数 = {n}")

def quick_sort(left, right):
    print("----def quick_sort-----------------------------------------------------")
    i = left
    j = right
    pivot = data[(left + right)//2]
    print(f"data[pivot] = {pivot}, data[{i}] ={data[i]}, data[{j}] = {data[j]}")

    while True:
        while data[i] < pivot:
            i = i + 1
            print(f"i = {i}, data[i] ={data[i]} ")
        while data[j] > pivot:
            j = j - 1
            print(f"j = {j}, data[j] ={data[j]} ")
        if i >= j:
            break
        print(f"{i}番地 の{data[i]}と{j}番地 = {data[j]}を入れ替える")
        data[i],data[j] = data[j],data[i]
        i = i + 1
        j = j - 1
    if left < i - 1:
        quick_sort(left,i - 1)
    if right > j + 1:
        quick_sort(j + 1,right)

print(data,"元のデータ")
quick_sort(0,n-1)
print(data,"クイックソート後のデータ")

あい

アルゴリズムが複雑なので
各所にprint関数を

挿入しました
出力を観察し
アルゴリズムを理解します

データを格納する

data = [8,6,5,3,6,10,4]
n = len(data) 
print(f"データ数 = {n}")

クイックソートを行う関数を定義し

データ探索を行うためのiとj

基準(pivot)を渡します

def quick_sort(left, right):
    print("----def quick_sort-----------------------------------------------------")
    i = left
    j = right
    pivot = data[(left + right)//2]
    print(f"data[pivot] = {pivot}, data[{i}] ={data[i]}, data[{j}] = {data[j]}")

無限ループに入る

d[0] = 8> 3より

while data[i] < pivot:

は実行されず

i = 0

    while True:
        while data[i] < pivot:
            i = i + 1

d[6] = 4> pivotより

while data[j] > pivot:を実行

条件式が偽なるまで

while処理を実行します

j = 3で処理を抜ける

        while data[j] > pivot:
            j = j - 1

whileを抜け

0と3番地のデータを入れ替えます

       if i >= j:
            break
        print(f"{i}番地 の{data[i]}と{j}番地 = {data[j]}を入れ替える")
        data[i],data[j] = data[j],data[i]

交換した番地から

左右に番地を1つshiftさせて

無限ループの最初に戻る

        if i >= j:
            break
        print(f"{i}番地 の{data[i]}と{j}番地 = {data[j]}を入れ替える")
        data[i],data[j] = data[j],data[i]
        i = i + 1
        j = j - 1

d[1] = 6> 3より

while data[i] < pivot:

は実行されず

i = 1

    while True:
        while data[i] < pivot:
            i = i + 1

d[2] = 5 > 3より

while data[j] > pivot:を実行

条件式が偽なるまで

while処理を実行します

j = 0で処理を抜ける

        while data[j] > pivot:
            j = j - 1

i = 1, j = 3

より無限ループを抜ける

       if i >= j:
            break

left = 0, i-1 =0

right = 6, j +1 = 1より

if right > j + 1:を実行し

再帰関数呼び出す

    if left < i - 1:
        quick_sort(left,i - 1)
    if right > j + 1:
        quick_sort(j + 1,right)

再起関数を呼び出し

データ探索を行うためのiとj

基準(pivot)を渡します

def quick_sort(left, right):
    print("----def quick_sort-----------------------------------------------------")
    i = left
    j = right
    pivot = data[(left + right)//2]
    print(f"data[pivot] = {pivot}, data[{i}] ={data[i]}, data[{j}] = {data[j]}")