왕초보의 알고리즘 정렬 종류 파헤치기 3 (병합정렬, 힙정렬, 퀵정렬 / 코드 구현 C언어)

 

시작하기 전에 이전 포스팅을 먼저 보고 오시는 것을 추천드립니다. (●'◡'●)

왕초보의 알고리즘 정렬 종류 파헤치기 1 (자료구조, 시간 공간 복잡도)

왕초보의 알고리즘 정렬 종류 파헤치기 2 (버블정렬, 삽입정렬, 선택정렬 / 코드 예제 C)

---

4. 병합정렬 (Merge sort)

지금부터 정말 흥미로운 함수들이 나온다. 

합병 정렬 또는 병합 정렬(영어: merge sort 머지 소트[*])은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945년에 개발했다. [1] 상향식 합병 정렬에 대한 자세한 설명과 분석은 1948년 초 헤르만 골드스타인과 폰 노이만의 보고서에 등장하였다. [2]

 

그림으로 확 이해가 되쥬?

흔히 쓰이는 하향식 2-way 병합 정렬은 다음과 같이 작동한다.

1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
5. 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다.

점점 똑똑해 진다 ㅠㅠ

그럼 코드로 확인해 보자.

#include <stdio.h>

void merge_sort(int *arr, int start, int end);
void merge(int *arr, int start, int mid, int end);

int main(void)
{
	int arr[7] = { 7, 2, 0, 1, 5, 6, 4 };
	int i;
 
	merge_sort(arr, 0, 6); //병합정렬로 들어간다.
 
    i = 0;
    while(i < 7)
        printf("%d\n", arr[i++]);
}

void merge_sort(int *arr, int start, int end)
{
	int mid;

	if(start < end)
	{
    	//리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
		mid = (start + end) / 2; 
        //분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
		merge_sort(arr, start, mid); //반을 잘라 앞부분
		merge_sort(arr, mid + 1, end); //반을 잘라 뒷부분
		merge(arr, start, mid, end);
	}
}

//정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
void merge(int *arr, int start, int mid, int end) 
{
	int sorted[7];
    int sorted_i;
	int i;
	int j;
	
 
    sorted_i = 0;
    i = start;
    j = mid + 1;
     /*결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 
    이때 정렬 결과가 임시배열에 저장된다.*/
	while(i <= mid && j <= end)
	{
		if(arr[i] <= arr[j])
			sorted[sorted_i++] = arr[i++]; 
		else
			sorted[sorted_i++] = arr[j++];
	}
	while(i <= mid)
		sorted[sorted_i++] = arr[i++];
	while(j <= end)
		sorted[sorted_i++] = arr[j++];
	sorted_i--;
    //복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다.
	while(sorted_i >= 0)
	{
		arr[start + sorted_i] = sorted[sorted_i];
		sorted_i--;
	}
}

$ ./a.out
0
1
2
4
5
6
7

---

 

5. 힙정렬 (heap sort)

