[자료구조] inserting sort 문제 REVIEW

 

 

우선 구조체와 포인터를 선언해 준다.

 

 

typedef struct record{
    int key;
    char *name;
    int grade;
}record;

typedef record *point;

 

record 구조체의 포인터 변수를 point로 두었다.

 

 

 

중요한 건 insert 함수 구현이니, main 함수는 먼저 바로 살펴보겠다.

 

int main()
{
    int n;

    FILE *f=fopen("in.txt","r");

    point arr[10];

    fscanf(f,"%d",&n);

    for(int i=0;i<n;i++)
    {
        arr[i]=(point)malloc(sizeof(record));
        arr[i]->name=(char *)malloc(sizeof(char)*6);
    }

    int x=0;
    int y=0;
    char name[6];

    for(int i=0;i<n;i++)
    {
        fscanf(f,"%d %s %d",&x,name,&y);
        arr[i]->key=x;
        strcpy(arr[i]->name,name);
        arr[i]->grade=y;
    }

    for(int i=1;i<n;i++)
    {
        point temp=arr[i];
        insert(temp,arr,i-1);
    }

    
    for(int i=0;i<n;i++)
    {
        printf("%d %s %d\n",arr[i]->key,arr[i]->name,arr[i]->grade);
    }

    for(int i=0;i<n;i++)
    {
        free(arr[i]->name);
        free(arr[i]);
    }

    fclose(f);
}

 

 

다른 부분들은 문제의 제시대로 입력값을 받고, 출력을 하고, free 시키는 등 어렵지 않게 수행할 수 있는 부분이지만, 

 

 

    for(int i=1;i<n;i++)
    {
        point temp=arr[i];
        insert(temp,arr,i-1);
    }

 

 

이 코드를 주목해 보자. 우리는 arr 배열을 key 값 순서대로 오름차순 정렬이 되도록 각 요소들을 insert 시켜 주어야 한다. 따라서 temp 변수를 두고 insert 함수를 호출하였는데, 바로 insert 함수와 연계하여 살펴보겠다.

 

void insert(point temp,point arr[10],int n)
{

        while(n>=0&&temp->key<arr[n]->key)
        {
            arr[n+1]=arr[n];
            n--;
        }
    arr[n+1]=temp;
}

 

 

헷갈릴 때는 대입을 해서 직접 가장 첫 요소부터 진행해 보자. i=1일 때, insert(temp,arr,0)을 호출할 것이다 (temp=arr[1])

insert 함수에서는 arr[0]과 arr[1] key의 크기 순서에 알맞게 정렬이 된 채로 끝나게 되고, 그 다음부터 insert(temp,arr,1)(temp=arr[2]) 의 경우는 temp를 자신의 앞에 있는 arr[0],arr[1]과 비교하여 자신에게 맞는 위치에 배치되고, ... 반복이다.

 

 

while 문 속의 arr[n+1]=arr[n]은, insert를 진행할 때 해당 요소부터 뒤로 이어지는 모든 요소를 한 칸씩 뒤로 당겨야 하기 때문에 쓰였다.

 

---

 

 

 

이 문제에서 중요한 것은 insert 함수와 해당 함수를 호출할 때 index를 주의해야 한다는 것이다. 특히 insert 함수 내에서는 n>=0 조건을 잊지 말자.