합병 정렬(Merge Sort)



합병 정렬? 

합병 정렬은 병합 정렬이라고도 불리며, 배열을 여러개로 분할해서 병합하면서 정렬하는 방법입니다.


특징

1) 메모리 내부에서 정렬하는 방법

2) 연결 리스트와 같은 순차적인 접근이 가능한 자료구조에 유일한 정렬 방법


어떠한 방법?

예제는 정렬할 배열과 임시로 담아놓을 배열 2개를 이용해서 정렬을 진행했습니다.


아래와 같은 배열이 있을 때



배열을 나눠서 정렬을 한 뒤 병합하면서 정렬을 진행합니다.




배열을 이용한 합병 정렬 예제


배열 출력 함수


void print_array(int array[], int size){
for(int i=0; i<size; i++){
printf("%-4d",array[i]);
}
printf("\n");
}

병합 정렬 함수


- size : 2씩 곱해지면서 정렬할 항의 수를 결정

- first, second : 하나의 배열을 두개처럼 사용하기위한 변수 각각 비교할 항 앞과 뒤를 가리킴

- i, j : 각각 비교할 앞의 항과 뒤의 항

- k : 임시로 담을 배열의 인덱스


void merge_sort(int a[], int n){
int i, j, k;
int first, second, size;
int *b;
b = (int*)malloc(sizeof(int)*n);
for(size = 1; size<n; size *=2){
first = -2 * size; // 초기 값
second = first + size;
while(second + size*2 < n){
first = second + size;
second = first + size;

i = k = first;
j = second;
while(i<first+size || (j<second+size && j<n)){
if(a[i]<=a[j]){
if(i<first + size)
b[k++] = a[i++];
else
b[k++] = a[j++];
}else{
if(j<second+size && j<n)
b[k++] = a[j++];
else
b[k++] = a[i++];
}
printf(" b[%d]=%d\t",k-1,b[k-1]);
}
printf("\n############################\n");
}
for(i=0; i<n; i++)
a[i] = b[i];
}
free(b);
}



메인 함수


void main(){
int array[] = {6,8,5,2,7,3,1,4};
int size = sizeof(array)/sizeof(int);
printf("########### Sorting before ###########\n");
print_array(array, size);
printf("######################################\n");
merge_sort(array, size);
printf("########### Sorting after ###########\n");
print_array(array, size);
}



실행 결과



참고 : C로 배우는 알고리즘 (이재규)

위키백과(합병 정렬)


관련 포스팅


[DataStructure] 기수 정렬(Radix Sort)

[DataStructure] 퀵 정렬(Quick Sort)

[DataStructure] 셸 정렬(Shell Sort)

[DataStructure] 버블 정렬(Bubble Sort)

[DataStructure] 삽입 정렬(Insertion Sort)

[DataStructure] 선택 정렬(Selection Sort)



'언어 > Data Strcuture' 카테고리의 다른 글

[C] 힙 정렬(Heap Sort)  (0) 2019.05.01
[C] 기수 정렬(Radix Sort)  (1) 2019.04.30
[C] 퀵 정렬(Quick Sort)  (0) 2019.04.24
[C] 셸 정렬(Shell Sort)  (2) 2019.04.23
[C] 버블 정렬(Bubble Sort)  (0) 2019.04.20

스택(Stack)


스택(Stack)?

스택은 LIFO(Last In First Out)구조로 


가장 나중에 들어간 값이 가장먼저 나오는 구조입니다.


삽입하는 PUSH와 삭제하는 POP 동작이 있습니다.


1. 스택 형태


2. PUSH


3. POP



배열을 이용한 예제


스택으로 사용할 int형 배열 선언 및 초기화 함수


#include "stdio.h"
#define MAX 10


int stack[MAX];
int top;


void init_stack(void){
top = -1;
}


스택에 push하는 함수


스택 크기보다 크면 오버플로우 발생


int push(int t){
if(top >=MAX-1){
printf("########### STACK OVER FLOW ###########\n");
return -1;
}else{
stack[++top] = t;
return t;
}
}


스택에서 pop하는 함수


스택 크기보다 작으면 오버플로우 발생


int pop(void){
if(top<0){
printf("########### STACK UNDER FLOW ###########\n");
return -1;
}
return stack[top--];
}

스택의 값을 출력하는 함수


void print_stack(void){
printf("PRINT STACK \n");
for(int i=top; i>=0; i--){
printf("%-6d",stack[i]);
}
printf("\n");
}

