JS 병합 정렬(Merge Sort), 분할 정복 전략(Divide and Conquer)

병합정렬은 데이터들을 잘게 쪼갠 다음에 하나로 합치는 과정에서 정렬하는 방법이다. 옛날에 테이프로 저장했는데 테이프는 데이터를 처음부터 읽어야 하는 특징이다. 테이프의 문제점 때문에 병합 정렬이 탄생했다.

-데이터를 절반씩 쪼개는 divide 작업을 먼저하는데 이 작업은 데이터가 하나만 남을 때까지 반복한다. 그 후에 하나씩 쪼개진 데이터를 정렬을 하면서 그룹화한다.

Big O

-worst case: O(nlog2n)

-best case: O(nlog2n)

-병합 정렬은 데이터를 분할 하는 단계와 다시 병합하는 단계로 나눌 수 있다. 분할하는 단계는 시간 복잡도에 포함하지 않는다.

-데이터를 분할한 후 병합하는 단계에서 재귀 호출의 길이는 log2n 이다. 1/2로 쪼개진 배열을 합치기 때문이다. 각각의 단계에서 데이터의 개수만큼 크기를 비교하는 연산이 필요하기 때문에 최대 n번의 비교 연산을 하게 된다.

-최선의 경우와 최악의 경우 모두 O(nlog2n)의 시간을 가지기 때문에 퀵정렬보다 항상 빠른것은 아니다. 퀵정렬이 병합 정렬보다 더 작은 상수 시간을 가지기 때문이다.3

장점: 최선의 경우와 최악의 경우가 O(nlog2n)의 시간이 소요되기 때문에 데이터분포에 영향을 덜 받는다. 항상 동일한 시간이 소요되므로 좋은 성능을 보장 한다.

단점: in place의 알고리즘이 아니기 때문에 별도의 메모리 공간이 필요하다.

stable: 중복된 데이터 순서가 바뀌지 않는다.

Merge Sort는 배열을 쪼개는 단계와 병합하는 단계로 나누어진다.

array의 길이가 2보다 작으면 분할이 끝나것이므로 return

2보다 크면 반으로 나눈닫.

left와 right으로 나눠진 배열은 각가 merge라는 함수를 호출하여 병합한다.

merge함수는 최종으로 합쳐진 배열을 담을 resultArray라는 배열을 준비하고

두 배열의 앞자리 숫자부터 비교하여 배열에 담는다.

while문을 빠져나오면 두 배열 중 숫자가 작은 한쪽 배열의 요소가 resultArray에 담기기 때문에 resultArray에 left와 right배열을 다시 합치고 리턴한다.

Divide and Conquer

-분할하여 정복한다.

-1680*640인 직사각형을 정사각형 토지로 잘게 나누고 싶을때. 정사각형의 토지는 가능한 크고 모든 정사각형의 토지의 크기는 같아야한다. 이럴때 분할정복한다.

-1.가장 간단한 경우로 기본 단계를 찾는다.

-2.주어진 문제를 가능한한 작게 줄여서 기본 단계가 되게끔 만드는 법을 찾는다.

-토지의 세로길이로 정사각형 2개를 만든다. 그러면 정사각형 2개와 직사가가형 한개가 된다.

-그 남은 직사각형을 똑같은 방법으로 나눈다.

-마지막에는 80*80이 돈다.

배열에 든 숫자의 합계를 구하는 문제.

1.기본 단계를 찾는다. 기본 단계는 원소의 개수가 0개이거나 1개인 배열을 받을 때 이다.

2.재귀 호출을 할 때마다 호출 대상이 되는 배열의 크기를 줄인다. sum([1,2,3,])은 1+ sum([2.3])으로 계산 가능한다.

sum([1,2,3])은 1+ sum([2.3]) 2 + sum([3])

function sumNum(arr){

if(arr.length === 0){

return 0;}

if(arr.length === 1){

return arr[0];}

return arr[0] + sumNum(arr.slice(1));}

sumNum([1.2.3.4.5])

웹 개발