(알고리즘) 삽입정렬

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

입력설명

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

출력설명

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

입력예제

• 11 7 5 6 10 9

출력예제

• 1 5 6 7 9 10 11

삽입 정렬(insertion Sort) 알고리즘

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

• 삽입정렬은 두 번째 자료부터 시작해 그 앞(왼쪽)의 자료들과 비교해 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 삽입해 정렬하는 알고리즘이다.
• 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.
• 처음 Key값은 두 번째 자료부터 시작한다.

function solution(arr) {
  let answer = arr;
  for(let i = 1; i < arr.length; i++) {
    let key = arr[i], j // 기준 점을 만들어준다.
    for(j = i - 1; j >= 0; j--) {
      if (arr[j] > key) arr[j+1] = arr[j]
      else break;
    }
    arr[j+1] = key;
  }
  return arr;
}