[Algorithm] Selection sort, Insertion sort

Below is the feedback from the professor regarding the assignment.

- Allocating a 1,000,000 (4MB) local variable in a function other than main is a very bad practice/habit.
- Local variables are placed on the operating system's stack, and the stack has a size limit.
- If that function is called multiple times, the program will crash.
- For such large data, use global variables, put them in main, or use malloc/free.

I looked into it further after modifying the code.

Code Modification

//  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 Arguments
        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 Arguments > 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;
}

Memory Area

When we write code in a certain language and execute it after compilation, variables and functions are stored in the memory structure as shown above.

Data Area

The data area is where global variables and static variables are allocated. Variables allocated to this area are generally allocated when the program starts and are only removed from memory when the program terminates. In other words, variables allocated in the data area exist until the program terminates. This matches the characteristics of global and static variables.

Stack Area

The stack area is where local variables and parameters generated during function calls are stored. Variables allocated in this area have the characteristic of disappearing once the function call is completed. This is a characteristic that clearly differentiates it from other memory areas. Since the memory for variables allocated later is freed first, it aligns with the characteristics of a stack.

Heap Area

The heap area is a memory area managed by the programmer. In other words, it is an area where memory space is allocated and deallocated according to the programmer's needs. It is the memory area created through dynamic allocation.

※ The memory for statically allocated variables is created in either the data or stack area depending on the characteristics of the variable. Static allocation is done entirely at the compile-time stage. However, at the compile-time stage, only the size of the memory is generated, and the value of the variable is not stored. This is why the size of an array must be specified only as a constant. Storing the variable's value occurs at the run-time stage, and dynamic allocation is used when you want to create memory at the run-time stage.

This leads to a question...

What happens if the Heap and Stack become full?