ソートアルゴリズム

こんばんは
最近アルゴリズムのソート分野を学習しています

そこで思ったのですが、添え字を利用したソートというのはダメなのでしょうか(計算量、正確性において)


手順としては
ソートしたいデータを一つずつ取り出して、取り出したデータを格納する配列の添字の箇所に代入していく。
全てのデータを代入し終えたら、データが代入されているところを出力して、ソート済みとする。

どうですか？天才ですか？

No.3 ベストアンサー 回答者： めぐみん_ 回答日時： 2018/06/09 21:42

No.2です、

お礼をみて。
検討すべき課題がまだまだありそうですね。

No.5 回答者： tknakamuri 回答日時： 2018/06/10 01:04

これは取りうる値が小さく限られる場合のソートで

オープンハッシュアルゴリズムの基本部分そのものですね。

一般的なソートには制約がきつくて使えませんが、用金を限れば
ポピュラーなアルゴリズムです。

No.4 回答者： kmee 回答日時： 2018/06/10 00:38

https://ja.wikipedia.org/wiki/%E3%83%90%E3%82%B1 …
https://ja.wikipedia.org/wiki/%E9%B3%A9%E3%81%AE …
https://ja.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0 …

残念ですが、既に知られた方法です。

No.2 回答者： めぐみん_ 回答日時： 2018/06/09 21:13

No.1です。

でもこれって、

・元の配列のサイズより要素数が大きくなる可能性がある
・負の数には対応できない
・そもそも配列：a 自体がIndexを用いた使い方に難点がある。『 a(n) 』で呼び出しても空の場合がある。

と言った感じでしょうか。

この回答へのお礼

ご回答有り難うございます

＞・元の配列のサイズより要素数が大きくなる可能性がある
はい、そう想定しています。メモリの無駄遣いですけどね

＞・負の数には対応できない
たしかに・・・。
でも、正の値を保持する配列a、負の値を保持する配列bを用意して、b→aの順に書き出していけば解決できると思います

＞・そもそも配列：a 自体がIndexを用いた使い方に難点がある。『 a(n) 』で呼び出しても空の場合がある。

あくまで新しい配列は途中経過であってソートが完了したデータではないです


さらに難点をあげるなら、元データが巨大な数値だった場合、配列が宣言できずオーバーフローになるので、桁数が制限されることですね

お礼日時：2018/06/09 21:30

No.1 回答者： めぐみん_ 回答日時： 2018/06/09 20:06

何番目のIndexに入れたら良いかってどうやって決めるのでしょう。

例えば元の配列のIndex：０の値を新しい配列のどこにいれるか？です。

この回答へのお礼

ご回答有り難うございます

取り出した値は、新しい配列の添え字の部分に入れます。

VBAでとりあえず、書いてみました。
（　ひとまず、元データの中の数値が重複しないことを前提としたコードですが、重複したケースも容易に実装できそうです　）

Sub sort()
Dim a(), tmp, Result
ReDim a(0)

'ソートしたい元データ
Dim num(): num = Array(2, 12, 90, 35, 18, 55, 7, 0)

'元データから数値を取り出し、新しい配列の添え字部分に代入
'数値が配列のサイズを超えている場合、内容を保持して再定義して配列を拡張
For Each tmp In num
If tmp > UBound(a) Then ReDim Preserve a(tmp)
a(tmp) = tmp
Next

'歯抜けデータ( "" )を取り除く
For Each tmp In a
If tmp <> "" Then Result = Result & "," & tmp
Next

Debug.Print Result
End Sub

お礼日時：2018/06/09 20:47