프로그래밍/알고리즘
2020. 4. 20.
Merge Sort (병합정렬)
개념 - 분할 정복 알고리즘을 응용한 정렬 (분할 정복이란 문제를 나눌 수 없을 때까지 나누어서 각각을 풀고 다시 합병하는 과정을 거쳐 문제의 답을 얻는 알고리즘을 말한다.) - 퀵 정렬보다 전반적으로 속도가 느림 - 데이터 크기만한 메모리가 더 필요 - 데이터의 상태에 영향을 받지 않음 (힙, 퀵 정렬은 같은 값의 데이터가 있으면 순서가 뒤바뀔 수도 있다. 정수형 배열[0] = 100, 배열[10] = 100을 정렬할 때 배열[10]이 배열[0]보다 앞에 오는 경우가 생일 수 있다. 그러나 병합 정렬은 위와 같은 상황이 발생하지 않는다.) 정수형 배열 A[9]가 있고 [0]번부터 순서대로 (5,3,1,9,4,2,8,7,6)이 있다고 가정하자. 배열 A의 값들을 정렬하려고 할 경우 (5,3,1,9,4..
