qnighy https://blog.hatena.ne.jp/qnighy/ 簡潔なQ https://qnighy.hatenablog.com/ Programming C glibcのqsortをターゲットに、クイックソートの最悪ケースO(n^2)を与えてみた。先日の記事の通り、glibcのqsortはマージソートだが、非常に大きいデータのときはクイックソートを利用するので、そのように仕向けてみた。実行した結果、約5億バイトの配列が確保され、ソートにかかった時間は以下のようになった。 マージソート(非アタック用データ)：37126ミリ秒 マージソート(アタック用データ)：46724ミリ秒 クイックソート(非アタック用データ)：39189ミリ秒 クイックソート(アタック用データ)：中断(507514ミリ秒以上) 明らかに最悪ケースである。環境は OS: Debia… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fqnighy.hatenablog.com%2Fentry%2F20090503%2F1241329233" title="qsortを撃墜し(最悪ケースを与え)てみた。 - 簡潔なQ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2009-05-03 14:40:33 rich https://qnighy.hatenablog.com/entry/20090503/1241329233 1.0 100%