JavaScript Algorithm - insertionSort

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

단 정렬은 삽입정렬을 구현해야하며 sort는 사용하면 안됩니다. 그리고 입력받는 배열은 전부 중첩되지않은 1차원 배열입니다. 

 

입력

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

출력

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

입출력 예시

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

let output2 = insertionSort([5, 4, 3, 2, 1]);
console.log(output2);

 

 

풀이코드 설명1

const insertionSort1 = function (arr, transform = (item) => item) {
  //sorted에 첫번째 요소 값 할당 
  let sorted = [arr[0]];
  //배열의 길이만큼 반복순회를 돌지만 2번째 요소부터 반복을 한다. 
  for (let i = 1; i < arr.length; i++) {
    if (transform(arr[i]) >= transform(sorted[i - 1])) {
      sorted.push(arr[i]);
      console.log("if", sorted);
    }
    else {
      for (let j = 0; j < i; j++) {
        if (transform(arr[i]) <= transform(sorted[j])) {
          console.log("i", i, "j", j);
          const left = sorted.slice(0, j);
          const right = sorted.slice(j);
          console.log("arr[i]", arr[i]);
          console.log("left", left);
          console.log("right", right);
          sorted = left.concat(arr[i], right);
          console.log("else", sorted);
          break;
        }
      }
    }
  }

  return sorted;
};

 

풀이코드 설명2

const insertionSort2 = function (arr, transform = (item) => item) {
  //배열의 길이만큼 순회, 두번째 요소부터 탐색을 시작한다. 
  for (let i = 1; i < arr.length; i++) {
    //i=1,2,3,4
    let current = arr[i];
    console.log("current", current);
    let j = i - 1;
    console.log("j", j);
    // Compare the current element with the elements in the sorted portion of the array
    console.log("transform(current)", transform(current));
    console.log("transform(arr[j]", transform(arr[j]));
    //바로 앞의 요소와 그 다음요소의 길이 비교
    while (j >= 0 && transform(current) < transform(arr[j])) {
      console.log("while1 j", j);
      arr[j + 1] = arr[j];
      console.log("arr[j+1], arr[j]", arr[j + 1], arr[j]);
      j--;
      console.log("while2 j", j);
    }
    // Insert the current element in its correct position
    console.log("before arr", arr);
    arr[j + 1] = current;
    console.log("after arr", arr);
  }
  return arr;
};
let output2 = insertionSort2([5, 4, 3, 2, 1]);
console.log(output2);

 

풀이코드 설명2의 console.log 출력

데이터 흐름이 이해가 안된다면 콘솔로그를 다 찍고 데이터를 찍어서 보면 흐름이 이해가 된다.

current 4
j 0
transform(current) 4
transform(arr[j] 5
while1 j 0
arr[j+1], arr[j] 5 5
while2 j -1
before arr [ 5, 5, 3, 2, 1 ]
after arr [ 4, 5, 3, 2, 1 ]
current 3
j 1
transform(current) 3
transform(arr[j] 5
while1 j 1
arr[j+1], arr[j] 5 5
while2 j 0
while1 j 0
arr[j+1], arr[j] 4 4
while2 j -1
before arr [ 4, 4, 5, 2, 1 ]
after arr [ 3, 4, 5, 2, 1 ]
current 2
j 2
transform(current) 2
transform(arr[j] 5
while1 j 2
arr[j+1], arr[j] 5 5
while2 j 1
while1 j 1
arr[j+1], arr[j] 4 4
while2 j 0
while1 j 0
arr[j+1], arr[j] 3 3
while2 j -1
before arr [ 3, 3, 4, 5, 1 ]
after arr [ 2, 3, 4, 5, 1 ]
current 1
j 3
transform(current) 1
transform(arr[j] 5
while1 j 3
arr[j+1], arr[j] 5 5
while2 j 2
while1 j 2
arr[j+1], arr[j] 4 4
while2 j 1
while1 j 1
arr[j+1], arr[j] 3 3
while2 j 0
while1 j 0
arr[j+1], arr[j] 2 2
while2 j -1
before arr [ 2, 2, 3, 4, 5 ]
after arr [ 1, 2, 3, 4, 5 ]
[ 1, 2, 3, 4, 5 ]