sort없이 삽입 정렬 Javascript

cptkuk91·2022년 8월 29일
1

Algorithm

목록 보기
79/161
post-custom-banner

문제

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

주의 사항

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

입출력 예시

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

풀이

const insertionSort = function (arr) {
	let result = [arr[0]];
    
    for(let i = 0; i < arr.length; i++){
    	if(arr[i] >= result[i -1]){
        	result.push(arr[i]);
        } else {
        	for(let j = 0; j < i; j++){
            	if(arr[i] <= result[j]){
                	let left = result.slice(0, j);
                    let right = result.slice(j);
                    result = left.concat(arr[i], right);
                    break;
                }
            }
        }
    }
    return result;
};

slice와 concat을 자유롭게 활용할 수 있다면 쉽게 접근 가능한 문제입니다.
처음에 result를 빈 배열로 설정 후 풀이하려했지만, 비교 값이 필요하다는 걸 늦게 깨달았습니다.

profile
메일은 매일 확인하고 있습니다. 궁금하신 부분이나 틀린 부분에 대한 지적사항이 있으시다면 언제든 편하게 연락 부탁드려요 :)
post-custom-banner

0개의 댓글