BTreeを書いた．集合型ということで． setと最小値を取り出すminpopのみサポート．木のバランスが崩れたときの再構築とかは考えていない． num === null) { $this->num = $x; } else { if ($this->num > $x) { $call = "left"; } else…

まーPHP 5.2.x 系以前でこういうことやろうとすると当然create_functionなどというひどいものを使わないといけなかったり。つーか、配列の結合が、+ と array_merge のどっちつかうかは何年PHPつかってても身に付かんな。添字配列と連想配列が一緒くたに扱わ…

リスト内包を使わない場合以下のようなかんじか？ #!/usr/bin/env python # -*- coding: utf-8 -*- def qsort(list): if len(list) == 0: return [] pivot = list.pop() return qsort(filter(lambda x: x < pivot, list)) + [pivot] + qsort(filter(lambda x…

#!/usr/bin/env python # -*- coding: utf-8 -*- def qsort(list): if len(list) == 0: return [] pivot = list.pop() return qsort([x for x in list if x < pivot]) + [pivot] + qsort([x for x in list if x >= pivot]) def main(): test_list = [2, 5, 3…

-module(qsort). -export([qsort/1]). qsort([]) -> []; qsort([Pivot|T]) -> qsort([X || X <- T, X < Pivot]) ++ [Pivot] ++ qsort([X || X <- T, X >= Pivot]). リスト内包をつかったときに、どういった処理を内部的におこなっているのかがきになる。

分割した要素を結合するときにはすでにミクロな集合内ではソートされていることが保証されているため線形時間で結合できる。というかんじ。 // merge_sort.c #include "merge_sort.h" void merge_sort(int *array, size_t size) { int div = (int)size/2, *l…

クイックソートをC言語で書いてみたら思いのほか書けなくてびっくりした。。そしてへんこんだ。でもまあ、リハビリだと思いつつがんばる。あとあれ、マージソートとの違いは、分割前に並び替えちゃうのか、統治時に並び替えるのか、そこなのよね。 // qsort.…

うちの教授も訳に参加してた。で、まあmumumuさんにすすめられたからおもむろに研究室を探してみたところ２冊も見つかった。適当に借りてきた。 アルゴリズムC++作者: ロバートセジウィック,Robert Sedgewick,野下浩平,佐藤創,星守,田口東出版社/メーカー: …