[アルゴリズム] 選択ソート、挿入ソート

以下は、当該課題に対する教授からの指摘事項です。

- main関数以外の関数内で1,000,000個（4MB）のローカル変数を割り当てるのは非常に良くない方式・習慣である
- ローカル変数はオペレーティングシステムのスタックに入るが、スタックにはサイズ制限がある
- その関数が複数回呼び出されるとプログラムがクラッシュする
- そのように大きなものはグローバル変数にするか、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("引数を正しく入力してください (例. selection_sort hw1_input.txt 1000)\n");
        return;
    }

        // 正しい引数
        int i,j;
        int min,temp;
        FILE *file = fopen( argv[1], "r" ); // ファイルポインタを開く
        char number[11]; // ファイルObjを行ごとに読み取るための数値コンテナ
        int lineCounter=0; // 行チェック用
        int maxCount = atoi(argv[2]);
        while(fgets(number, sizeof(number), file)){
            if(lineCounter==maxCount){
                break;
            }
            tempArray[lineCounter] = atoi(number); // 整列されていない配列をintでセット
            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("実行時間 = %.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("引数を正しく入力してください (例. selection_sort hw1_input.txt 1000)\n");
        return;
    }

        // 正しい引数 > タスク実行 :)
        int i,j;
        int temp;
        FILE *file = fopen( argv[1], "r" ); // ファイルポインタを開く
        char number[11]; // ファイルObjを行ごとに読み取るための数値コンテナ
        int lineCounter=0; // 行チェック用
        int maxCount = atoi(argv[2]);
        while(fgets(number, sizeof(number), file)){
            if(lineCounter==maxCount){
                break;
            }
            tempArray[lineCounter] = atoi(number); // 整列されていない配列をintでセット
            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("実行時間 = %.1f ms\n", ((double)(end_time-start_time)) / CLOCKS_PER_SEC * 1000);

    return 0;
}

メモリ領域

私たちが特定の言語でコードを書いてコンパイルおよび実行すると、上記のようなメモリ構造に変数および関数が格納される。

データ領域 (Data Area)

データ領域は、グローバル変数とstatic変数が割り当てられる領域である。この領域に割り当てられる変数は一般的にプログラムの開始と同時に割り当てられ、プログラムが終了して初めてメモリから消滅する。つまり、データ領域に割り当てられた変数はプログラムが終了するまで存在し続けるという特徴を持つ。グローバル変数とstatic変数の特徴と一致する部分である。

スタック領域 (Stack Area)

スタック領域は、関数呼び出し時に生成されるローカル変数とパラメータが格納される領域である。この領域に割り当てられた変数は、関数呼び出しが完了すると消えるという特徴を持つ。これは他のメモリ領域とは明確に比較される特徴である。遅く割り当てられた変数のメモリが先に解除されるため、スタックの特徴と一致する。

ヒープ領域 (Heap Area)

ヒープ領域は、プログラマーが管理するメモリ領域である。つまり、プログラマーの必要に応じてメモリ空間が割り当ておよび消滅する領域である。動的割り当てによって生成されるメモリ領域である。

※ 静的に割り当てられる変数のメモリは、変数の特性によってデータまたはスタック領域に生成される。静的割り当てはコンパイル段階 (Compile-time) で全て行われる。ただし、コンパイル段階ではメモリのサイズを確保するだけで、変数の値は保存されない。このため、配列のサイズは定数でしか指定できないのである。変数値の保存はランタイム (Run-time) で行われ、ランタイム段階でメモリを生成しようとする際に使うのが動的割り当てである。

そうなると、ここで疑問が湧く...

ヒープとスタックがいっぱいになったらどうなるのだろうか？