Pythonでクイックソートを実装してみた

概要

Pythonでクイックソートを実装してみました。以下のページを参考にしました。
http://www1.cts.ne.jp/~clab/hsample/Sort/Sort9.html

ソースコード

上記コードのC言語になっているのをPythonに書き換えただけです。新規性はありません。

quick_sort2.py

import random

data = {}
data2 = {}
NUM = 10
i = 0
while i < NUM:
    data[i] = random.random()
    i = i + 1

#show
def show_data():
    print("==>> show data")
    i = 0
    while i < NUM:
        print ( str(i) + ":" + str(data[i]) )
        i = i + 1

def show_data2():
    print("==>> show data2")
    i = 0
    while i < NUM:
        print ( str(i) + ":" + str(data2[i]) )
        i = i + 1

#copy
def copy_data_to_data2():
    print("==>> copy data to data2")
    i = 0
    while i < NUM:
        data2[i] = data[i]
        i = i + 1

#quick_sort2
def quick_sort2(array, left, right):
    print("==>> quick sort2")
    i = left
    j = right
    pivot = array[int((left+right) / 2)]
    while True:
        while array[i] < pivot:
            i = i + 1
        while pivot < array[j]:
            j = j - 1
        if i >= j:
            break
        tmp = array[i]
        array[i] = array[j]
        array[j] = tmp
        i = i + 1
        j = j - 1
    if left < i - 1:
        quick_sort2(array, left, i - 1)
    if j + 1 < right:
        quick_sort2(array, j + 1, right)

copy_data_to_data2()
show_data2()
quick_sort2(data2, 0, NUM-1)
show_data2()

実行結果

ちゃんと実行できました。アルゴリズムは無事動いているようです。

$ python3 quick_sort2.py 
==>> copy data to data2
==>> show data2
0:0.8969745850034738
1:0.6939236435877685
2:0.6311058167247571
3:0.45635917159782413
4:0.2613377918663322
5:0.39833556618487165
6:0.509455775434223
7:0.20510519476218125
8:0.9416542109856895
9:0.6955748482344979
==>> quick sort2
==>> quick sort2
==>> quick sort2
==>> quick sort2
==>> quick sort2
==>> quick sort2
==>> quick sort2
==>> quick sort2
==>> show data2
0:0.20510519476218125
1:0.2613377918663322
2:0.39833556618487165
3:0.45635917159782413
4:0.509455775434223
5:0.6311058167247571
6:0.6939236435877685
7:0.6955748482344979
8:0.8969745850034738
9:0.9416542109856895