[JavaScript/section 7] 04 - 삽입 정렬

📌 문제

N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 문제이다. 정렬하는 방법은 삽입 정렬이다.

 

🧐 삽입 정렬(insertion sort)이란 무엇일까❓

• 손 안의 카드를 정렬하는 방법과 유사하다.
  • 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입한다.
  • 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다.
• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
• 매 순서마다 해당 요소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

 

📝 풀이

🧑🏻‍💻 나의 풀이 방법

function solution(arr) {
  const answer = [];

  for (let i = 0; i < arr.length; i++) {
    // for 문을 돌면서 배열에 요소를 하나씩 추가한다.
    answer.push(arr[i]);
    let j = i;

    // while 문을 돌면서 j가 j - 1보다 작다면 교체하고 j--를 한다.
    // j가 j - 1보다 크다면 자신의 위치를 찾은 것이므로 while 문을 벗어난다. 
    while (j > 0 && answer[j] < answer[j - 1]) {
      [answer[j], answer[j - 1]] = [answer[j - 1], answer[j]];
      j--;
    }
  }

  return answer;
}

let arr = [11, 7, 5, 6, 10, 9];
console.log(solution(arr));

 

👨🏼‍🏫 강사님 풀이 방법

function solution(arr) {
  let answer = arr;

  for (let i = 1; i < arr.length; i++) {
    // 배열이 뒤로 밀리면 값이 달라지기 때문에 temp 변수에 저장
    let tmp = arr[i];
    let j;
    // 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 arr[j]가 temp보다 크면 한 칸씩 뒤로 이동
    for (j = i - 1; j >= 0; j--) {
      if (arr[j] > temp) arr[j + 1] = arr[j];
      else break;
    }
    // arr[j]가 temp보다 작아 break 문을 만나거나 for 문이 그대로 끝나는 경우 
    // temp가 자신의 위치를 찾은 것이므로 arr[j + 1]에 temp를 저장
    arr[j + 1] = temp;
  }

  return answer;
}

let arr = [11, 7, 5, 6, 10, 9];
console.log(solution(arr));