[Algorithm] Merge Sort(병합 정렬)
[무료] 알고리즘의 개요와 실습 환경 구축 - 인프런 | 강의
알고리즘을 배우며, 실무에서는 알고리즘이 어떻게 활용되는지 알아봅니다., [임베딩 영상] 알고리즘의 개요와 실습 환경 구축 알고리즘은 문제를 해결하는 절차입니다.입력, 출력, 유한성, 명
www.inflearn.com
8강 병합정렬에 대한 리뷰이다.
병합정렬도 퀵소트처럼 분할 정렬이다. 하지만 퀵소트에 비해 안정적인 n*logN 의 시간복잡도를 가진다.
분할(divide): 주어진 리스트를 요소 1개가 남을 때까지 절반으로 쪼개는 작업을 거치고
정복(conqure & merge): 쪼개기가 완료되면 인접한 요소끼리 비교하여 정렬된 상태로 합친다.
더 정확한 이해를 위해 gif 파일도 첨부하겠다.
** 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);
출처:
JavaScript로 Merge Sort(병합정렬) 구현하기
JavaScript, Recursion
jun-choi-4928.medium.com
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) 합병(머지, 병합) 정렬
안녕하세요. 이번 시간에는 합병 정렬(머지 정렬 또는 병합 정렬)에 대해 알아보겠습니다. 삽입 정렬보다는 더 복잡하지만, 성능은 훨씬 좋아 자주 쓰이는 정렬 방법 중 하나입니다. 합병 정렬
www.zerocho.com
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)
[정렬 알고리즘 모음] 더보기 1. 계수 정렬 (Counting Sort) 2. 선택 정렬 (Selection Sort) 3. 삽입 정렬 (Insertion Sort) 4. 거품 정렬 (Bubble Sort) 5. 셸 정렬 (Shell Sort) 6. 힙 정렬 (Heap Sort) 7. 합..
st-lab.tistory.com