iT邦幫忙

2018 iT 邦幫忙鐵人賽
DAY 21
2
自我挑戰組

Verilog 從放棄到有趣系列 第 21

[Day21]插入排序法

今天一樣再來介紹一個排序,叫做插入排序法(Insert Sort).不知道昨天介紹完泡沫排序之後,大家在電路的部分對排序法有沒有更多的想法,今天來談談如何做出跟想像中不一樣的插入排序,首先一樣先來看一下插入排序的Pseudocode

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

當要插入一個新的元素時,就要去找到適合自己的位置,如果換成用電路做的話該怎麼去平行化呢?

首先,假設有n個元素,就創一組n+1個的bit array跟放n個元素的register array,

https://ithelp.ithome.com.tw/upload/images/20180101/20107543fw4f5aX3yC.png

用一個例子說明,假設原本就放了排序好的四個元素,這時候要插入一個4,bitarray會從1開始更新到n,比原本array的值還大就填1,小於等於填0,bitarray最左邊永遠填1,

https://ithelp.ithome.com.tw/upload/images/20180101/20107543YYKsvKqRpe.png

接下來開始找2’b10的位置,像上圖標記為綠色的地方,然後把四插入進去,剩下的往後面娜一個位置,接下在插入0的數字,一樣先更新bit array的值,然後找出2’b10的位置,把值插進去,剩下的值往後挪,如下圖.

https://ithelp.ithome.com.tw/upload/images/20180101/20107543EsOKvDiSI4.png

最後就完成拉!!

https://ithelp.ithome.com.tw/upload/images/20180101/20107543gatAksS05k.png

看到這裡應該就可以開始動手做做看囉.

Insert sort Verilog code:

reg [6:0]bit_array;
reg [2:0]insert_array[5:0];

always@(*)begin
  if(rst)begin
  for(i=0;i<6;i=i+1)
    bit_array[i] = 0;
  bit_array[6] = 1;
end
else if(in_valid)begin
  for(i=0;i<6;i=i+1)
    bit_array[i] = (data_in > insert_array[i]) ? 1 : 0;		  
end
else begin
  for(i=0;i<6;i=i+1)
    bit_array[i] = 0;
  bit_array[6] = 1;
end
end

always@(posedge clk)begin
  if(in_valid)begin
  for(i=6;i>1;i=i-1)begin
    insert_array[i-1] <= (bit_array[i-:2]==2'b10) ? data_in : 
								 (bit_array[i-:2]==2'b11) ? insert_array[i-1] : insert_array[i];		
  end
end
end 

always@(posedge clk)begin
  if(in_valid)
  out_valid <= 1;
else
  out_valid <= 0;
end

https://ithelp.ithome.com.tw/upload/images/20180101/20107543kWbPQskTiq.jpg

跑模擬時,我把全部array設為最大值,insert順序為1 5 3 6 4 0,模擬結果可以參考上圖.


上一篇
[Day20]泡沫排序法
下一篇
[Day22]BCD計數器
系列文
Verilog 從放棄到有趣30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言