삽입 정렬

문제

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

 

문제풀이

삽입 정렬(Insertion Sort)

• 손 안의 카드를 정렬하는 방법과 유사
• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교
• 비교 후 자신의 위치를 찾아 삽입함으로써 정렬을 완성
• 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 적재

코드

function solution(...arr) {
  let answer = arr;

  for(let i = 1; i < arr.length; i++) { //삽입 정렬 두 번째 자료부터 시작하기 때문에 인덱스 초기값 1
    for(let j = i; j > 0; j--) { //현재 자신 앞에 놓여 있는 자료 배열의 갯수만큼 순회해야 하기 때문에 해당 갯수만큼 초기값 할당
      if(arr[j] < arr[j - 1]) {
        [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
      } else break; // 자신의 앞에 요소보다 크다는 것은 그 이후에 나오는 어떠한 수보다도 작아질 수 없기 때문에 순회 종료
    }
  }

  return answer;
}

console.log(solution(11, 7, 5, 6, 10, 9));

---

function solution(arr){
                let answer=arr;
                for(let i=0; i<arr.length; i++){
                    let tmp=arr[i], j;
                    for(j=i-1; j>=0; j--){
                        if(arr[j]>tmp) arr[j+1]=arr[j]; //이전 요소가 클 경우 해당 요소를 뒤로 넘김
                        else break;
                    }
                    arr[j+1]=tmp; //마지막으로 순회가 끝난 위치에 tmp 삽입
                } 
                return answer;
            }

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