[演算法] 選擇排序 (Selection sort)、插入排序 (Insertion sort)

以下是教授針對此作業提出的指正事項：

- 在 main 以外的函式中配置 1,000,000 個（4MB）的區域變數是非常不好的方式/習慣。
- 區域變數會進入作業系統的堆疊（stack），而堆疊有大小限制。
- 若該函式被多次呼叫，程式將會崩潰。
- 像這樣的大型變數應設為全域變數、放在 main 中，或者使用 malloc/free 進行動態配置。

修正程式碼後，我又進一步了解了相關知識。

程式碼修正

//  studentID : A889056
//  selection_sort.c
//  Algorithm_Hongik
//
//  Created by GiPyeong Lee on 2015. 3. 3..
//  Copyright (c) 2015年 com.devsfolder.Hongik. All rights reserved.
//

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

int tempArray[1000001]={0,}; // 容器
void selection_sort(int argc, const char * argv[]){

    if ( argc <= 2 ) /* argc 應為 2，以便正確執行檔案並指定測試案例數量 */
    {
        printf("Please Input Correctly Arguments (eg. selection_sort hw1_input.txt 1000\n");
        return;
    }

        // 正確的參數
        int i,j;
        int min,temp;
        FILE *file = fopen( argv[1], "r" ); // 開啟檔案指標
        char number[11]; // 用於讀取檔案中逐行物件的數字容器
        int lineCounter=0; // 檢查行數
        int maxCount = atoi(argv[2]);
        while(fgets(number, sizeof(number), file)){
            if(lineCounter==maxCount){
                break;
            }
            tempArray[lineCounter] = atoi(number); // 設定整數未排序陣列
            lineCounter++;
        }
        fclose(file); // 關閉檔案指標

        for (i=0; i<maxCount; i++) {
            min = i; // 設定目前索引
            for (j=i+1; j<maxCount; j++) {
                if(tempArray[min]>tempArray[j]){
                    min = j;
                }
            }
            temp = tempArray[min];
            tempArray[min] = tempArray[i];
            tempArray[i]=temp;
        }
        for(i=0;i<maxCount;i++){
            printf("%d\n",tempArray[i]);
        }

}

int main(int argc, const char * argv[]) {
    // 在此插入程式碼...
    clock_t start_time, end_time; // 宣告時間變數
    start_time = clock(); // 開始時間
    selection_sort(argc,argv);
    end_time = clock(); // 結束時間
    printf("Running time = %.1f ms\n", ((double)(end_time-start_time)) / CLOCKS_PER_SEC * 1000);

    return 0;
}

//  studentID : A889056
//  insertion_sort.c
//  Algorithm_Hongik
//
//  Created by GiPyeong Lee on 2015. 3. 4..
//  Copyright (c) 2015年 com.devsfolder.Hongik. All rights reserved.
//

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int tempArray[1000001]={0,}; // 容器
void insertion_sort(int argc, const char * argv[]){
    if ( argc <= 2 ) /* argc 應為 2，以便正確執行檔案並指定測試案例數量 */
    {
        printf("Please Input Correctly Arguments (eg. selection_sort hw1_input.txt 1000\n");
        return;
    }

        // 正確的參數 > 執行任務 :)
        int i,j;
        int temp;
        FILE *file = fopen( argv[1], "r" ); // 開啟檔案指標
        char number[11]; // 用於讀取檔案中逐行物件的數字容器
        int lineCounter=0; // 檢查行數
        int maxCount = atoi(argv[2]);
        while(fgets(number, sizeof(number), file)){
            if(lineCounter==maxCount){
                break;
            }
            tempArray[lineCounter] = atoi(number); // 設定整數未排序陣列
            lineCounter++;
        }
        fclose(file); // 關閉檔案指標
        for (i=1; i<maxCount; i++) {
            temp = tempArray[i];
            j=i-1;
            while((temp<tempArray[j])&&(j>=0)){
                tempArray[j+1]=tempArray[j];
                j=j-1;
            }
            tempArray[j+1]=temp;
        }

        for(i=0;i<maxCount;i++){
            printf("%d\n",tempArray[i]);
        }

}

int main(int argc, const char * argv[]) {
    // 在此插入程式碼...
    clock_t start_time, end_time; // 宣告時間變數
    start_time = clock(); // 開始時間
    insertion_sort(argc,argv);
    end_time = clock(); // 結束時間
    printf("Running time = %.1f ms\n", ((double)(end_time-start_time)) / CLOCKS_PER_SEC * 1000);

    return 0;
}

記憶體區域

當我們使用特定語言編寫程式碼，經過編譯並執行時，變數與函式會儲存在如下的記憶體結構中。

資料區（Data Area）

資料區是分配全域變數與 static 變數的區域。在此區域分配的變數通常會在程式啟動時同步分配，並直到程式結束時才會從記憶體中清除。換句話說，資料區分配的變數具有會持續存在直到程式結束的特徵。這與全域變數與 static 變數的特性一致。

堆疊區（Stack Area）

堆疊區是儲存函式呼叫時所產生的區域變數與參數的區域。此區域分配的變數具有會在函式呼叫結束後消失的特性。這與其他記憶體區域有顯著的區別。後分配的變數記憶體會先被釋放，這與堆疊（Stack）的特性一致。

堆積區（Heap Area）

堆積區是由程式設計師管理的記憶體區域。也就是說，這是根據程式設計師的需求分配及銷毀記憶體空間的區域，是透過動態配置產生的記憶體區域。

※ 靜態分配變數的記憶體會根據變數的特性，在資料區或堆疊區中產生。靜態分配在編譯階段（Compile-time）即全部完成。然而，編譯階段只會產生記憶體大小，並不會儲存變數的值。這就是為什麼陣列大小必須指定為常數的原因。變數值的儲存是在執行階段（Run-time）完成的，而為了在執行階段產生記憶體所使用的技術即為動態配置。

這時產生了一個疑問...

如果 Heap 和 Stack 都滿了會發生什麼事呢？