메인함수

11개의 값을 push할 경우 10개는 정상적으로 push 되지만,
나머지 1개의 값은 스택 오버플로우가 발생합니다.

두번째 pop을 수행할 때 5개의 값은 정상적으로 pop 되지만,
나머지 1개의 값은 스택 언더플로우가 발생합니다.

void main(){
init_stack();
printf("########### PUSH ###########\n");
for(int i=0; i<11; i++){
push(i);
}
print_stack();
printf("########### POP ###########\n");
for(int i=0; i<5; i++){
pop();
}
print_stack();
for(int i=0; i<6; i++){
pop();
}
}

실행 결과

참고 : C로 배우는 알고리즘 (이재규)






저작자표시 비영리

'언어 > Data Strcuture' 카테고리의 다른 글

[C] 삽입 정렬(Insertion Sort)  (0) 2019.04.19
[C] 선택 정렬(Selection Sort)  (0) 2019.04.19
[C] 트리(Tree)  (0) 2019.04.07
[C] 큐(Queue)  (2) 2019.04.01
[C] 연결리스트(LinkedList)  (0) 2019.03.28

연결리스트(LinkedList)



연결리스트(LinkedList)?

연결리스트는 동적인 자료구조로 배열처럼 메모리에 연속된 공간을 차지하지 않습니다.


1. 단순 연결리스트(Simple LinkedList)


노드와 다음링크를 가리키는 링크로 구성


처음 시작을 의미하는 head와 마지막 노드인 tail로 구성

2. 환형 연결리스트(Circular LinkedList)


가장 마지막 노드가 처음의 노드를 가리키는 연결리스트

3. 이중 연결리스트(Doubly LinkedList)


전, 후 노드를 가리키는 링크를 가지는 연결리스트


단순 연결리스트 예제


구조체 (key, value, 다음을 가리키는 링크로 구성) 선언


typedef struct _node
{
int key; // key
char *value; // value
struct _node *next; // 다음 노드의 위치
} node;
node *head, *tail; // head, tail


초기화 함수

head 와 tail 초기화


void init_list(void){
head = (node*)malloc(sizeof(node));
tail = (node*)malloc(sizeof(node));
head -> next = tail;
tail -> next = tail;
}

노드 삽입 함수
입력받은 노드의 다음에 삽입


node *insert_list(int key, char *value, node *t){
node *s;
s = (node*)malloc(sizeof(node));
s->key = key;
s->value = value;
s->next = t->next;
t->next = s;
return s;
}

노드 삭제 함수
입력받은 노드를 삭제

int delete_list(node *t){
node *s = head;
while(s->next != tail){
if(s->next==t){
s->next = t->next;
free(t);
break;
}else{
s = s->next;
}
}
}

노드 검색 함수
key를 이용해서 원하는 노드를 검색

node *find_node(int key){
node *s = head->next;
while(s != tail->next){
if(key == s->key){
break;
}else{
s = s->next;
}
}
return s;
}


전체 검색 함수

void findAll(){
node * t = head->next;
printf("#########findAll()########\n");
while(t != tail){
printf("find(%d) = %s , address = %d\n",t->key,find_node(t->key)->value,&t->next);
t = t->next;
}
printf("##########################\n");
}

메인 함수
노드 초기화 후 5개 데이터를 추가하고 2개의 데이터 삭제 후 전체 출력

void main(){
init_list();
insert_list(0,"apple",head);
insert_list(1,"banana",find_node(0));
insert_list(2,"melon",find_node(1));
insert_list(3,"grape",find_node(2));
insert_list(4,"pineapple",find_node(3));

delete_list(find_node(2));
delete_list(find_node(1));
findAll();
}

실행 결과


참고 : C로 배우는 알고리즘 (이재규)


관련 포스팅


[Data Strcuture] - 트리(Tree)

[Data Strcuture] - 큐(Queue)

[Data Strcuture] - 스택(Stack)

[Data Strcuture] - 연결리스트(LinkedList)




저작자표시 비영리

'언어 > Data Strcuture' 카테고리의 다른 글

[C] 삽입 정렬(Insertion Sort)  (0) 2019.04.19
[C] 선택 정렬(Selection Sort)  (0) 2019.04.19
[C] 트리(Tree)  (0) 2019.04.07
[C] 큐(Queue)  (2) 2019.04.01
[C] 스택(Stack)  (1) 2019.03.29

+ Recent posts

티스토리툴바