삽입 정렬

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

▣ 입력설명

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

▣ 출력설명

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

▣ 입력예제 1

6
11 7 5 6 10 9

▣ 출력예제 1

5 6 7 9 10 11

문제 풀이

삽입 정렬

2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입한다.

1. 두번째 원소부터 시작해야하니 i=1부터 시작
2. tmp에 삽입할 값을 넣어둔다.
3. j는 삽입할 값의 앞 원소부터 배열의 첫 원소까지
   3-1. arr[j]가 삽입할 값보다 크면 뒤로 옮기고
   3-2. arr[j]가 삽입할 값보다 작으면 반복문 탈출해서 arr[j]의 뒤에 값을 삽입한다.

function solution(array) {
  let arr = array;
  for (let i = 1; i < arr.length; i++) {
    let tmp = arr[i];
    let j;
    for (j = i - 1; j >= 0; j--) {
      if (arr[j] > tmp) {
        arr[j + 1] = arr[j];
      } else break;
    }
    arr[j + 1] = tmp;
  }
  return arr;
}
let array = [11, 7, 5, 6, 10, 9];
console.log(solution(array));