週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Sedgewick, R., "Implementing Quicksort Programs," Comm. ACM, 21, 10 (1978) 847--857.を斜め読みしました。

Median-of-three partitioning reduces the number of comparisons by about 14 percent,

本家でもその程度でした。私の結果より少し数字がよくなっているのは、たぶん私の三項の選び方が適当だからだと思います。適当というのは3つ同じものを選ぶ可能性があるとか。

あと、この論文だと、先頭、最後尾、真ん中の三つの要素から三項メジアンを取っています。さらに、三項メジアンをとらない場合、ピボットは先頭の値を採用しています。 私の認識だとこれはまずいです。ピボット選択にはまじめに乱数を用いないと、O(N2)になるはまりケースを作ることが可能になるので。 このケースだと(1,2,...,N, N,N-1,...,1)みたいな、中央が最大、両端が最小となる入力で、O(N2)にできるはずです。

そもそも、1978年にrandomized algorithmの研究はすでになされてたんでしょうか。Rabin-Miller素数判定法が1978年なのを考えるとまだあまり深い研究はなされていなかったのかもしれません。誰か詳しい人いらっしゃいませんか。

スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/246-5c58b7dc
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。