Algorithm - Sorting (Insertion Sort) 插入排序法

-

想法:

類似玩大老二在整理牌的時候

把所有牌分成已排序區和未排序區

初始假設第一張在已排序區

例如

在第一回合

把第二張拿來跟第一張比較

第二張如果小於第一張 => 第二張放在較小的位置

第二張如果大於第一張 => 第二張放在較大的位置

所以此時第一張和第二張的相對位置會是正確的

(第一二張位在已排序區，其他都是未排序區)

在第二回合

把第三張拿來跟已排序區的做比較

找到對的相對位置後插進去

所以此時這三張牌的相對位置會是正確的

以此類推


要注意一個地方

在插入的地方

要把插入的地方往後的地方(直到已排序區的尾巴)都往後移一格

記得要先移動最後面的值

如果從最前面開始移動

會把值一直往後覆寫


Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int *a, int *b);
void printarray(int size, int *data);
void generate_random_array(int size, int *data);


void bubblesort(int size, int *data);
void selectionsort(int size, int *data);
void insertionsort(int size, int *data);

void swap(int *a, int *b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void printarray(int size, int *data){
    printf("data: ");
    for(int i = 0; i < size; i++){
        printf("%d,", data[i]);
    }
    printf("\n");
}

void generate_random_array(int size, int *data){
    srand(time(NULL));
    for(int i = 0; i < size; i++){
        data[i] = rand()%1000;
    }    
}


#include <stdio.h>
#include <stdlib.h>
#include "Sort.h"

void insertionsort(int size, int *data){
    int i, j, k;
    int tmp;
    for(i = 1; i < size; i++){
        for(j = 0; j < i; j++){
            if(data[j] > data[i]){
                tmp = data[i];
                for(k = i-1; k >= j; k--){
                    data[k+1] = data[k];    
                }
                data[j] = tmp;
                break;
            }
        }
        printarray(size, data);
    }
}

void main(){

    int size = 10;
    int *data = (int*)malloc(sizeof(int) * size);

    //generate random array
    generate_random_array(size, data);
    printf("original:\n");
    printarray(size, data);

    //sorting
    printf("sorting:\n");
    insertionsort(size, data);

    //result
    printf("result:\n");
    printarray(size, data);
}


複雜度:

時間複雜度 O(n^2) 雙重迴圈 

(雖然迴圈看起來是三重，但最裡面那層是接續第二層迴圈繼續往下的意思，所以不會是尋訪三遍)

空間複雜度 O(1) 只需要一個額外的暫存空間

留言

張貼留言

這個網誌中的熱門文章

Formal Verification(正規驗證)介紹和如何使用 SVA(System Verilog Assertion) 做驗證

-
圖片
(零)前提: 關於 Formal Verification，其實我也還不是很理解，而且資源也不是那麼多，尤其很多都只是觀念性的介紹，甚至寫得很艱澀難懂落落長，但沒實質提到該怎麼做 Formal Verification。 但據說驗證在 IC 設計上又是非常重要的，所以雖然這部分真的不好理解，還是硬著頭皮收集資料寫下這一篇，所以這篇也不會寫到太深，畢竟這整個要講起來是很專業領域的。 因此這篇適用於對 Formal Verification 完全不理解的人，希望可以幫助你入門。 (一)正文: 當我們完成一塊電路時，要怎麼確定功能跟預期的結果是一樣的？ 1. 在軟體內跑 Waveform，比對預期結果和實際結果     (1) 有 GUI，淺顯易懂     (2) 新手友善 2. 寫 Testbench，比對預期結果和實際結果     (1) 許多參數要自己設定     (2) 需要下點功夫才能理解 上述方法都是把所有的 Case 會產生的結果用手寫出來，然後再用人眼去比對每個預期結果和實際結果是不是一樣。 但此時問題來了，但如果今天有上千個 Case，還是只能靠我們自己把這上千個 Case 列出來，然後一一用人眼比對嗎？ 此時 Formal Verification 的功用就出來了！ 簡單來說它就是把你 電路該有的行為列成正規化的公式 然後再用一個 檢查器去確認你的電路的行為總是會跟這個公式所描述的行為 是一樣的 這部分對於一個新手來說可能真的會很 Hardcore 不過會了之後真的會變得很方便！ Functional Verification 把所有 Testcase 列出來然後作驗證。 Formal Verification (二)實驗: 安裝: 首先要安裝好這些東西 yosys symbiyosys gtkwave yices sudo apt-get install autoconfig lubgmp3-dev (Ubuntu) sudo yum install autoconfig lubgmp3-dev (CentOS，不過沒實際試過，只是猜測應該是這樣) 以上東西要怎麼裝，Google 就可以查到了 我本身的環境是使用 CentOS7，在安裝過程中也碰到蠻多坑的 (雖然後來還是自...
閱讀完整內容

Quartus Qsys + Nios II 入門使用

-
環境設置 OS: Windows 10 Software: Intel Quartus Prime Lite 18.0 Platform: Cyclone V GT 5CGTFD9E5F35C7 ================================================= Nios II 簡介 Nios II 為 Altera 所設計的 32-bit RISC soft-core CPU 其完全在 Altera 的 FPGA 板子上實現 版本有分為 f/s/e e是最便宜最簡單的 也是下面的實驗我們會選擇的版本 ================================================= Platform Designer 簡介 簡單來說 他就是可以用 Intel 的 IP 定義你的系統的工具 IP 之間的連接 或是對應到的位址之類的 所以如果要設計一個只有由 Intel IP 所組成的系統 這是非常方便的工具 ================================================= 以下實驗基本上都是參照 helloworld：基於Qsys的第一個Nios II系統設計 來去完成 所以有些詳細的步驟不在贅述 請直接參考網站裡面寫的 下面只會大概提到該做什麼事情 以及遇到的問題和解決方式 ================================================= 實驗 - Platform Designer 這裡主要是要建立 硬體 系統 步驟 1. 在 Quartus 建立新的專案 2. 建立 bdf 檔案 3. 點  Tool > Platform Designer，進到  Platform Designer 頁面 在這裡主要要新增 4 個元件 Nios II (classic) Processor On-Chip Memory (RAM or ROM) Intel FPGA IP JTAG UART Intel FPGA IP System ID Peripheral Intel FPGA IP 然後將該連的線連起來 每個元件的 clk 都要接到時鐘的 clk_out 每個元件的 reset 都要接到時鐘的 reset Nios II (clas...
閱讀完整內容

Quartus Qsys + Nios II + SDRAM 進階使用

-
圖片
環境設置 OS: Windows 10 Software: Intel Quartus Prime Lite 18.0 Platform: Cyclone V GT 5CGTFD9E5F35C7 基本上跟  Quartus Qsys + Nios II 入門使用  的步驟一樣 只有 Platform Designer 部分需要更改 ============================================== 新增 DDR3 SDRAM Controller with UniPhy IP ============================================== PHY Setting 頁面設定 Speed Grade: 7 (配合板子) Memory clock frequency: 400 MHz PLL reference clock frequency: 100 MHz Memory Preset: MT41J64M16LA-15E ============================================== Memory Parameter 頁面設定 Total Interface Width: 8 Memory Initialization Option > Memory CAS latency setting: 8 Output drive strength setting: RZQ/4 ODT Rtt nominal value: RZQ/4 Memory Write CAS latency setting: 6 Dynamic ODT(RTT/WR) value: RZQ/4 ============================================== Memory Timing 和 Board Setting 保持不動  ============================================== Controller Setting 頁面設定 打勾 Generate power-of-2 data bus widths for Qsys or SOPC Builder Maximum Avalon-MM burst lenght: ...
閱讀完整內容