진정한 프로그래머가 되길 꿈꾸며..

[자료구조] 병합정렬(merge sort)[자료구조] 병합정렬(merge sort)
병합 정렬은 여러 개의 정렬된 자료의 집합을 결합하여 한 개의 정렬된 집합으로 만드는 방법이다. 병합 정렬은 전체 원소들에 대해서 수행하지 않고 부분집합으로 분할하고 각 부분집합에 대해서 정렬 작업을 완성한 후에 정렬된 부분집합을 다시 결합하는 분할 정복 기법을 사용한다. 
 
 2개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법을 2-way 병합이라 하고, n개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법을 n-way 병합이라고 한다. 2-way 병합 정렬은 다음과 같은 작업을 반복 수행하면서 완성한다.

(1) 분할 : 입력 자료를 같은 크기의 부분집합 2개로 분할한다.

(2) 정복 ; 부분집합의 원소들을 정렬한다. 부분집합의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다.

(3) 결합 : 정렬된 부분집합들을 하나의 집합으로 통합한다.

병합 정렬은 각 단계에서 새로 병합하여 만든 부분집합을 저장할 공간이 추가로 필요하기 때문에 정렬할 원소 n개에 대해서 2xn개의 메모리 공간을 사용한다. n개의 원소를 분할하기 위해서 log₂n번의 단계를 수행하고, 부분집합의 원소를 비교하면서 병합하는 단계에서 최대 n번의 비교 연산을 수행하므로 전체 병합 정렬의 시간 복잡도는 O(nlog₂n )이 된다.

아래의 동영상을 보면 이해하기 쉬울 것이다.


[자료구조] 병합정렬(merge sort)[자료구조] 병합정렬(merge sort)

퀵 정렬(quick sort )은 정렬할 전체 원소에 대해서 정렬을 수행하지 않고 기준값을 중심으로 왼쪽 부분집합과 오른쪽 부분집합으로 분할한다. 왼쪽 부분 집합에는 기준값보다 작은 원소들을 이동시키고, 오른쪽 부분집합에는 기준값보다 큰 원소들을 이동시킨다.
 이 때 사용하는 기준값을 피봇(pivot)이라고 하는데, 일반적으로 전체 원소 중에서 가운데에 위치한 원소를 피봇으로 선택한다.
 퀵 정렬은 다음의 두 가지 기본 작업을 반복 수행하여 완성한다.

(1)분할(divide): 정렬할 자료들을 기준값을 중심으로 2개의 부분집합으로 분할 한다.

(2)정복(conquer) : 부분집합의 원소들 중에서 기준값보다 작은 원소들은 왼쪽 부분집합으로, 기준값보다 큰 원소들은 오른쪽 부분집합으로 정렬한다. 부분집합의 크기가 1 이하로 충분히 작지 않으면 순환 호출을 이용하여 다시 분할한다.

분할 작업을 순환적으로 반복하면서 피봇의 왼쪽 부분집합과 오른쪽 부분집합을 정렬하는 방법으로 전체 원소들을 정렬한다. 부분집합으로 분할하기 위해서는 L과 R을 사용한다. 왼쪽 끝에서 오른쪽으로 움직이면서 크기를 비교하여 피봇보다 크거나 같은 원소를 찾아 L로 표시하고, 오른쪽 끝에서 왼쪽으로 움직이면서 피봇보다 작은 원소를 찾아 R로 표시한 후에 두 원소를 서로 교환한다. L과 R이 만나면 피봇과 R의 원소를 서로 교환하여 피봇의 위치를 확정한다.
 피봇의 확정된 위치를 기준으로 만들어진 왼쪽 부분집합과 오른쪽 부분집합에 대해서 퀵 정렬을 순환적으로 반복 수행하는데, 부분집합의 크기가 1 이하가 되면 퀵정렬을 종료한다.

간단한 퀵정렬 소스 이다.

int partition(int a[], int begin, int end)
{
 int pivot, temp, L, R ;
 L = begin ;
 R = end ;
 pivot = (begin+end)/2 ;

 while(L<R)
 {
  while((a[L]<a[pivot]) && (L<R)) L++ ;
  while((a[R]>=a[pivot]) && (L<R)) R-- ;
  if(L<R)
  {
   temp = a[L] ;
   a[L] = a[R] ;
   a[R] = temp ;
  }
 }

 temp = a[pivot] ;
 a[pivot] = a[R] ;
 a[R] = temp ;

 return L ;  
}

