[Algorithm] Merge Sort(병합 정렬)

 

https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5#curriculum

[무료] 알고리즘의 개요와 실습 환경 구축 - 인프런 | 강의

 

 

8강 병합정렬에 대한 리뷰이다.

 

 

 

병합정렬도 퀵소트처럼 분할 정렬이다. 하지만 퀵소트에 비해 안정적인 n*logN 의 시간복잡도를 가진다.

 

 

 

 

분할(divide): 주어진 리스트를 요소 1개가 남을 때까지 절반으로 쪼개는 작업을 거치고

정복(conqure & merge): 쪼개기가 완료되면 인접한 요소끼리 비교하여 정렬된 상태로 합친다. 

 

 

더 정확한 이해를 위해 gif 파일도 첨부하겠다.

 

 

 

https://gaemi606.tistory.com/entry/%ED%80%B5-%EC%A0%95%EB%A0%ACQuick-sort

 

 

 

** C++

동빈 나님의 강의에서 나온 소스이다. 변수 이름만 보기 쉽게 조금 바꿨다.

 

#include <stdio.h>

int number = 8;
int sorted[8]; // 정렬 배열은 반드시 전역 변수로 만들어줘야 함 
// 필요할 때마다 배열을 만드는 불필요한 메모리 사용을 막기 위함 

void merge(int a[], int start, int middle, int end) {
	int i = start; // 쪼개진 왼쪽 리스트의 시작점
	int j = middle + 1; // 쪼개진 오른쪽 리스트의 시작점
	int k = start; // sorted의 인덱스(0부터 시작)
	
	// 작은 순서대로 배열에 삽입 
	while(i <= middle && j <= end) {
		if (a[i] <= a[j]) { // 왼쪽 리스트 원소가 오른쪽 리스트 원소보다 작거나 같으면
			sorted[k] = a[i]; // 왼쪽 리스트 원소를 sorted 에 삽입
			i++; // 왼쪽리스트 인덱스 증가
		} else {
			sorted[k] = a[j]; // 반대의 경우 오른쪽리스트 원소 sorted에 삽입 후 인덱스 증가
			j++;
		}
		k++;
	}
	// 남은 데이터 삽입
	if (i > middle) { // 왼쪽 리스트 먼저 채워졌을 때 
		for (int t = j; t <= end; t++) { // 오른쪽리스트 원소(t=j)로 채워줌
			sorted[k] = a[t];
			k++;
		}
	} else { // 오른쪽 리스트 먼저 채워졌을 때
		for (int t = i; t <= middle; t++) { // 왼쪽리스트 원소(t=i)로 채워줌
			sorted[k] = a[t];
			k++;
		}
	}
	// 정렬된 배열을 삽입 (sorted를 복사해서 원래 배열에옮겨줌)
	for (int t = start; t <= end; t++) {
		a[t] = sorted[t];
	} 
}

void mergeSort(int a[], int m, int n) {
	if (m < n) {
		int middle = (m + n) / 2;
		mergeSort(a, m, middle);
		mergeSort(a, middle + 1, n);
		merge(a, m, middle, n);
	}
}

int main(void) {
	int array[number] = {7, 6, 5, 8, 3, 5, 9 , 1};
	mergeSort(array, 0, number - 1);
	for (int i = 0; i < number; i++) {
		printf("%d ", array[i]);
	}
}

 

 

 

** Javascript

 

let number = 8;
let sorted = Array.from(number).fill(0);

