配列を使ったヒープソート

一昨日は二分木を使ったヒープソートを作った。配列を使ったヒープの構造についてはここのページのヒープの項が分かりやすい。

 cf. 二分木 (binary tree) とヒープ (heap) – Algorithms with Python

二分木のルートを番号 0 として、各ノードに幅優先で左から番号をふっていく。ふった番号を配列の添字だと考えれば、次の関係が成り立つ。
すなわち、親の添字を k とすると:

  • 左側の子の添字は 2 * k + 1
  • 右側の子の添字は 2 * k + 2

子の添字を k とすると:

  • 親の添字は floor((k – 1) / 2)

となる。
これで二分木を配列に置き換えられる。後はやることは基本的に一緒だ。

実行例:

unsorted: [15, 70, 93, 27, 5, 8, 26, 40, 74, 67]
sorted:   [5, 8, 15, 26, 27, 40, 67, 70, 74, 93]

[おまけ]

二分木を使ったヒープソート(heap_sort.rb)と今日の配列を使ったヒープソート(heap_sort2.rb)の実行時間の比較をしてみた。

takatoh@nightschool $ time ruby heap_sort.rb
unsorted: [85, 61, 68, 9, 73, 79, 26, 84, 21, 13]
sorted:   [9, 13, 21, 26, 61, 68, 73, 79, 84, 85]

real	0m0.102s
user	0m0.019s
sys	0m0.008s
takatoh@nightschool $ time ruby heap_sort2.rb
unsorted: [65, 26, 92, 51, 33, 31, 61, 97, 34, 57]
sorted:   [26, 31, 33, 34, 51, 57, 61, 65, 92, 97]

real	0m0.034s
user	0m0.017s
sys	0m0.017s

配列を使ったヒープソートのほうが3倍位速い。ま、そうだろうな…と思ったら、user の時間は大して変わらないな。

二分ヒープ(ヒープ木)を使ったヒープソート

ヒープソートって配列を使ってやるのがフツウみたいだけど、アルゴリズムのアイデアに忠実に二分ヒープ(木)を使ってやってみた。
参考にしたページはココらへん。

 cf. 二分木 (binary tree) とヒープ (heap) – Algorithms with Python
 cf. 二分ヒープ – ウィキペディア

なんだかあんまりきれいじゃないけど。特に downheap のあたりが。
とりあえず出来たって感じ。
最初は upheap や downheap でノード自体を入れ替えようとしてたのでもっとひどかった。ノードはそのままにしておいて持っている値だけ入れ替えればいいことに気づいていくらかマシになった。

実行結果:

takatoh@nightschool $ ruby heap_sort.rb
unsorted: [75, 63, 96, 9, 21, 92, 48, 83, 51, 31]
sorted:   [9, 21, 31, 48, 51, 63, 75, 83, 92, 96]

Rubyでクイックソート

 cf. RubyでクイックソートとRSpecでそのテストを書いてみる – 凸ろぐ

なんだかまどろっこしい書き方をしてるなあ。これでいいんじゃないか?

takatoh@nightschool $ ruby qsort.rb
                    user     system      total        real
Array#sort:     0.000000   0.000000   0.000000 (  0.000006)
Array#qsort:    0.000000   0.000000   0.000000 (  0.000013)

Array#soft 速いな。やっぱり自前で作るよりあるものを使ったほうがいいってことか。
いや、リンク先の実装だと速いのか?

takatoh@nightschool $ ruby qsort2.rb
                 user     system      total        real
Array#sort:   0.000000   0.000000   0.000000 (  0.000006)
Array#qsort:  0.000000   0.000000   0.000000 (  0.000019)

そんなことはなかった。

Schemeでユークリッドの互除法

今日は時間がないので埋草的エントリ。
ユークリッドの互除法で最大公約数を求める。

takatoh@nightschool $ gosh gcd.scm
21

Schemeでマージソート

やってみた。

実行結果:

^o^ > gosh merge-sort.scm
(1 2 3 4 5 6 7 8 9)

バイナリサーチ

AOJの問題を解く途中で作ったのでメモしておく。結局使わなくなったけど。
あらかじめソートされているのが前提。見つからないときは None を返す。

実行結果:

^o^ > python binary_search.py
3359
None
0
None

素数を無限に列挙するジェネレータ

エラトステネスの篩を応用して書いてみた。

^o^ > python primes3.py 100
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

ここでは100未満の素数を出力している。さすがに primes3.py 1000000 とかやると遅い。

挿入ソート

Pythonでやってる人を見かけたので俺も。

実行結果:

^o^ > python insertion_sort.py
unsorted: [1, 9, 6, 3, 8, 6, 5, 2, 7, 4, 2, 9, 8, 5, 7, 3, 4, 1]
sorted:   [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]

Python の for文には else をつけることができるんだ。初めて使った。

Luhnアルゴリズムでクレジットカードの番号をチェック:Haskell版

こないだやったLuhnアルゴリズムでのチェックをHaskellでもやってみた。

実行結果:

^o^ > runhaskell checkCardNumber.hs
True
True
True
True
True
True
True
True
True
True
True
True
True

Luhnアルゴリズムでクレジットカードの番号をチェック

クレジットカード番号のチェックサムには Luhnアルゴリズムというのが使われているのを知った。

cf. Luhnアルゴリズムでクレジットカードの番号をチェック – brainstorm
cf. Luhnアルゴリズム – Wikipedia

Rubyでやってみた。

カード番号の例は↓ここで紹介されているもの。
cf. ECサイトの動作テストに使える、クレジットカードのテスト番号一覧 – Webクリエイターボックス

実行結果:

^o^ > check_card_numbers.rb
true
true
true
true
true
true
true
true
true
true
true
true
true