문제 : insertionSort

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.

입력

인자 1 : arr

• number 타입을 요소로 갖는 배열
• arr[i]는 정수
• arr.length는 1,000 이하

출력

• number 타입을 요소로 갖는 배열을 리턴해야 합니다.
• 배열의 요소는 오름차순으로 정렬되어야 합니다.
• arr[i] <= arr[j] (i < j)

주의사항

• 삽입 정렬을 구현해야 합니다.
• arr.sort 사용은 금지됩니다.
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

입출력 예시

let output = insertionSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]

풀이

삽입정렬 알고리즘을 구현하면 된다!
삽입정렬이란 배열의 2번째부터 앞에 수와 비교해서 크면 그대로 작으면 앞으로 땡기는 정렬 알고리즘이다.

const insertionSort = function (arr, callback = (num) => num) {
	for (let i = 1; i < arr.length; i++) {
	    let num = arr[i];	// 비교 대상
    	let index = i - 1;	// 앞에꺼와 비교해야하기 때문에

	    while (index >= 0 && callback(arr[index]) > callback(num)) {
          	// 앞으로 땡기면서 비교하기 때문에 index가 0보다 낮아지면 안된다(배열을 벗어남)
            // arr[index] > num : 대상값이 전값보다 크면 계속 반복실행
    		arr[index + 1] = arr[index];
          	// 지금위치에 전의 값을 넣는다
		    index--;
            // 비교 대상 앞으로 이동
    	}

    	arr[index + 1] = num;
    }
    return arr;
};

느낀점

삽입정렬을 알고있어서 구현했었는데 문제에서 callback함수를 이용하라고 해서 당황했었다..
callback 함수가 필요한가? 싶었는데 필요한가보다... 일단 지금은 다른것도 공부해야하기에.. callback를 다시 공부하고 왔을때 이해되는지 봐야겠당.