힙 정렬(Heap sort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최소 힙을 구성하고 오름차순 정렬을 위해서는 최대 힙을 구성하면 된다.

힙정렬의 과정을 이미지화 해놨다!

과정은 아래와 같이 작동한다.

1. n개의 노드에 대한 완전 이진트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다. (이진트리는 각 부모가 자식을 2개씩만 가질 수 있는 것을 말한다!)
2. 최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.
3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.
4. 2와 3을 반복한다.

이렇게만 보면 뭔 소린지 당최 모르겠다. 일단 이 정렬을 이해하려면 <트리>가 무엇인지 이해해야 한다.

트리는 나무를 위아래로 뒤집어 놨다고 생각해 보자.

힙 정렬에서 사용할 이진트리는 한 부모에서 2 자식(?)씩 뻗어내려 간다. 힙 정렬을 알기 위해서는 힙 상태라는 것부터 알아야 한다. 힙 상태라는 것은 부모 노드가 자식노드보다 큰 숫자를 가지고 있다는 의미이다. 간단하게 말해서 힙정렬은 아래와 같이 설명할 수 있다.

 

1. 힙 상태로 바꿔준다.

2. 그리고 오름차순으로 정렬한다. 

3. 힙 상태로 바꿔준다.

2. 그리고 오름차순으로 정렬한다.

...

 

테크니컬 적으로는 이렇게 두 가지의 프로세스를 여러 번 거친다. 아래의 예를 보자.

---

1. 힙 상태 만들기

 

각 작은 트리마다 수행해준다.

heapify : 부모노드가 자식노드보다 작자면, 자식노드 두 개를 비교해서 가장 큰 숫자를 부모 노드로 올려준다.

2. 이 상태에서 [0] = 7 값과 [6] = 4 값을 바꿔준다. 그러면 가장 무거운 값이 맨 뒤로 가게 된다.

3. 여기서 맨 마지막에 잘 정렬된 [6] 번 배열은 제외하고 나머지를 다시 힙상태로 만든다.

4. 가장 큰 수와 열려있는 마지막 노드를 바꿔준다.

5. 맨 마지막에 잘 정렬된 [5] 번 배열은 제외하고 나머지를 다시 힙상태로 만든다.

6. 가장 큰 수와 열려있는 마지막 노드를 바꿔준다.

7. 맨 마지막에 잘 정렬된 [4] 번 배열은 제외하고 나머지를 다시 힙상태로 만든다.

8. 가장 큰 수와 열려있는 마지막 노드를 바꿔준다.

9. 맨 마지막에 잘 정렬된 [3] 번 배열은 제외하고 나머지를 다시 힙상태로 만든다.

10. 가장 큰 수와 열려있는 마지막 노드를 바꿔준다.

11. 맨 마지막에 잘 정렬된 [2] 번 배열은 제외하고 나머지를 다시 힙상태로 만든다.

둘은 바꿀필요가 없으니 그냥 둔다.

12. 가장 큰 수와 열려있는 마지막 노드를 바꿔준다.

 

이렇게 내가 원했던 오름차순으로 잘 정리가 되었다..! 

 

그럼 이제 코드를 짜보자 헥헥

1. 최대 힙으로 바꾸는 함수를 만들어야 하고

2. 바꿔주는 함수도 있어야 한다.

#include <stdio.h>

void    heapify(int *arr, int size);
void    swap_root(int *arr, int size);

int main()
{	
    int arr[7] = {7, 2, 0, 1, 5, 6, 4};
    int size;
    int i;

    //원래 배열을 출력하기 위한 printf
    i = 0;
    printf("Original arr\n");
    while(i < 7)
    {
        printf("%d ", arr[i]);
        i++;
    }
    printf("\n");
    
    //heap sort 시작
    i = 0;
    size = 7;
    while(i < 7)
    {
        heapify(arr, size); //힙상태로 만들어주고
        swap_root(arr, size); //루트노드와 마지막노드를 바꿔준다
        size--; //마지막 노드는 제외하기 위해서 숫자를 줄이고
        i++; //다음 차례로 넘어간다.
    }
	
    //변화 후 배열을 출력하기 위한 printf
    i = 0;
    printf("after heap sort\n");
    while(i < 7)
    {
        printf("%d ", arr[i]);
        i++;
    }
    printf("\n");
    return 0;
}

void    heapify(int *arr, int size) //힙상태를 만든다.
{
    int i;
    int tmp;
    int root;
    int child;

    i = 1;
    while(i < size)
    {
        child = i;
        while (child != 0)
        {
            root = (child - 1) / 2; //루트노드의 길이를 구하는 방법
            if(arr[root] < arr[child]) //만약에 루트노드가 자식노드보다 작다면 바꿔주기
            {
                tmp = arr[root];
                arr[root] = arr[child];
                arr[child] = tmp;
            }
        child = root; // 다시 원점으로 돌아간다. 
        }
        i++; // i가 증가하면서 child가 증가한다.
    }
}

void    swap_root(int *arr, int size) //루트노드와 마지막 노드 스왑하기
{
    int tmp;

    tmp =  arr[0];
    arr[0] = arr[(size - 1)]; //배열은 0부터 시작하기 때문에 하나를 줄여준다.
    arr[(size - 1)] = tmp;
}

결과는!

$ ./a.out
Original arr
7 2 0 1 5 6 4
after heap sort
0 1 2 4 5 6 7

---

6. 퀵정렬 (Quick sort)

퀵 정렬(Quicksort)은 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다.  또한 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 이러한 이유로 퀵소트(빠른 정렬)라는 이름의 기원이 되었다.

자꾸 쪼개서 옮기네 이거아주!

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.

 

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot)이라고 한다. 
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다. 그리고 재귀적 호출에 따라 정렬되기 때문에 스택이 사용된다.

 