void quickSort(int a[], int begin, int end)
{
 if(begin<end)
 {
  int p ;
  p = partition(a, begin, end) ;
  quickSort(a, begin, p-1) ;
  quickSort(a, p+1, end) ;
 }
}

그리고 아래의 동영상을 참고 하면 퀵정렬을 이해하기 좀더 쉬울것이다.

[자료구조] 정렬

정렬이란 순서 없이 배열되어 있는 자료들을 작은 것부터 큰 것 순서의 오름차

순이나 큰 것부터 작은 것 순서의 내림차순으로 재배열 하는 것이다. 할일을 순

서대로 정하는 것이나 가게에서 음식을 유통기한 순서대로 냉장고에 진열하는

것, 도서관에서 도서번호 순서대로 책들을 정리하는 것, 이름 순서로 기록되어

있는 전화번호부 등 일상 생활에서 정렬을 사용하고 있다.

자료를 정렬하는데 사용하는 기준이 되는 특정 값을 키라고 한다. 특정 이름이

라던지, 수치 등을 이용할 수 있는데 중복되는 값이 여서는 안된다.

정렬 방법은 실행하는 방법과 정렬이 수행되는 장소에 따라서 분류될 수 있다.


실행 방법에 따른 분류

정렬은 실행하는 방법에 따라 비교식 정렬과 분산식 정렬로 구분할 수가 있다.

비교식 정렬은 비교하고자 하는 각 키값들을 한번에 두개씩 비교하여 교환함으

로써 정렬을 실행하는 방식이다. 그리고 분산식 정렬은 키값을 기준으로 하여

자료를 여러 개의 부분집합으로 분해하고, 각 부분집합을 정렬함으로써 전체를
정렬하는 방식이다.


정렬 장소에 따른 분류

컴퓨터에서 수행되는 정렬은 컴퓨터 메모리 내부에서 정렬하는 내부정렬과 메

모리의 외부인 보조 기억 장치에서 정렬하는 외부 정렬로 분류할 수 있다.

[자료구조] 연결 자료구조를 이용한 큐의 구현..
순차 자료구조를 이용하여 구현한 큐에는 몇 가지 단점이 있다. 사용 크기가 제

한되어 큐의 길이를 마음대로 사용할 수 없고, 원소가 없을 때에도 항상 그 크

기를 유지하고 있어야 하므로 메모리도 낭비 된다는 점이다. 이와 같은 문제를

극복하기 위해 연결 자료구조를 이용하여 크기 제한이 없는 연결 큐(Linked

Queue)를 구현해 보자.

연결 큐에서 원소는 데이터 필드와 링크 필드를 가진 노드로 구성하며, 첫 번째
노드를 가리키는 front 포인터와 마지막 노드를 가리키는 rear 포인터를 사용한

다. 연결 큐의 초기 상태(공백 큐)는 front와 rear를 NULL 포인터로 설정하여 표

현한다.

다음은 간단히 구현한 소스 이다.

#include <stdio.h>
#include <malloc.h>

typedef struct QNode{
 char data ;
 struct QNode *link ;
} QNode;

typedef struct {
 QNode *front, *rear ;
} LQueueType ;

LQueueType* createLinkedQueue()
{
 LQueueType *LQ ;
 LQ = (LQueueType*)malloc(sizeof(LQueueType)) ;
 LQ->front = NULL ;
 LQ->rear = NULL ;

 return LQ ;
}

bool isEmpty(LQueueType* LQ)
{
 if(LQ->front == NULL)
 {
  printf("\n Linked Queue is empty! \n") ;
  return true ;
 }else
  return false ;
}

void enQueue(LQueueType* LQ, char item )
{
 QNode* newNode = (QNode*)malloc(sizeof(QNode)) ;
 newNode->data = item ;
 newNode->link = NULL ;

 if(LQ->front == NULL)
 {
  LQ->front = newNode ;
  LQ->rear = newNode ;
 }else
 {
  LQ->rear->link = newNode ;
  LQ->rear = newNode ;

 }
}

