python で 挿入ソート
最近プログラミングの基礎をちょっとずつ読んでます。
プログラミングの基礎 (Computer Science Library)
- 作者: 浅井健一
- 出版社/メーカー: サイエンス社
- 発売日: 2007/03
- メディア: 単行本
- 購入: 17人 クリック: 409回
- この商品を含むブログ (126件) を見る
ocamlを題材にした有名な本です。
10章くらいで再帰を使って挿入ソートを書くという問題がでてきます。
答えはサポートページにありますが、ocamlで書いたあと、普段使ってるpythonでも書いてみました。
python 2.7です
def insert(lst, n): """昇順リストlstにnを適切な位置に挿入して返す """ if not lst: return [n] else: first, rest = lst[0], lst[1:] if first > n: return [n] + [first] + rest else: return [first] + insert(rest, n) assert insert([], 5) == [5] assert insert([1, 3, 4, 7, 8], 5) == [1, 3, 4, 5, 7, 8] def ins_sort(lst): """受け取った整数のリストlstを挿入法で昇順に並べる """ if not lst: return [] else: first, rest = lst[0], lst[1:] return insert(ins_sort(rest), first) assert ins_sort([]) == [] assert ins_sort([1]) == [1] assert ins_sort([2, 1]) == [1, 2] assert ins_sort([5, 3, 8, 1, 7, 4]) == [1, 3, 4, 5, 7, 8]
python3だとifが値を返すようになるんでしたっけ