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

#include<stdio.h>

#include<stdlib.h>

#include<time.h>  

// node 구조체 정의

typedef struct _node node;

typedef node *pnode;

struct _node {

    int data;

    pnode next;

};

void quick(pnode low, pnode high) {

    pnode p=low, q=NULL;

    // v 는 피봇값, low가 가리키는 노드의 값

    // 포인터 p는 피봇보다 작은 값들의 마지막 노드를 나타낸다.

    // 즉 p->next는 피봇보다 큰 값들의 시작되는 노드를 가리킨다.

    // q는 분할을 하기 위해서 피봇보다 작은 값들을 찾아가는 현재 노드를 가리킨다.

    // 피봇값보다 크지 않은 노드를 찾으면 p->next 노드의 값과 바꾸어 준다.

    // 그 후에 p는 p->next로 바뀌게 된다.

    int v, temp;

    // high포인터는 마지막 노드의 next 이다.

    // 만약 q가 high와 같다면 현재 노드는 low가 가리키는 노드 한개만 존재한다.

    // 따라서 아무일도 하지 않고 return을 한다.

    if(low==NULL || low==high || low->next==high) { return; }

    q=low->next;

    // v는 피봇값이다.

    v=low->data;

    // 피봇보다 크지 않은 값들을 찾아서 피봇보다 큰값들의 맨 앞의 값과 바꾸어 준다.

    while(q!=high) {

        // 피봇보다 크지 않은 값을 찾았다.

        if(q->data<=v) {

            // 만약 p->next와 q가 다르다면, 두 값을 바꾸어 준다.

            // 만약 p->next와 q가 같다면, 처음 v보다 크지 않은 값을 찾은 경우이고

            // 이때는 p가 p->next가 됨으로써 문제가 해결된다.

            // 물론 값을 서로 바꾸어 준 경우에도 p는 p->next가 되어야 한다.

            if(p->next!=q) {

                temp=q->data; q->data=p->next->data; p->next->data=temp;

            } 

            // 현재 p->next 가 가리키는 값이 피봇보다 크지 않은 값이 되었기 때문에

            // p는 p->next가 된다.

            p=p->next;

        }

        // q는 다음 노드를 가리킨다.

        q=q->next;

    }

    // 만약 low와 p가 같지 않다면 두 값을 서로 바꾸어 준다.

    if(low!=p) { temp=low->data; low->data=p->data; p->data=temp; }

    // 순환적으로 퀵정렬을 한다.

    quick(low, p); 

    quick(p->next, high); 

} 

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

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

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 linkedList = NULL;

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

  

    printf("정수: ");

    scanf("%d", &n); 

    srand(time(NULL));

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

        z=rand(); 

        push(&linkedList, z);

    }

    printList(linkedList);

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

    quick(linkedList, NULL);

  

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

    printList(linkedList);           

  

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

  

    return 0;

}