ソート最適化の時間

私は2種類があります。の場合、sort1の要素数が1000のランダムベクトルは20.3を返し、sort2 5.4を返します。しかしソートされた配列のresoultsを取得しようとしているとき、toSortベクトルがすでにソートされている最善の状況では、resoultsはちょっと変わってしまいます。 sort1の場合は12.234、sort2の場合は0.0213です。 .. 10 000要素の場合、sort1は982.069、sort2は0.2です！ソート最適化の時間

私は、ベクトルがソートされているかどうかを比較するアサーションを持っています。私はWindows 7とWindows 8で最新のmingwを使用しています。i7-5700 HQとi5-6300Uの場合

これは実装がない、より良いものを作成するための練習です。私はすべて私のアイデアだから、std :: sortを使いたくない。

私の質問は：なぜ2番目のアルゴリズムは10 000要素で私の〜0時間を与えるのですか？

出典

2016-11-15 Filip Rynkowski

これは並べ替えアルゴリズムの練習用であると仮定しているか、['std :: sort']（http://en.cppreference.com/w/cpp/algorithm/sort）代わりに。 –

あなたの質問は何ですか？すでにソートされたベクトルの数がどう違うのですか？どのように最初の並べ替えを最適化するには？他に何か？ –

キャッシュ。 2番目のアルゴリズムは常に隣接する要素を比較しているため、L1（または少なくともL2）キャッシュで両方の要素を見つける可能性が非常に高くなります。詳細については、http://stackoverflow.com/q/11227809/771073を参照してください。 –

いずれの場合も、最初のものはn²の複雑さを持ちます。

ソートする場合には、あなたの第2のアルゴリズムは線形であるのに対し：

toSort[minElem] < toSort[minElem - 1]とtoSort[maxElem] > toSort[maxElem+1]は、あなたの内側のループブレークので、すぐに、常にfalseです。

出典

2016-11-15 08:52:49 Jarod42

答えて

関連する問題