중요한 건 이 정렬이 위에서 다룬 모든 정렬 중에 가장 빠른 정렬이다! 그리고 이 정렬은 이해하고 나면 정말 깔끔하고 쉽다. 아래의 예시를 보기 전에 일단 아래의 규칙을 이해하자.

 

피벗(pivot)은 맨 앞의 숫자든, 맨 뒤의 숫자든, 중간에 어떠한 숫자든 상관없다. 보통 컴퓨터에서는 맨 앞 숫자를 정한다고 한다.

left는 오른쪽으로 이동하면서 pivot값보다 작으면 쭉쭉 나아가고, 크면 멈춘다.

right는 왼쪽으로 이동하면서 pivot값보다 크면 쭉쭉 나아가고, 작면 멈춘다.

이렇게 멈춘 지점에서 left와 right가 값을 바꿔준다.

left와 right이 엇갈리면 멈춘다.

---

그럼 계속 시험해 봤던 같은 숫자로 예를 들어보자.

이런 방법이...! （⊙ｏ⊙）

퀵함수는 생각보다 이해하기 힘들었다. 그래서 다른 배열로 또 연습해 보았다. 

혹시나 이 글을 차근차근 읽고 있다면, 스스로 아래의 배열을 퀵정렬로 오름차순 만드는 것을 시도해 보자.

 

<테스트 예제>

8

69

5

50

7

3

1

11

10

20

 

답은 여기에 👇

---

그럼 이제 코딩을 짜보자@@

#include <stdio.h>

//위치를 바꿔주는 함수
void    swap(int *a, int *b)
{
    int tmp;

    tmp = *a;
    *a = *b;
    *b = tmp;
}

//배열을 비교해주는 함수
int    quick_sorting(int *arr, int start, int end)
{
    int pivot;
    int left;
    int right;
    int tmp;

    pivot = start;
    left = start;
    right = end + 1;

    while(left < right)
    {
        while(left <= end && arr[left] < arr[pivot])
            left++;
        while(right >= start && arr[right] > arr[pivot])
            right--;
        if(left < right) //left가 pivot보다 크고 right가 pivot보다 작으면!
            swap(&arr[left], &arr[right]);  
        //착착 돌다가 left와 right이 겹치면 while문을 빠져나옴         
    }
    swap(&arr[right], &arr[pivot]); //그러면 pivot과 겹친 곳을 바꿔줌

    return(right); // pivot위치를 반환해줌
}

//배열을 보내주는 함수
void    quick_sort(int *arr, int start, int end)
{
    int pivot;

    if(start < end)
    {
        pivot = quick_sorting(arr, start, end);
        quick_sort(arr, start, pivot - 1);
        quick_sort(arr, pivot + 1, end);
    }
}

int main()
{
    int arr[7] = {7, 2, 0, 1, 5, 6, 4};
    int i;

    quick_sort(arr, 0, 6);

    i = -1;
    while (++i < 7)
        printf("%d ", arr[i]);
    printf("\n");
    return (0);
}

$ ./a.out
0 1 2 4 5 6 7

---

드디어 필수 정렬들을 모두 정리했다. 모든 정렬을 코딩해 보면서 가장 쉽고 빠른 quick 정렬을 push swap에 사용하는 게 나을 것 같다는 생각이 들었다. 그러면 이제 코딩을 하러 가볼까!

 

출처

https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC

힙 정렬 - 위키백과, 우리 모두의 백과사전

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

합병 정렬 - 위키백과, 우리 모두의 백과사전

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

퀵 정렬 - 위키백과, 우리 모두의 백과사전