アカウント名:
パスワード:
たまに、最前線で使われてる実践的なアルゴリズムである、と誤解してる人を見かけるけど、実際のところは「初学者にすぐに説明出来るぐらいに簡単な内では一応実用性があるやつ」ぐらいがせいぜい。
その簡単さ故に、そこで紹介されてる範囲ではクイックソートが最強、という構成の教科書が多いのが原因じゃないかと思うけど。あるいは、再帰呼び出しが必要になる分かりやすい例として重宝されているだけか。
ちゃんと、違うんだぞさっと説明出来るのがこの辺までなだけでこれは実用的じゃないからな、ときちんと注意する必要がある。
汎用ソートアルゴリズムで、クイックソートを時代遅れにするほど早い奴って、具体的にはどれの話?
>あるいは、再帰呼び出しが必要になる分かりやすい例として重宝されているだけか。知ったかぶりしても、こういう所でウソがバレる。
クイックソートでは再帰呼び出しは使わない。再帰呼び出しを使っても書けるだけ。必用なんてとんでもない。
C++のstd::sort()だとイントロソートか何か。今時の規格では「最悪時間計算量がO(n log n)の内部ソート」と定められているので少なくともクイックソートでは無理。
std::stable_sort()は「最悪時関計算量がO(n log n)の安定そーと」と規格で定められてるので、これもクイックソートは該当しない。JavaのSort()は安定ソートと規格で定められていて、同じく。マニュアルを見ると、それじゃなきゃダメって訳ではないけど、と前置きしてマージソートが例として挙げられてる。
PythonやRubyやJavascriptも最近では利便性のため安定ソ
イントロソートはクイックソートの亜種でしょ。
ソートアルゴリズムを性質で分類したら、全く別の枠に収まるぐらいに改良された亜種だけどね。
その亜種もC++みたいなスピード狂向けの言語でしか標準ライブラリに採用されない程度に人気が無い。なんでこんなに不安定なソートが不人気なのか知らないけど。
あとまあ、でかいデータを扱うソフトウェアほどスピード狂が実装する傾向にあるだろうし、その極北のデータベースなんかでは使われてるのかも知れないけど。そうなると、世界で最も大量のデータをソートしてるアルゴリズムは? の答えはその手の亜種かも知れない。
条件を満たすまでは普通にクイックソートするアルゴリズムがクイックソートとは全く別の枠?しまいにゃスピード狂とか全く関係ないこと口走ってるし。そこは言語規格側でアルゴリズムまで明示してるかどうか程度の話だよ……
革新的進歩してると思ってたら案外して無かったってのが恥ずかしいのはわからんでもないが……
クイックソートは「最悪計算量がO(n^2)」の枠。イントロソートに改良すると「最悪時関計算量がO(n log n)」の枠。アルゴリズムのアイデアの系譜で分類しても実用的な意味はない。最終的に出来上がるアルゴリズムの性質が別物という話。
同じく、言語の規格ではアルゴリズムが明示されてはいない。そんなところを規格化したら、より良いアルゴリズムが見つかったら困るだろうにその関数やメソッドが満たす性質(安定か不安定か、最悪時関計算量がO(n log n)であるなど)が示されているだけ。その条件を満たすアルゴリズムがあれば、実装は何でも良い。
一般に、不安定なソートの方
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
海軍に入るくらいなら海賊になった方がいい -- Steven Paul Jobs
クイックソートはオワコンなので問題無し (スコア:-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)
クイックソートは「最悪計算量がO(n^2)」の枠。
イントロソートに改良すると「最悪時関計算量がO(n log n)」の枠。
アルゴリズムのアイデアの系譜で分類しても実用的な意味はない。
最終的に出来上がるアルゴリズムの性質が別物という話。
同じく、言語の規格ではアルゴリズムが明示されてはいない。
そんなところを規格化したら、より良いアルゴリズムが見つかったら困るだろうに
その関数やメソッドが満たす性質(安定か不安定か、最悪時関計算量がO(n log n)であるなど)が示されているだけ。
その条件を満たすアルゴリズムがあれば、実装は何でも良い。
一般に、不安定なソートの方