[WP]no.006 クイックソート@hsp

HSPでクイックソート
スタック使わない方法って無かったっけ?無いか。

製作時間40分ぐらい

ランダムな数字の羅列など面白くないので、交換する度に画面の描画を行います。クッソ遅く感じます。
このプログラムのピボット選択が見事にバブルなので、そもそも交換する度に画面の描画を行うのが間違い。
マージソートの方が多分楽しい。

ピボット選択を修正すればさらに劇的に早くなりますが、C言語レベルで書く、表示しないなら大して変わらないはず。

#const N 80
#define swap(%1,%2) swapi=%1 : swapj=%2 : gosub *lswap // idx %1,%2を交換

randomize // 初期化
dim tarray,N
repeat N
tarray.cnt=rnd(460)+10
loop

dim stack,20,2 : stackp=0

// 全領域で初期化
low=0
high=n-1
repeat
if low==N-1 : break // lowが末尾に到達したなら終了
if (low==high){ // これ以上分割不能なら、一段戻る(stackからpop)
stackp--
low=stack.stackp.0
high=stack.stackp.1
continue
}

pivotd=tarray.((low+high)/2) // pivotを範囲内の真ん中の値とする(適当で構わない)
swap ((low+high)/2),low // pivot要素を先頭(low)に避難
idx=low
repeat high-low,low+1 // pivotより小さい値を左に、大きい値を右に移動させる
if (tarray.cnt < pivotd){
idx++
swap idx,cnt
}
loop
swap idx,low // 分かれ目にpivotを置く。
logmes strf("%d %d *%d",low,high,idx)
// pivot操作より左側のブロック、pivotより右側のブロックに分けることができた。
// 右側のブロックの範囲はスタックに積んでおき、左側のブロックの範囲を次で処理する。
stack.stackp.0=idx+1
stack.stackp.1=high
stackp++

high=idx
wait 1
loop
stop
*lswap
if (swapi==swapj) : return
t=tarray.swapi
tarray.swapi = tarray.swapj
tarray.swapj = t

redraw 0
hsvcolor ,,255 : boxf : color
repeat N
boxf cnt*640/N,470,(cnt+1)*640/N,470-tarray.cnt
loop
redraw 1
wait 8
return


swapの画面描画は省略ですよー。

「pivot操作より左側のブロック、pivotより右側のブロックに分けることができた。」とは次のようなイメージ

pivotより小さい pivot pivotより大きい
□□□□□□□□□□◇■■■■■■■■■■■■
low high

確定している事は
・pivotはここの位置で確定
・□は◇と◇より右側に移動することは無い。
・■は◇と◇より左側に移動することは無い。
つまり、□の範囲内と■の範囲内それぞれでもう一度ソートを行えばよい。典型的分割統治。

実行するとグラフィカルにソートの様子が映し出されますが、これらの意味が全く伝わってこない様子
スポンサーサイト

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

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

コメントの投稿

非公開コメント

プロフィール

舞葉(ぶよう)

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

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

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

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

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

この人とブロともになる

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

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