アカウント名:
パスワード:
たまに、最前線で使われてる実践的なアルゴリズムである、と誤解してる人を見かけるけど、実際のところは「初学者にすぐに説明出来るぐらいに簡単な内では一応実用性があるやつ」ぐらいがせいぜい。
その簡単さ故に、そこで紹介されてる範囲ではクイックソートが最強、という構成の教科書が多いのが原因じゃないかと思うけど。あるいは、再帰呼び出しが必要になる分かりやすい例として重宝されているだけか。
ちゃんと、違うんだぞさっと説明出来るのがこの辺までなだけでこれは実用的じゃないからな、ときちんと注意する必要がある。
汎用ソートアルゴリズムで、クイックソートを時代遅れにするほど早い奴って、具体的にはどれの話?
>あるいは、再帰呼び出しが必要になる分かりやすい例として重宝されているだけか。知ったかぶりしても、こういう所でウソがバレる。
クイックソートでは再帰呼び出しは使わない。再帰呼び出しを使っても書けるだけ。必用なんてとんでもない。
C++のstd::sort()だとイントロソートか何か。今時の規格では「最悪時間計算量がO(n log n)の内部ソート」と定められているので少なくともクイックソートでは無理。
std::stable_sort()は「最悪時関計算量がO(n log n)の安定そーと」と規格で定められてるので、これもクイックソートは該当しない。JavaのSort()は安定ソートと規格で定められていて、同じく。マニュアルを見ると、それじゃなきゃダメって訳ではないけど、と前置きしてマージソートが例として挙げられてる。
PythonやRubyやJavascriptも最近では利便性のため安定ソ
イントロソートはクイックソートの亜種でしょ。
ソートアルゴリズムを性質で分類したら、全く別の枠に収まるぐらいに改良された亜種だけどね。
その亜種もC++みたいなスピード狂向けの言語でしか標準ライブラリに採用されない程度に人気が無い。なんでこんなに不安定なソートが不人気なのか知らないけど。
あとまあ、でかいデータを扱うソフトウェアほどスピード狂が実装する傾向にあるだろうし、その極北のデータベースなんかでは使われてるのかも知れないけど。そうなると、世界で最も大量のデータをソートしてるアルゴリズムは? の答えはその手の亜種かも知れない。
> なんでこんなに不安定なソートが不人気なのか知らないけど。???
不安定なソートを標準ライブラリに持っているプログラミング言語が少ない。
不安定・安定の違いは、安定なソートは必要の無いところを入れ替えない。不安定はそういう保証が無い。
例えば名前順に並んでいる成績表を成績順にソートしたときに、100点のやつが複数人居たとする。安定なソートアルゴリズムだと、100点のやつだけ抜き出すと、そこは名前の順のままになっている。不安定なソートアルゴリズムでソートすると、同点の連中の並び順が揃わない。そういう成績表をそのまま張り出すと不格好な結果になる。
不格好で済めば良いけど、オークションなんかで、入札金額
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
「毎々お世話になっております。仕様書を頂きたく。」「拝承」 -- ある会社の日常
クイックソートはオワコンなので問題無し (スコア:-1)
たまに、最前線で使われてる実践的なアルゴリズムである、と誤解してる人を見かけるけど、
実際のところは「初学者にすぐに説明出来るぐらいに簡単な内では一応実用性があるやつ」ぐらいがせいぜい。
その簡単さ故に、そこで紹介されてる範囲ではクイックソートが最強、という構成の教科書が多いのが原因じゃないかと思うけど。
あるいは、再帰呼び出しが必要になる分かりやすい例として重宝されているだけか。
ちゃんと、違うんだぞさっと説明出来るのがこの辺までなだけでこれは実用的じゃないからな、ときちんと注意する必要がある。
ウソばっか (スコア:1)
汎用ソートアルゴリズムで、クイックソートを時代遅れにするほど
早い奴って、具体的にはどれの話?
>あるいは、再帰呼び出しが必要になる分かりやすい例として重宝されているだけか。
知ったかぶりしても、こういう所でウソがバレる。
クイックソートでは再帰呼び出しは使わない。
再帰呼び出しを使っても書けるだけ。必用なんてとんでもない。
Re: (スコア:1)
C++のstd::sort()だとイントロソートか何か。
今時の規格では「最悪時間計算量がO(n log n)の内部ソート」と定められているので少なくともクイックソートでは無理。
std::stable_sort()は「最悪時関計算量がO(n log n)の安定そーと」と規格で定められてるので、これもクイックソートは該当しない。
JavaのSort()は安定ソートと規格で定められていて、同じく。
マニュアルを見ると、それじゃなきゃダメって訳ではないけど、と前置きしてマージソートが例として挙げられてる。
PythonやRubyやJavascriptも最近では利便性のため安定ソ
Re: (スコア:0)
イントロソートはクイックソートの亜種でしょ。
Re: (スコア:0)
ソートアルゴリズムを性質で分類したら、全く別の枠に収まるぐらいに改良された亜種だけどね。
その亜種もC++みたいなスピード狂向けの言語でしか標準ライブラリに採用されない程度に人気が無い。
なんでこんなに不安定なソートが不人気なのか知らないけど。
あとまあ、でかいデータを扱うソフトウェアほどスピード狂が実装する傾向にあるだろうし、
その極北のデータベースなんかでは使われてるのかも知れないけど。
そうなると、世界で最も大量のデータをソートしてるアルゴリズムは? の答えはその手の亜種かも知れない。
Re:ウソばっか (スコア:0)
> なんでこんなに不安定なソートが不人気なのか知らないけど。
???
Re: (スコア:0)
不安定なソートを標準ライブラリに持っているプログラミング言語が少ない。
不安定・安定の違いは、安定なソートは必要の無いところを入れ替えない。不安定はそういう保証が無い。
例えば名前順に並んでいる成績表を成績順にソートしたときに、100点のやつが複数人居たとする。安定なソートアルゴリズムだと、100点のやつだけ抜き出すと、そこは名前の順のままになっている。不安定なソートアルゴリズムでソートすると、同点の連中の並び順が揃わない。そういう成績表をそのまま張り出すと不格好な結果になる。
不格好で済めば良いけど、オークションなんかで、入札金額