[WP]no.005 基数ソート+バケットソート@HSP

整数最速のソートアルゴリズム。多分。

製作時間30分
基数は10、4桁まで。

アルゴリズムの詳細はWikipediaへ。
ざっくりすると、「0~9」の数字が付いたバケットに配列内のデータを投げ込み、0から順に取り出してソートするイメージです。
これを桁単位で行う。投げ込む順番は保持する必要があるので、バケットはQueueなイメージ。

リスト(Queue)を使うのですが、hspでは配列しか扱えないのでメモリ消費は大きめ。


dim target,100 // ソート前
dim result,100 // ソート済み

dim bkt,101,10

// 乱数生成
randomize
repeat 100
target.cnt=rnd(10000)
loop

repeat 100
result.cnt=target.cnt
loop

l=1
repeat 4
// バケットに入れる
repeat 100
i=((result.cnt/l)\10)
logmes ""+i+" "+bkt.0.i
bkt.((bkt.0.i)+1).i=result.cnt
bkt.0.i++
loop
// バケットから出す
i=0
repeat 10
c=cnt
repeat bkt.0.c,1
result.i=bkt.cnt.c
i++
loop
bkt.0.c=0
loop
l=l*10
loop

text=""
repeat 100
text+=strf("%6d %6d\n",target.cnt,result.cnt)
loop
objmode 2
mesbox text,640,480,0
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

tag : HSP3 アルゴリズムとデータ構造

コメントの投稿

非公開コメント

プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
1253位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
219位
アクセスランキングを見る>>