Python3でクイックソートを書いてみた
- 作者: 伊藤静香
- 出版社/メーカー: インプレス
- 発売日: 2016/03/16
- メディア: Kindle版
- この商品を含むブログ (1件) を見る
- 「アルゴリズムを、はじめよう」第10章クイックソートから。
- リストの先頭値を基準値として昇順にクイックソートします。
- Pythonっぽくカッコよく書けないかと思い試行錯誤してみましたが、 結局本に記載されている擬似言語コードを書き起こしただけになってしまいました。
- 再帰カッコイイ
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]