[JS] 코딩 테스트 문제 : 삽입 정렬

문제 : 삽입 정렬

문제 설명

N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
정렬하는 방법은 삽입정렬입니다.

▣ 입력설명

첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에
있습니다.

▣ 출력설명

오름차순으로 정렬된 수열을 출력합니다.

▣ 입력예제 1

6
11 7 5 6 10 9

▣ 출력예제 1

5 6 7 9 10 11

내코드

function solution(arr) {
  let answer = arr;
  console.log("초기값", ...arr);

  // 2번째 숫자부터 순회
  for (let i = 1; i < answer.length; i++) {
    let temp = answer[i];

    // i - 1 번 숫자 j 부터 i 번째 숫자 temp 와 비교해 크다면
    // j + 1 번째 숫자는 j 번째 숫자가 되고 작다면 숫자 temp 가 되고 break
    // 마지막 번호 까지 진행될 때 까지 break 되지 않았다면 가장 작은 숫자이므로 첫번째 숫자는 temp 가 됨
    for (let j = i - 1; j >= 0; j--) {
      if (answer[j] > temp) {
        answer[j + 1] = answer[j];
      } else {
        answer[j + 1] = temp;
        break;
      }
      if (j === 0) {
        console.log(`기준값 {${temp}} 진행상황`, ...arr);
        answer[0] = temp;
      }
      console.log(`기준값 {${temp}} 진행상황`, ...arr);
    }
    console.log(`현재 ${i} 번째 정렬된 값:`, ...arr);
  }
  return answer;
}

풀이

1. i 는 1 부터 1씩 증가하며 입력된 숫자 배열의 길이 전까지 반복하는 반복문 안에서 정렬될 기준 값을 의미하는 변수 temp 를 선언하고 i 번째 값으로 초기화
2. 위 반복문 안에서 j 는 i -1 부터 1씩 감소 하며 0까지 반복하는 반복문 안에서 기준이된 temp값의 위치를 지정하기 위해 temp 와 answer[j] (j 는 i-1 부터 시작하므로 즉 j 는 i 이전 값들의 인덱스를 의미한다.) 값을 비교하여 answer[j] 값이 더 큰 경우 자연스럽게 temp는 answer[j] 는 앞에 위치해야 하므로 answer[j] 값은 한칸뒤 값인 answer[j + 1] 에 저장된다.
3. 만약 temp 값보다 작은 경우 그 값 바로 뒤가 순서상 temp 가 위치해야 하므로 answer[j + 1] 값은 temp 값으로 변경되고 반복문을 break 하여 종료합니다.
4. 만약 위 반복과정이 마친후 j 가 0 까지 진행된 경우는 temp 값이 이전 값들과 비교해 가면서 계속 기준값 temp 가 작아 이전값은 모두 한칸씩 뒤로 땡겨진 상태이므로 temp 값은 맨 앞에 위치시켜 마무리한다.
5. 모든 반복과정이 종료된 후 정렬된 배열을 반환

보완할 수 있는 부분

// 기존코드
for (let i = 1; i < answer.length; i++) {
  let temp = answer[i];

  for (let j = i - 1; j >= 0; j--) {
    if (answer[j] > temp) {
      answer[j + 1] = answer[j];
    } else {
      answer[j + 1] = temp;
      break;
    }
    if (j === 0) answer[0] = temp;
  }
}

// 보완코드
for (let i = 1; i < answer.length; i++) {
  let temp = answer[i],
    j;
  for (j = i - 1; j >= 0; j--) {
    if (answer[j] > temp) {
      answer[j + 1] = answer[j];
    } else break;
  }
  answer[j + 1] = temp;
}

기본적인 동작방식은 동일하지만 이전과 달리 j 두번째 for 문 이전에 선언해 두 번째 for 문이 처리된 후 j 값을 활용해서 바로 temp 값의 위치가 정해짐

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard