[알고리즘] 병합 정렬

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)
  • 태그

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

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.