[算法] 选择排序 (Selection sort), 插入排序 (Insertion sort)

以下是针对该作业教授的指点意见。

- 在 main 以外的其他函数内分配 1000000 大小的（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,}; // Container
void selection_sort(int argc, const char * argv[]){

    if ( argc <= 2 ) /* argc should be 2 for correct execution for file and how many testcase */
    {
        printf("Please Input Correctly Arguments (eg. selection_sort hw1_input.txt 1000\n");
        return;
    }

        // Correct Alguments
        int i,j;
        int min,temp;
        FILE *file = fopen( argv[1], "r" ); // open file pointer
        char number[11]; // number container for reading line by line in file Obj
        int lineCounter=0; // this is check line
        int maxCount = atoi(argv[2]);
        while(fgets(number, sizeof(number), file)){
            if(lineCounter==maxCount){
                break;
            }
            tempArray[lineCounter] = atoi(number); // set int unordered array
            lineCounter++;
        }
        fclose(file); // close file pointer

        for (i=0; i<maxCount; i++) {
            min = i; // set current Index
            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[]) {
    // insert code here...
    clock_t start_time, end_time; // Time Variable Declare
    start_time = clock(); // Time to start
    selection_sort(argc,argv);
    end_time = clock(); // Time to end
    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,}; // Container
void insertion_sort(int argc, const char * argv[]){
    if ( argc <= 2 ) /* argc should be 2 for correct execution for file and how many testcase */
    {
        printf("Please Input Correctly Arguments (eg. selection_sort hw1_input.txt 1000\n");
        return;
    }

        // Correct Alguments > Do Task :)
        int i,j;
        int temp;
        FILE *file = fopen( argv[1], "r" ); // open file pointer
        char number[11]; // number container for reading line by line in file Obj
        int lineCounter=0; // this is check line
        int maxCount = atoi(argv[2]);
        while(fgets(number, sizeof(number), file)){
            if(lineCounter==maxCount){
                break;
            }
            tempArray[lineCounter] = atoi(number); // set int unordered array
            lineCounter++;
        }
        fclose(file); // close file pointer
        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[]) {
    // insert code here...
    clock_t start_time, end_time; // Time Variable Declare
    start_time = clock(); // Time to start
    insertion_sort(argc,argv);
    end_time = clock(); // Time to end
    printf("Running time = %.1f ms\n", ((double)(end_time-start_time)) / CLOCKS_PER_SEC * 1000);

    return 0;
}

内存区域

当我们用某种语言编写代码、编译并运行程序时，变量和函数会存储在如下的内存结构中。

数据区 (Data Area)

数据区是分配全局变量和静态 (static) 变量的区域。分配在该区域的变量通常在程序开始时分配，只有在程序结束时才从内存中消失。也就是说，分配在数据区的变量具有持续存在直到程序结束的特性。这部分与全局变量和静态变量的特性相吻合。

栈区 (Stack Area)

栈区是存储函数调用时创建的局部变量和参数的区域。该区域分配的变量具有在函数调用完成后消失的特性。这与其他内存区域有明显的区别。由于后分配的变量内存先被释放，这与栈的特性相一致。

堆区 (Heap Area)

堆区是程序员管理的内存区域。也就是说，这是根据程序员的需要进行内存空间分配和销毁的区域。它是通过动态分配创建的内存区域。

※ 静态分配的变量内存根据变量的特性生成在数据区或栈区。静态分配全部在编译阶段 (Compile-time) 完成。但是，编译阶段只是生成内存大小，并不存储变量的值。这就是为什么数组大小必须指定为常量的原因。变量值的存储在运行时 (Run-time) 进行，在运行时阶段想要创建内存时所使用的就是动态分配。

那么，这里产生了一个疑问……

如果堆 (Heap) 和栈 (Stack) 都满了会怎样？