char deQueue(LQueueType* LQ)
{
 QNode* old = LQ->front ;
 char item ;

 if(isEmpty(LQ)) return 0 ;
 else
 {
  item = old->data ;
  LQ->front = LQ->front->link ;

  if(LQ->front == NULL )
   LQ->rear = NULL ;

  free(old) ;

  return item ;
 }
}

void printfLQ(LQueueType* LQ)
{
 QNode* temp = LQ->front ;
 printf("\n Linked Queue : [") ;

 while(temp){
  printf("%3c", temp->data) ;
  temp = temp->link ;
 }
 printf("]") ;
}

void main()
{
 LQueueType* LQ1 = createLinkedQueue() ;
 
 enQueue(LQ1, 'a') ;
 printfLQ(LQ1) ;

 enQueue(LQ1, 'b') ;
 printfLQ(LQ1) ;

 deQueue(LQ1) ;
 printfLQ(LQ1) ;

 enQueue(LQ1, 'c') ;
 printfLQ(LQ1) ;

 deQueue(LQ1) ;
 printfLQ(LQ1) ;

 deQueue(LQ1) ;
 printfLQ(LQ1) ;
}

[자료구조] 순차 자료구조를 이용한 큐의 구현.

1. 선형 큐

1차원 배열을 사용하는 순차 자료구조로 큐를 구현해보자. 이때 배열의 크기는

큐의 크기, 즉 큐에 저장할 수 있는 최대 원소 갯수가 된다. 그리고 배열에 저장

된 원소 중에서, 첫 번째 원소의 인덱스를 저장할 front 변수와 저장된 마지막

원소의 인덱스를 저장할 rear 변수를 사용한다. 초기 공백 큐의 상태는 front 변

수와 rear 변수의 값을 -1로 설정한다.

정리된 소스는 아래와 같다... ( 정말 간단히 구현만 했다. )

#include <stdio.h>
#include <stdlib.h>

#define Q_SIZE 100

char queue[Q_SIZE] ;

int front, rear ;

void enQueue( char item)
{
 if(rear == Q_SIZE -1 )
 {
  printf("\nQueue is full!\n" ) ;
  return ;
 }else
 {
  rear++ ;
  queue[rear] = item ;
 }
}

void deQueue()
{
 if( front == rear )
 {
  printf("\nQueue is empty!\n" ) ;
  return ;
 }else
 {
  front++ ;
 }
}

void printfQueue()
{
 printf("Queue : [") ;
 for(int i = front+1; i <= rear ; ++i )
  printf("%3c", queue[i]) ;

 printf(" ] \n") ;
}

void main()
{
 front = -1 ;
 rear = -1 ;

 enQueue('a') ;
 printfQueue() ;

 enQueue('b') ;
 printfQueue() ;

 deQueue() ;
 printfQueue() ;

 enQueue('c') ;
 printfQueue() ;

 deQueue() ;
 printfQueue() ;

 deQueue() ;
 printfQueue() ;
}

실행해 보면..

위와 같은 결과가 나온다...

하지만 위와 같은 소스는, 배열에 모든 정보가 꽉 찬 이후에는 동작을 하지 않

는다.. 바로 그 것을 해결하기 위해 나온 것이 원형 큐다..

2. 원형 큐

위의 선형 큐와 같은 경우는 rear가 배열의 마지막 위치에 있게 되면 큐에 빈자

리가 있는데도 포화 상태로 인식하고 삽입연산을 수행하지 않는다.

원형 큐는 선형 큐와 마찬가지로 1차원 배열을 사용하는데, 논리적으로 배열의

처음과 끝이 연결되어 있다고, 생각하는 것이다.

원형 큐에서는 초기 공백 상태일 때 front와 rear의 값이 0이 되고, 공백 상태와

포화 상태를 쉽게 구분하기 위해서 자리 하나를 항상 비워둔다. 원형 큐에서의

공백 상태는 front = rear 가 된다. rear가 앞으로 이동하면서 원소를 삽입하고,

front는 rear가 이동한 방향으로 따라가면서 원소를 삭제한다. 원형 큐에서는 배

열의 인덱스가 n-1 다음에 다시 0이 되어야 하므로 사용할 인덱스를 정하기 위

해서 나머지 연산자 mod를 사용한다.

원형 큐는 위의 소스를 바탕으로 직접 해보길 바란다.

[자료구조] 순차 자료구조를 이용한 큐의 구현.

