[알고리즘] 병합 정렬

2022. 2. 9. 16:38·알고리즘/풀이 힌트
반응형

병합 정렬 : 피벗 값이 없고 일단 정확히 반으로 자르고 나중에 정렬

-> 퀵 정렬과 마찬가지로 ' 분할 정복' 방법을 채택한 알고리즘

​

정확하게 반절씩 나눈다는 점에서 최악의 경우에도 O(N * logN)의 시간 복잡도를 가진다.

​

76583519를 병합 정렬을 사용하여 정렬한다고 했을 경우

시작 : 7 6 5 8 3 5 9 1

1 : 67 58 35 19로 2개씩 묶어서 2개씩 각각 정렬해 준다.

2 : 5678 1359로 4개씩 묶어 4개씩 각각 정렬해 준다.

3 : 13556789 ​로 하나로 합치며 정렬하여 준다.

​

이때 폭을 N 높이를 log2N이라고 한다.

즉, 위 정렬은 8 * log28(3) 번 연산을 한다.

1번에서 8번 -> 76 정렬 때 2번, 58 정렬 때 2번, 35 정렬 때 2번, 91 정렬 때 2번 = 8

2번에서 8번 -> 67 58 정렬 때 4번, 35 91 정렬 때 4번 = 8번

-> 67 58 정렬 방법은

67 58 -> 6 5 비교 5가 작기 때문에 5가 제일 앞 5 _ _ _

-> 6 8 비교 6이 작기 때문에 5 다음 6 5 6 _ _

-> 7 8 비교 7이 작기 때문에 6 다음 7 5 6 7 _

-> 나머지 8 5 6 7 8

====> 총 4번 연산

3번에서 8번 -> 5678 1359 정렬 때 8번 = 8번

​

====> 총 24번 연산 => 8 * 3

​

그렇기 때문에 병합 정렬의 시간 복잡도는 O(N * log2N)이다.

병합 정렬의 시간 복잡도

O(N * logN)

 
#include<stdio.h>

#define num 8
int sorted[8];                     // 합칠때 마다 배열이 필요하기 때문에 메모리 소모를 줄이기 위해서 
                                   // 정렬 배열은 반드시 전역변수로 선언하여 모든 함수가 공통으로 사용
void merge(int a[], int m, int middle, int n) {
	int i = m;
	int j = middle + 1;   // (7  6)  (5  8) 정렬시 middle 값은 0 + 3 / 2 
	int k = m;			  // 즉 1이기 때문에 6의 자리에 값이기 때문에 +1을 해주어 j는 2 => 5부터 시작이다
//  작은 순서대로 배열에 삽입

	while ( i <= middle && j <= n){
		if (a[i] <= a[j]) {
			sorted[k] = a[i];
			i++;
		}
		else {
			sorted[k] = a[j];
			j++;
		}
		k++;
	}
//  남은 데이터 삽입  -> 위 예시 2번에서 67 58 연산시 마지막 8의 경우를 대비하여
	if (i > middle) {    // i가 먼저 배열에 삽입 되었을 경우
		for (int t = j; t <= n; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	else {              // j가 먼저 배열에 삽입 되었을 경우
		for (int t = i; t <= middle; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
//  마지막 정렬된 배열을 삽입
	for (int t = m; t <= n; t++) {
		a[t] = sorted[t];   
	}
}

void mergeSort(int a[], int m, int n) {  // 병합 정렬인 경우 재귀함수를 사용하면 쉽게 구현이 가능하다.
//  크기가 1보다 큰 경우
	if(m < n){
		int middle = (m + n) / 2;
		
		mergeSort(a, m, middle);        // m과 middle 사이에서 array[]배열을 정렬
		mergeSort(a, middle + 1, n);    // middle + 1과 n 사이에서 array[]배열을 정렬
		merge(a, m, middle, n);
	}
}

int main(void) {
	int array[num] = { 7, 6, 5, 8, 3, 5, 9, 1 };
	mergeSort(array, 0, num - 1);

	for (int i = 0; i < num; i++)
		printf("%d ", array[i]);
}

​

병합 정렬을 구현할 때 신경써야 하는 부분은 정렬에 사용되는 배열 sorted 배열을 반드시 '전역변수'로 선언해야 한다는 것이다.

함수 안에 배열을 선언할 경우 매 번 배열을 선언해야 한다는 점에서 메모리 자원의 낭비가 커질 수 있기 때문입니다.

​

이와 같이 병합 정렬은 기존 데이터를 담을 추가적인 배열 공간이 필요하다는 점에서 메모리 활용이 비효율적이란 문제와 일반적인 경우 퀵 정렬보다 느리다는 점이 있지만

​

어떠한 상황에도 정확이 O(N * logN)을 보장한다는 점에서 몹시 효율적인 알고리즘이다.

반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘 > 풀이 힌트' 카테고리의 다른 글

[알고리즘] 퀵 정렬_원리  (0) 2022.02.09
[알고리즘] 삽입 정렬  (0) 2022.02.09
[알고리즘] 버블정렬  (0) 2022.02.09
알고리즘 순서도 도형의 의미  (0) 2022.02.09
[알고리즘] 선택 정렬  (0) 2022.02.09
'알고리즘/풀이 힌트' 카테고리의 다른 글
  • [알고리즘] 삽입 정렬
  • [알고리즘] 버블정렬
  • 알고리즘 순서도 도형의 의미
  • [알고리즘] 선택 정렬
잉여개발자
잉여개발자
풀스택 개발자를 목표로 잉여롭게 개발 공부도 하면서 다양한 취미 생활도 즐기고 있는 잉여 개발자입니다.
  • 잉여개발자
    잉여로운 개발일지
    잉여개발자
    • 분류 전체보기 (789)
      • 개발정보 (36)
      • 개발환경 (7)
      • 개발생활 (19)
      • React (141)
        • 이론 (23)
        • 기능 (12)
        • 실험실 (88)
        • 버그 (6)
        • 패스트캠퍼스 (9)
        • Npm (3)
      • React Native (28)
        • 공통 (6)
        • TypeScript (3)
        • JavaScript (18)
        • 버그 (1)
      • Next.js (30)
        • 이론 (13)
        • 실험실 (13)
        • 버그 (3)
      • Web (35)
      • 알고리즘 (202)
        • 풀이 힌트 (39)
      • JavaScript (47)
      • TypeScript (29)
        • 기초 (27)
        • 실험실 (2)
      • Node.js (13)
        • 이론 (0)
        • 기능 (3)
        • 실험실 (9)
        • 버그 (1)
      • 도커 (4)
      • CCNA (22)
        • 이론 (4)
        • 문제 (18)
      • 취미생활 (167)
        • 잉여로운 칵테일 (2)
        • 잉여의 식물키우기 (130)
        • 잉여로운 여행기 (11)
        • 잉여의 제2외국어 (21)
        • 잉여로운 책장 (2)
      • Java (1)
        • Java의 정석 (1)
      • 꿀팁 공유 (3)
  • 태그

    Docker
    리얼클래스
    타입스크립트
    네트워크
    영어회화
    타일러영어
    프로그래머스
    CCNA
    javascript
    ReactNative
    next.js
    Babel
    영어독학
    네이버 부스트캠프
    ChatGPT
    Node.js
    CSS
    자바스크립트
    바질 키우기
    바질
    리액트
    redux
    덤프
    다이소
    리얼학습일기
    webpack
    typescript
    react
    알고리즘
    식물
  • hELLO· Designed By정상우.v4.10.1
잉여개발자
[알고리즘] 병합 정렬
상단으로

티스토리툴바