function merge(a, start, middle, end) {
	let i = start;
	let j = middle + 1;
	let k = start;
	
	while(i <= middle && j <= end) {
		if (a[i] <= a[j]) {
			sorted[k] = a[i];
			i++;
		} else {
			sorted[k] = a[j];
			j++;
		}
		k++;
	}
	if (i > middle) {
		for (let t = j; t <= end; t++) {
			sorted[k] = a[t];
			k++;
		}
	} else {
		for (let t = i; t <= middle; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	for (let t = start; t <= end; t++) {
		a[t] = sorted[t];
	} 
}

function mergeSort(a, m, n) {
	if (m < n) {
		// 인덱스가 소수점으로 들어가서 undefined -> Math.floor 사용
		let middle = Math.floor((m + n) / 2);
		mergeSort(a, m, middle);
		mergeSort(a, middle + 1, n);
		merge(a, m, middle, n);
	}
}

function main() {
	let array = [7, 6, 5, 8, 3, 5, 9 , 1];
	mergeSort(array, 0, number - 1);
	console.log(array.join(", "));
}

 

 

계속 안 됐었는데 드디어 됐다. (n + m) / 2 때문이었다.

 

k++ 때문에 array index 에러 나는 건가 싶었는데

 

console.log(k) 찍어보니 7.5 12.25 난리나 있었음

 

 

 

 

 

위 소스보다 javascript 로는 아래 소스가 병합정렬이 더 잘 보이는 것 같아서 가져왔다.

 

 

const merge = function (left, right) { // 정렬된 왼쪽과 오른쪽 배열을 받아서 하나로 합치는 순수한 함수
	// left, right already sorted
	const result = [];
	while (left.length !== 0 && right.length !== 0) {
		left[0] <= right[0] ? result.push(left.shift()) : result.push(right.shift());	
	}

	return [...result, ...left, ...right]; // 아래 세줄과 같은 역할을 하는 코드
    // if(left.length === 0) results.push(...right);
    // if(right.length === 0) results.push(...left);
    // return results;
}

const mergeSort = function (array) {
	// ending condition: length === 1 인 배열이 들어올 때, 정렬이 끝난 것. 
	if (array.length === 1) return array;

	// 2로 나누고 내림을 해야
	// length 가 2일 때도 안전하게 배열을 slice 할 수 있다.
	const middleIndex = Math.floor(array.length / 2); 
	const left = array.slice(0, middleIndex);
	const right = array.slice(middleIndex);

	// 재귀로 계속해서 반으로 나누면서 length 가 1이 될때까지 쪼개고, 
	// 거꾸로 올라오면서 순수한 함수인 merge에 인자로 넣어서 다시 병합되어서 최종값을 리턴한다.
	return merge(mergeSort(left), mergeSort(right));
}

const arr = [7, 6, 5, 8, 3, 5, 9 , 1];

const result = mergeSort(arr);
console.log(result);

 

 

출처:

https://jun-choi-4928.medium.com/javascript%EB%A1%9C-merge-sort-%EB%B3%91%ED%95%A9%EC%A0%95%EB%A0%AC-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-c13c3eee6570

JavaScript로 Merge Sort(병합정렬) 구현하기

 

 

var mergeSort = function(array) {
  if (array.length < 2) return array; // 원소가 하나일 때는 그대로 내보냅니다.
  var pivot = Math.floor(array.length / 2); // 대략 반으로 쪼개는 코드
  var left = array.slice(0, pivot); // 쪼갠 왼쪽
  var right = array.slice(pivot, array.length); // 쪼갠 오른쪽
  return merge(mergeSort(left), mergeSort(right)); // 재귀적으로 쪼개고 합칩니다.
}
function merge(left, right) {
  var result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) { // 두 배열의 첫 원소를 비교하여
      result.push(left.shift()); // 더 작은 수를 결과에 넣어줍니다.
    } else {
      result.push(right.shift()); // 오른쪽도 마찬가지
    }
  }
  while (left.length) result.push(left.shift()); // 어느 한 배열이 더 많이 남았다면 나머지를 다 넣어줍니다.
  while (right.length) result.push(right.shift()); // 오른쪽도 마찬가지
  return result;
};

mergeSort([5,2,4,7,6,1,3,8]); // [1, 2, 3, 4, 5, 6, 7, 8]

 

출처:

https://www.zerocho.com/category/Algorithm/post/57ee1fc107c0b40015045cb4

(Algorithm) 합병(머지, 병합) 정렬

 

 

 

 

javascript 에는 push, shift, pop, unshift 등 배열에 값을 추가하거나 제거는 다양한 함수들을 볼 수 있는데

 

1) push

const 배열 = ['something'];
const 값 = 'else'

배열.push(값); // 배열의 맨 끝에 값 추가
console.log(배열); // 'something', 'else'

 

 

2) pop

const 배열 = ['something', 'else'];

배열.pop(); // 배열의 맨 끝에 값 삭제
console.log(배열); // 'something'

const 배열 = ['something', 'else'];

const 값 = 배열.pop(); // pop은 뺀 값을 return 해준다.
console.log(값); // 'else'

 

 

3) shift

const 배열 = ['something', 'else'];

배열.shift(); // 배열의 맨 앞에 값 삭제
console.log(배열); // 'else'

const 배열 = ['something', 'else'];

const 값 = 배열.shift(); // shift도 뺀 값을 return 해준다.
console.log(값); // 'something'

 

4) unshift

const 배열 = ['something'];
const 값 = 'else'

배열.unshift(값); // 배열의 맨 앞에 값 추가
console.log(배열); // 'else', 'something'

 

 

 

 

 

 

** Java

 

 

java로는 사실 맨 처음 저 인강 소스로는 이해가 잘 안 가서 아래 블로그를 훨씬 더 많이 참고 했다.

 

소스도 동빈 나님의 C++ 소스랑 비슷해서 속으로 쾌재를 부름

 

private static int number = 8;
private static int[] sorted = new int[number];

private static void merge(int a[], int start, int middle, int end) {
	int i = start;
	int j = middle + 1;
	int k = start;
	
	while(i <= middle && j <= end) {
		if (a[i] <= a[j]) {
			sorted[k] = a[i];
			i++;
		} else {
			sorted[k] = a[j];
			j++;
		}
		k++;
	}

	if (i > middle) {
		for (int t = j; t <= end; t++) {
			sorted[k] = a[t];
			k++;
		}
	} else {
		for (int t = i; t <= middle; t++) {
			sorted[k] = a[t];
			k++;
		}
	}

	for (int t = start; t <= end; t++) {
		a[t] = sorted[t];
	} 
}

private static void mergeSort(int a[], int m, int n) {
	if (m < n) {
        if (m == n) return; // 더 쪼개질 수 없는 경우를 위해서 추가(없어도 됨)
		int middle = (m + n) / 2;
		mergeSort(a, m, middle);
		mergeSort(a, middle + 1, n);
		merge(a, m, middle, n);
	}
}

public static void main(String[] args) {
	int array[] = {7, 6, 5, 8, 3, 5, 9 , 1};
	mergeSort(array, 0, number - 1);
	for (int i = 0; i < number; i++) {
		System.out.printf("%d ", array[i]);
	}
}

 

 

참고:

https://st-lab.tistory.com/233

자바 [JAVA] - 합병정렬 / 병합정렬 (Merge Sort)