이전 포스팅의 순차 자료구조를 이용한 스택은 구현하기는 쉽지만, 물리적으로
크기가 고정된 배열을 사용하기 때문에 스택의 크기를 변경하기가 어렵고 메모

리의 낭비가 생길 수 있다는 문제가 있다. 이러한 순차 자료구조의 문제는 연결
자료구조를 사용함으로써 해결할 수 있다.

연결 자료 구조 중에서 단순 연결 리스트를 이용하여 스택을 구현하면 스택의

원소는 연결리스트의 노드가 된다. 스택에 원소를 삽입할 때 마다 연결 리스트

에 노드를 하나씩 연결한다. 그리고 스택 원소의 순서는 연결 리스트 노드의 링

크를 사용하여 표현한다. 스택의 top을 표현하기 위해서 노드에 포인터 top을

사용한다. 스택의 초기 상태는 포인터 top을 NULL 포인터로 설정하여 표현한

다.

다음은 간단히 구현해본 연결 자료구조 스택 소스 이다...

#include <stdio.h>

typedef struct stackNode{

 int data ;
 struct stackNode *link ;

}stackNode ;

stackNode* top ;

void push(int Num)
{
 stackNode* temp = new stackNode ;
 temp->data = Num ;
 temp->link = top ;
 top = temp ;
}

int pop()
{
 int Num ;
 stackNode* temp = top ;

 if(top == NULL )
  return 0 ;
 else
 {
  Num = temp->data ;
  top = temp->link ;
  delete temp ;
  return Num ;
 }
}

void printStack()
{
 stackNode* p = top ;
 
 printf("STACK [") ;

 while(p)
 {
  printf(" %d ", p->data ) ;
  p = p->link ;
 }
 printf(" ] \n ") ;
}

void main()
{
 top = NULL ;
 
 printStack() ;

 push(1) ;

 printStack() ;

 push(2) ;

 printStack() ;

 push(3) ;

 printStack() ;

 pop() ;

 printStack() ;

 pop() ;

 printStack() ;

 pop() ;

 printStack() ;
}

순차 구조와 거의 비슷하지만, 각 함수별로 저장하는 방식만 조금 다를 뿐이

다... 그리고 할당된 메모리를 해제하는 부분이 값을 빼는 부분에만 있기 때문

에 값을 많이 넣고, 그냥 종료해버리면 메모리누수가 생길 것이다..

이 것은 조금만 고민하면 알 수 있는 것이니 소스를 조금씩 개인적으로 수정해

서 쓰길 바란다..

스택은 수차 자료구조인 1차원 배열을 이용하여 스택을 구현할 수 있다. 1차원

배열인 stack[n]을 사용할 때 n은 배열 크기로서 배열원소의 갯수를 나타내는

데, 이것이 스택의 크기다. 스택에 원소가 쌓이는 순서는 배열의 인덱스로 표현

한다. 따라서 스택의 첫 번째 원소는 stack[0]에 저장되고, 스택의 두 번째 원

소는 stack[1]에 저장되고, 스택의 i번째 원소는 stack[i-1]에 저장된다.

스택이 top을 표현하기 위해서 배열 stack의 마지막 원소의 인덱스를 변수 top

에 저장한다. 변수 top에 0부터 n-1까지의 인덱스를 저장하게 되므로 스택의 초

기 상태에는 -1을 저장한다..

아래는 간단히 구현한 스택의 소스 이다.

#include <stdio.h>

#define STACK_SIZE 100

int stack[STACK_SIZE] ;

int top = -1 ;

void push(int Num)
{
 if( top >= STACK_SIZE - 1)
  return ;
 else stack[++top] = Num ;
}

int pop()
{

 if( top == -1)
  return 0 ;
 else return stack[top--] ;
}

void printStack()
{
 printf("Stack [ ") ;
 
 for( int i = 0 ; i <= top ; ++i )
  printf("%d ", stack[i]) ;
 
 printf("] \n") ;

}

void main()
{
 printStack() ;

 push(1) ;

 printStack() ;

 push(2) ;

 printStack() ;

 push(3) ;

 printStack() ;

 pop() ;

 printStack() ;

 pop() ;

 printStack() ;

 pop() ;

 printStack() ;
}

정말 간단한 구조이기 때문에 그냥 스택이 이런거구나 하는데만 쓰면 된다..