- 再考—クイックソート、イントロソート in C/C++
- [[[ Median-of-3 Killer 系列 ]]] Musser によるイントロソートの原著(http://www3.interscience.wiley.com/journal/7328/abstract)によれば、Median-of-3 Killer 系列により、クイックソート内で3要素の中央値をピボットに選ぶ手続きの弱点を突いて、ソートコストを著しく増大させることができてしまう。 それを防ぐために、イントロソートでは再帰レベルに応じてヒープソートに移行させているわけであるが、一方、クイックソー
- ID=14, cdate=2010/07/23 19:29, mdate=2010/07/23 19:37, owner=taiji, tags=qsort, psort, sort, C, C++
- 再考—並列ソートと検索 in C/C++
- 前回 sort_r-20100723.tar.bz2(upfile:1279875329-sort_r-20100723.tar.bz2) とともに示したように、並列マージソートと並列イントロソートは極めてパフォーマンスが良好である事がわかった。但し、要素数が少ないとスレッド処理のオーバーヘッドが無視できないことから、詳細な調査を行った。 [[[ 並列マージソート、並列イントロソート ]]] * ##pmergesort_r## が C による並列マージソート(自作) * ##parallel_stable
- ID=13, cdate=2010/07/16 22:39, mdate=2010/07/23 17:59, owner=taiji, tags=psort, psort_r, psort_b, C, C++, Blocks, GCD