コレクションの数値をSortで並び替える

質問

ご多忙中申し訳ありません。

Dim data As New List(Of Integer)で型指定した、dataの数値を単純に、下記のコードのようにdata.Sort() で並べ替えをしても綺麗に並べ替えが出来ますが、殆どのサイトでは、このような使い方をせず、IComparerインターフェイスを実装したクラスを使ったり、又はバブルソートなどを使って並べ替えをしていますが。
単純にdata.Sort() のような、並べ替えは問題があるのでしょうか、大変恐縮ですがご教示ください。

FormにButtonとListBoxを貼り付けました。

Dim data As New List(Of Integer) 'Integer型にする。
Private Sub f() Handles MyBase.Load
'データをaddする。
data.Add(235)
data.Add(4)
data.Add(567)
data.Add(53)
data.Add(56)
data.Add(87943)
data.Add(43)
data.Add(890)
data.Add(342)
data.Add(56)
data.Add(64)
data.Add(5)
data.Add(0)
ListBox1.Items.Clear()
End Sub
Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
Dim i As Integer
Dim dtcnt As Integer 'リストの数の変数。
dtcnt = data.Count 'リストの数を取得してループの回数に使う。
data.Sort() '並べ替え
For i = 0 To dtcnt - 1
ListBox1.Items.Add(data(i)) 'テストの結果をリストボックスに表示。
Next 'ListBox1には綺麗に並べ替えが完了して表示されています。
End Sub

何卒宜しくお願いします。

回答No.3

kmee · ベストアンサー

安定/安定でない が問題になるのは、次の場合です。
(1)並び順としては同順位になる、別の値が存在する。
#2の例で 2,11 2,12 等のようなものです
(2)ソート前の並び順に依存する処理が必要
#2の例の「1番目が同じだったら、最初に登場したものを使う」というようなものです

逆に言えば
・全て違う順位
・同順位のものは全て同じ値(入れ替わってもわからない)
・ソート前の並び順は関係無い処理しかしない
場合には、安定性は関係ありません。

> ＃リスト.Sort() がクイックソートで不安定の場合、項目が下記のように、1列の場合は、リスト.Sort() で並び替えをしても問題はないのでしょうか？

この場合
・「お礼」欄にあった例では、そもそも同順位のものが無い。
・「補足」欄にあった例では、並び順で同順位になるもの[1]は、すべて「1」という区別のつかない値。
なので、安定性は関係ありません。

> ＃リスト.Sort() とした場合は、なにやら「クイックソート」になるようなニュアンスで書かれていたよううですが、本当にそうなんでしょうか？

「このメソッドは、QuickSort アルゴリズムを使用する System.Array.Sort を使用します。」
とあるから、クイックソートでしょう。

> リスト.Sort() ←のリストの部分をIntegerで型指定した場合でも、やはりクイックソートになるのでしょうか？

List.SortでもList(of T).Sortでも「このメソッドは、QuickSort アルゴリズムを使用する System.Array.Sort を使用します。」とありますから、クイックソートでしょう。

お礼

たびたびのお返事有難うございました。

とてもわかりやすい説明でした。

まだまだ、わからないことだらけですので、これからも宜しくお願いします。

本当に有難う御座いました。

回答No.2

kmee

http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88
「安定」とはここにある意味です。
「並び換えができないことがある」という意味ではありません。

例えば
2,12
1,10
2,13
2,11
を1番目の要素だけで並び変えれば、2,12 2,13 2,11は全て「同じ値」になります。
この「同じ値」のものが、ソート前と同じ順番であることが保証されているのが「安定」です。この例で言えば「2,12 2,13 2,11」となることが保証されます。
「安定でない」というのは、この順番が保証されない、ということです。「2,11 2,12 2,13」になるかもしれないし「2,13 2,12 2,11」になるかもしれない、ということです。

やりたいことによっては、安定であることが求められます。
例えば、この例で「1番目が同じだったら、最初に登場したものを使う」という処理をしたければ、順番が変わる可能性のある「安定でない」ソートは使えません。

お礼

kmeeさんへ、再度のお返事有難う御座います。

「安定」、「不安定」の意味は、kmeeさんが例を示してくださったおかげで、「1番目の項目が間違った並び替えになる可能性がある」という、私の間違った考え方は訂正されました。

少し調べているうちに、またもや疑問点が生じてしまいました。
＃リスト.Sort() とした場合は、なにやら「クイックソート」になるようなニュアンスで書かれていたよううですが、本当にそうなんでしょうか？

＃kmeeさんが、教えてくださった。URLによると、クイックソートは「不安定」のようですが。（kmeeさんが、例で示してくださったようになる）
リスト.Sort() ←のリストの部分をIntegerで型指定した場合でも、やはりクイックソートになるのでしょうか？

＃リスト.Sort() がクイックソートで不安定の場合、項目が下記のように、1列の場合は、リスト.Sort() で並び替えをしても問題はないのでしょうか？
例
23
641
1
368
5
のように、単純な一列の数字の羅列です。

ご多忙中、何度もすいません。ご教示いただければ幸いです。

補足

「いろいろなソートアルゴリズム」
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/

ここのサイトにクイックソートの図解説明が載っていましたので、少しイメージしましたが、クイックソートの場合、下記のような、項目が一列の数値では問題がないように思えるのですが、間違っているでしょうか？
例
23
1
641
1
1
368
5
のように、単純な一列の数字の羅列です。
1が3箇所ありますが、どの位置の1かは、わからなくても構わないという前提です。

回答No.1

kmee

・単純な数値で無い場合など、「大小」関係が定義されていないので、引数無しのSortが使えない。
・大小関係を自分で定義したものにしたい。文字列を最初の4文字目を無視して並び換える、等
・Sortで使われているアルゴリズムがわからないので、確実に安定ソートをしたい場合は自分で用意する。
・Sortを使うと便利だが、ソートの原理が勉強できないので、使わない

あたりが考えられます。

お礼

早速のお返事有難う御座います。

＞単純な数値で無い場合など、「大小」～引数無しのSortが使えない。
この場合ですと、確かにSortには無理があります。

＞大小関係を自分で定義したものに～文字目を無視して並び換える
この場合もSortを使って並び替えすならば、
If CInt(data(l2).Substring(3, ｔｘｔ)) < CInt(data(l2 + 1).Substring(3, ｔｘｔ)) Then

こんな感じで、バブルソートしたほうが、早いですね。

＞Sortで使われているアルゴリズム～ソートをしたい場合は自分で用意
Sortは安定した結果は得られない、ということでしょうか？

＞Sortを使うと便利～勉強できないので、使わない
ごもっともなご意見だと思います、バブルソートなどは非常に簡単な原理ですけど、私のような無能な人間には、教えてもらわなければ、なかなか気がつきません。

わかりやすい、お返事有難うございました。