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