단순 연결리스트를 이용한 병합정렬

단순 연결리스트를 이용한 병합정렬

#include<stdio.h>

#include<stdlib.h>

#include<time.h>  

// node 구조체 정의

typedef struct _node node;

typedef node *pnode;

struct _node {

    int data;

    pnode next;

};

 

// 함수의 원형 

pnode SortedMerge(pnode a, pnode b);

void FrontBackSplit(pnode source, pnode *frontRef, pnode *backRef);

 

// 자료는 복사하지 않고 포인터만 바꾸어 주어서(원래 있던 노드를 그대로 사용)

// 정렬을 해 나가는 방법입니다 

void MergeSort(pnode *headRef) {

    pnode head = *headRef;

    pnode a;

    pnode b;

 

    // 길이가 0이나 1일경우는 그냥 반환합니다.

    if ((head == NULL) || (head->next == NULL)) {

        return;

    }

 

    // 주어진 리스트를 두부분 a, b 로 나눕니다.

    FrontBackSplit(head, &a, &b); 

 

    // 재귀적(순환적)으로 각각의 쪼개진 리스트를 정렬합니다.

    MergeSort(&a);

    MergeSort(&b);

 

    // 쪼개서 정렬한 두 리스트를 합쳐서 한개의 리스트로 만듭니다.

    *headRef = SortedMerge(a, b);

}

 

// 병합함수 - 자료를 복사하지 않고 포인터만 연결해주어서 병합합니다.

pnode SortedMerge(pnode  a, pnode b) {

    pnode result = NULL;

    pnode p;

 

    // 한쪽 리스트가 없다면 다른 쪽 리스트를 반환합니다.

    if (a == NULL) {

        return(b);

    } else if (b==NULL) {

        return(a);

    }

     

    // 작은 노드를 result 라고 합니다.

    if(a->data <= b->data) {

        result=a;

        a=a->next; // 연결한 쪽은 다음 노드로 이동합니다.

    } else {

        result=b;

        b=b->next; // 연결한 쪽은 다음 노드로 이동합니다.

    }

    // 병합을 하기 위한 포인터

    p=result; 

    // 양쪽이 모두다 있을 경우 선택을 계속합니다.

    while(a!=NULL && b!=NULL) {

    // a, b 중에서 작은 쪽을 선택합니다.

        if (a->data <= b->data) {

            p->next = a;  // 작은 쪽을 p->next에 연결합니다.

            a=a->next;    // 연결한 쪽은 다음 노드로 이동합니다.

            p=p->next;    // p를 다음 노드로 이동시킵니다.

        } else {

            p->next = b;  // 작은 쪽을 p->next에 연결합니다.

            b=b->next;    // 연결한 쪽은 다음 노드로 이동합니다.

            p=p->next;    // p를 다음 노드로 이동시킵니다.

        }

    }

    // 위의 while문을 탈출하였습니다.

    // a가 끝이 났던지, b가 끝이 났습니다.

    // 만약 a가 끝이 났다면, p->next에 b를 연결합니다.

    // 만약 b가 끝이 났다면, p->next에 a를 연결합니다.

    if(a==NULL) {

        p->next=b;

    } else {

        p->next=a;

    }

    // 결과리스트(시작하는 노드)를 반환합니다.   

    return(result);

}

 

// 보조함수

// 주어진 리스트를 길이가 같은 두 부분으로 나눕니다.

// 한칸씩 앞으로 이동하는 slow와 두칸씩 앞으로 이동하는 fast 포인터를 가지고

// fast가 끝에 닿으면 slow는 중간을 가리키게 됩니다.

// slow까지를 전반부, slow->next를 후반부로 쪼개는 것입니다.  

void FrontBackSplit(pnode source,

          pnode *frontRef, pnode *backRef) {

    pnode fast;

    pnode slow;

    if (source==NULL || source->next==NULL) {

        // length < 2 cases 

        *frontRef = source;

        *backRef = NULL;

    } else {

        slow = source;

        fast = source->next;

 

        // fast를 두칸, slow를 한칸씩 전진시킵니다. 

        while (fast != NULL) {

            fast = fast->next;

            if (fast != NULL) {

                slow = slow->next;

                fast = fast->next;

            }

        }

 

        // slow까지가 전반부이고, slow->next  부터가 후반부입니다.

        *frontRef = source;

        *backRef = slow->next;

        slow->next = NULL;

    }

}

 

// 주어진 연결리스트를 프린트하는 함수

// 일부만 샘플로 출력해 보았습니다. 

void printList(pnode node) {

    int i=0;

    while(node!=NULL) {

        if(i<1000 || i%10000==0)

            printf("%d ", node->data);

        i+=1;

        node = node->next;

    }

}

 

// 연결 리스트의 앞에 정수 데이터로 노드를 만들어서 삽입하는 함수 

void push(pnode *head_ref, int new_data) {

    // 노드를 만듬 

    pnode new_node = (pnode) malloc(sizeof(node));

  

    // 자료를 넣음 

    new_node->data  = new_data;

  

    // 기존의 리스트와 새노드를 연결해줌 

    new_node->next = (*head_ref);    

  

    // 헤더를 새노드로 이동시킴 

    (*head_ref)    = new_node;

} 

  

// 테스트를 위한 구동 프로그램

int main() {

    // Start with the empty list 

    pnode res = NULL;

    pnode a = NULL;

    int i, n=10000000, x, y, z;

  

    // 위의 n을 바꾸어주면 필요한 만큼의 난수를 만들수 있습니다.

    // 난수의 발생은 ms vc++ 의 15비트 난수를 확장해서 만들었습니다. 

    srand(time(NULL));

    for(i=0;i<n;i+=1) {

        x=rand(); y=rand(); z=(x<<15)|y;

        push(&a, z);

    }

    printList(a);

    // 위에서 만든 리스트를 병합정렬로 정렬합니다. 

    MergeSort(&a);

  

    printf("\n정렬된 리스트: \n");

    printList(a);           

  

    printf("\n끝이 났습니다.\n");

  

    return 0;

}