현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

연결리스트에서 정렬하기...

hurryon의 이미지
글쓴이: hurryon / 작성시간: 토, 2003/09/13 - 2:42오후

냠냠...오래간만에 자료구조 책을 열어 놓고 보고 있습니다만...역시 어렵네요. 아마도...머리가 영...

단순 연결리스트입니다. 단순 연결리스트로 만들어진 녀석들을 정렬하고 싶은데...잘 안되네요. 오름차순이든 내림차순이든 정렬해 보려고 하는데...아마도 응용력이 상당히 떨어지는 듯.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>

struct data
{
    int index;
    int number; 

    struct data *next;
};

typedef struct data link;
typedef link *node;

node head;

int get_random()
{
    unsigned char ran, mask, i;
    struct timeval now_time;

    ran = 0;

    for(i = 0 ; i < 1 ; i++)  
    {
        gettimeofday(&now_time, 0);

        mask = now_time.tv_usec / 2;
        mask <<= i;
        ran |= mask;
    }
    
    return(ran);
} 

void node_init()
{
    node tmp;
    int i;  

    printf("Function: %s Start!\n", __func__);

    for(i = 0; i < 10; i++)
    {
        tmp = (link *)malloc(sizeof(link));

        if(tmp == NULL)
        {
            fprintf(stdout, "Out of memory, node_init\n");
            exit(1);
        }

        else
        {
            tmp->index = i;
            tmp->number = get_random();

            printf("index: %2d number: %4d\n", tmp->index, tmp->number);

            tmp->next = head; 
            head = tmp;
        }
    }
}

void node_sort()
{
    node previous;
    node current;
    struct data *next;

    previous = NULL;
    current = head;

    printf("Function: %s Start!\n", __func__);

    while(current != NULL)
    {
        if(previous == NULL)
        {
            previous = current;
        }

        else
        {
            if(previous->number > current->number)
            {
                printf("%d %d\n", previous->number, current->number);

                next = current->next;
                previous->next = next;
                current->next = previous->next;

                current = current->next;
            }

            else
            {
                current = current->next;
            }
        }
    }

}

void node_print()
{
    node tmp;

    tmp = head;

    printf("Function: %s Start!\n", __func__);

    while(tmp != NULL)
    {
        printf("index: %2d number: %4d\n", tmp->index, tmp->number);

        tmp = tmp->next;
    }
}

int main()
{
    if((head = (link *)malloc(sizeof(link))) == NULL)
    {
        fprintf(stdout, "Out of memory\n");
        exit(1);
    }

    head = NULL;

    node_init();

    node_print();

    node_sort();

    node_print();

    return(0);
}

결과는 다음과 같이 나옵니다.

[hurryon@localhost ~/c/0909]$ ./simple_link 
Function: node_init Start!
index:  0 number:  114
index:  1 number:  236
index:  2 number:   88
index:  3 number:  193
index:  4 number:   42
index:  5 number:  146
index:  6 number:   12
index:  7 number:  119
index:  8 number:  224
index:  9 number:   72
Function: node_print Start!
index:  9 number:   72
index:  8 number:  224
index:  7 number:  119
index:  6 number:   12
index:  5 number:  146
index:  4 number:   42
index:  3 number:  193
index:  2 number:   88
index:  1 number:  236
index:  0 number:  114
Function: node_sort Start!
72 12
72 42
Function: node_print Start!
index:  9 number:   72
index:  3 number:  193
index:  2 number:   88
index:  1 number:  236
index:  0 number:  114
[hurryon@localhost ~/c/0909]$

으흠. 이중 연결리스트로 해결하는 방법을 원하는게 아닙니다. 흐.

Forums: 
프로그래밍 QnA
sliver의 이미지

글쓴이: sliver / 작성시간: 토, 2003/09/13 - 3:41오후

퀵소트를 이용해서 짜봤습니다.

node quicksort_helper(node h)
{
  node pivot = h;
  node left=NULL,right=NULL;
  if(pivot==NULL) return NULL;
  h = h->next;
  while(h!=NULL) {
    node *which_side;
    node tmp;
    if(h->number > pivot->number) which_side = &right;
    else which_side = &left;
    tmp = h;
    h = h->next;
    tmp->next = *which_side;
    *which_side = tmp;
  }
  left = quicksort_helper(left);
  right = quicksort_helper(right);
  pivot->next = right;
  if(left==NULL) h = pivot;
  else {
    h = left;
    while(left->next!=NULL) left = left->next;
    left->next = pivot;
  }
  return h;
}
    
void node_quicksort()
{
  head = quicksort_helper(head);
}

리스트 크기가 별로 크지 않다면 insertion sort도 괜찮을 것 같네요.

둘러보기