반응형




아래의 게시물과 같은 병합 정렬이지만 다른 코드를 소개하고자 한다.


아래 코드보다는 조금 더 길지만, 내용을 이해하기에는 더 편한 코드이다.


아래 그림은 소스코드의 내용 이해를 돕기 위해 제작하였다.








1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h>
#include <stdlib.h>
 
 
void MergeTwoArea(int arr[], int left, int mid, int right)
{
    int fIdx = left;
    int rIdx = mid + 1;
    int i;
    // 병합 결과를 담을 메모리 공간 할당
    int *sortArr = (int*)malloc(sizeof(int)*(right + 1));
    int sIdx = left;
 
 
    // 병합 할 두 영역의 데이터를 비교하여 
    // 배열 sortArr에 담는다.
    while (fIdx <= mid && rIdx <= right)
    {
        if (arr[fIdx] <= arr[rIdx])
            sortArr[sIdx] = arr[fIdx++];
 
        else
            sortArr[sIdx] = arr[rIdx++];
 
        sIdx++;
    }
 
    // 배열의 앞 부분이 sortArr로 모두 이동되어서 배열
    // 뒷부분에 남은 데이터를 모두 sortArr로 이동
    if (fIdx > mid)
    {
        for (i = rIdx; i <= right; i++, sIdx++)
            sortArr[sIdx] = arr[i];
    }
 
    // 배열 뒷부분이 sortArr로 모두 이동되어서 배열
    // 앞부분에 남은 데이터를 모두 sortArr로 이동
    else
    {
        for (i = fIdx; i <= mid; i++, sIdx++)
            sortArr[sIdx] = arr[i];
    }
 
    // malloc를 통해 정렬한 내용을 원래 배열에 넣는다.
    for (i = left; i <= right; i++)
        arr[i] = sortArr[i];
 
    // 메모리 할당 해제
    free(sortArr);
}
 
void MergeSort(int arr[], int left, int right)
{
    int mid;
 
    if (left < right)
    {
        // 중간 지점을 계산
        mid = (left + right) / 2;
 
        // 둘로 나눠서 각각을 정렬한다.
        MergeSort(arr, left, mid);    // left~mid에 위치한 데이터 정렬
        MergeSort(arr, mid + 1, right); // mid+1~right에 위치한 데이터 정렬
 
                                        // 정렬된 두 배열을 병합한다.
        MergeTwoArea(arr, left, mid, right);
    }
}
 
 
int main()
{
    int arr[10= { 2,3,5,6,1,8,6,9,0,};
 
    printf("정렬 전 ::");
    for (int i = 0; i <= 9; i++)
        printf("%d ", arr[i]);
 
    MergeSort(arr, 09);
 
    printf("\n정렬 후 ::");
    for (int i = 0; i <= 9; i++)
        printf("%d ", arr[i]);
 
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형

'Applied > 알고리즘' 카테고리의 다른 글

퀵 정렬(Quick Sort)  (0) 2016.10.02
다양한 알고리즘 그림으로 볼 수 있는 사이트  (0) 2016.09.22
병합 정렬(Merge Sort)  (0) 2016.08.30
버블 정렬(Bubble Sort)  (0) 2016.08.30
std sort 알고리즘  (0) 2016.08.22