読者です 読者をやめる 読者になる 読者になる

プチコンで遊ぼう! (はてなブログ版)

任天堂3DSのプチコンで遊ぼう! [twitter:@eida_s]

はてなダイアリーから移行しました。 はてなダイアリーのURLを開いても自動的にこちらにリダイレクトされますのでご了承ください。

140コムソート

プチコン

ソートアルゴリズムの一種である、コムソートをプチコンで実装してみました。
プチコンにはSORT命令およびRSORT命令があるので必要性は全くないのですが、アルゴリズムの勉強として実装したものです。

コムソートは1991年に開発された比較的新しいソートアルゴリズムです。
コムソートという名前の、コムは櫛(くし)のことです。これはソートする様子が櫛で梳くような動きとなるからだといわれています。
アルゴリズムの分類としては、最も原始的なソートアルゴリズムの一つである、バブルソートの改良版となります。
なので動作原理はバブルソートそのものです。
今回はSWAP命令を使うため、バブルソートの改良版であるコムソートを選んだわけです。
アルゴリズムについてはwikipediaの「コムソート」の項を参照してください。


140コムソート本体は、本当にソート部分しか実装していないので、本体の前側に配列の定義を、本体の後ろ側にソート後の配列の表示を行うコードを追加したのが以下です。
ツイートしたのは本体部分のコメントも外した部分となります。

140コムソートの使い方は、Nに配列の要素数を、A()にソート対象となる配列を定義しておき、140コムソートを呼び出すだけです。
処理後はA()はソートされた状態となっています。

'INITIALIZE ARRAY
CLEAR
N=9:DIM A(N)
FOR I=0TO N-1
A(I)=RND(10):?A(I);" ";
NEXT:?

'140COMBSORT
'A():Array  N:A Number Of Elements
@140COMBSORT
H=0OR N/1.3
FOR I=0TO 1FOR J=0TO N-H-1
IF A(J)>A(J+H)THEN SWAP A(J),A(J+H)I=0
NEXT:I=I*(H<2)H=0OR H/1.3+(H<2)NEXT

'DISPLAY ARRAY
FOR I=0TO N-1
?A(I);" ";
NEXT:?
END