학습(알고리즘)

1. 합병정렬은 분할 후 정렬합병을 하기 때문에 합병정렬이라고 부른다. 
구조는 재귀로 분할을 하고 정렬을 하는데 그 내부에 분할된 배열은 1개가 남을 때 까지 계속해서 분할되기 때문에 [1,2,3,4] 라면 [1],[2],[3],[4]로 분할되고 [1,2], [3,4]로 합병된 다음 [1,2,3,4]로 다시 합병된다. 코드는 아래와 같다.

function merge(arr1, arr2){//정돈된 배열(또는 하나만 있는 배열) arr1, arr2
    let results = []; //합병해서 돌려보낼 배열
    let i = 0; //idx i
    let j = 0; //idx j
    while(i < arr1.length && j < arr2.length){  //idx i또는 j가 길이초과시 중단
        if(arr2[j] > arr1[i]){               //배열의 맨 앞 비교 후 push, idx추가
            results.push(arr1[i]);
            i++;
        } else {
            results.push(arr2[j])
            j++;
        }
    }
    while(i < arr1.length) { //위 while이 종료됬으므로 arr1/2중 하나는 종료됬으므로
        results.push(arr1[i])
        i++;
    }
    while(j < arr2.length) { //아직 종료되지 않은 배열이면 push해서 마무리하기
        results.push(arr2[j])
        j++;
    }
    return results;          //arr1,2 모두 results에 넣었으므로 합병된 배열 반환
}

function mergeSort(arr){                //재귀함수로 분할
    if(arr.length <= 1) return arr;      //[1]처럼 길이1되면 종료
    let mid = Math.floor(arr.length/2);  //왼쪽 오른쪽 나누기 위한 중앙값
    let left = mergeSort(arr.slice(0,mid));//왼쪽값 slice로 받기(0~middle-1까지)
    let right = mergeSort(arr.slice(mid)); //오른쪽값 middle~끝까지 받기
    return merge(left, sright); 나눤 배열 merge로 정렬하며 합치기
}

오늘도 문제를 풀다보니 강의는 많이 듣지 못한 것 같다.
재귀, 배열, 구현등의 문제를 풀면 풀수록 적응이 되서 오답보다 정답의 비율이 더 많아진 것 같다.

오늘도 그래도 열심히 한 것 같은데..