AT's Blog

プログラミング、回路設計、ギター、音楽、読書とか

Python3でクイックソートを書いてみた

quick_sort.py

import random

def qsort(ls, left, right):
    print("----")
    print("ls:",ls)
    print("left:",left)
    print("right:",right)

    i = left + 1
    k = right
    
    while(i < k):
        while((ls[left] > ls[i]) and (i < right)):
            i += 1
        while((ls[left] < ls[k]) and (k > left)):
            k -= 1
        if(i < k):
            ls[i], ls[k] = ls[k], ls[i]

    if(ls[left] > ls[k]):
        ls[left], ls[k] = ls[k], ls[left]

    if(left < k-1):
        qsort(ls, left, k-1)
    if(right > k+1):
        qsort(ls, k+1, right)
        
    return

def main():
    ls = list(range(0,10))
    random.shuffle(ls)

    qsort(ls, 0, len(ls)-1)
    print(ls)
    
if __name__ == '__main__':
    main()

実行結果

>python quick_sort.py
----
ls: [6, 8, 3, 1, 0, 7, 9, 2, 4, 5]
left: 0
right: 9
----
ls: [2, 5, 3, 1, 0, 4, 6, 9, 7, 8]
left: 0
right: 5
----
ls: [1, 0, 2, 3, 5, 4, 6, 9, 7, 8]
left: 0
right: 1
----
ls: [0, 1, 2, 3, 5, 4, 6, 9, 7, 8]
left: 3
right: 5
----
ls: [0, 1, 2, 3, 5, 4, 6, 9, 7, 8]
left: 4
right: 5
----
ls: [0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
left: 7
right: 9
----
ls: [0, 1, 2, 3, 4, 5, 6, 8, 7, 9]
left: 7
right: 8
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]