言語/verilog/Tips/配列をソートする(クイックソート) - MoriLab.

配列をソートする(クイックソート)

概要

クイックソートのサンプルです。
アレイサイズ等、可変への対応を特にしていません。
実際に使用する場合はもうすこし作りこむ必要あり。

• taskのautomaticについて

これがないと、再帰呼び出しが正常にうごきません。
C言語などは、関数は呼ばれるたびにローカル変数を別に生成しますが、verilogは標準だとそうではありません。
実体は１つ、というイメージでしょうか。ハードウェア言語らしいといえばらしいですが・・・
automaticをつけることで、呼ばれるたびに実体を生成するようになる模様。

動作確認

ツール	バージョン	結果
ncverilog	06.11-s004	OK
VCS-MX		未確認
ModelSim		未確認

テストコード

28個のデータに乱数を入れたのち、ソートします。

reg [15:0] array [0:27];
  integer i;
  integer x;
 
  initial begin
    x=0;
    repeat(100)begin
      for(i=0;i<=27;i=i+1)begin
        array[i] = $random;
      end
      qsort(0,27);
    end
  end
 

ソースコード

task automatic qsort;
    input integer p_start;
    input integer p_end;
    reg [15:0] thr_val;
    integer    thr_p;
    integer    pi;
    integer    pj;
    integer    x;
  begin
    x=x+1;
    if(!(p_start>=p_end || p_start<0 || p_end<0 || p_start>27 || p_end>27))begin
      thr_val = array[p_start];
      pi      = p_start;
      pj      = p_end;
      while(pi<pj)begin
        while(array[pj]>=thr_val && pi<pj)begin
          pj=pj-1;
        end
        array[pi]=array[pj];
        while(array[pi]<=thr_val && pi<pj)begin
          pi=pi+1;
        end
        array[pj]=array[pi];
      end
      array[pi]=thr_val;
      if(p_start<p_end)begin
        qsort(p_start,pi-1 );
        qsort(pi+1   ,p_end);
      end
    end
  end
endtask
 

---