[TIL] 2020. 08. 08. Insertion_Sort

달밤·2020년 8월 8일
1

TIL

목록 보기
91/110
post-thumbnail

오늘 배운 것

삽입 정렬(Insertion Sort)

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. <위키백과>

  • 우선 난 위키백과의 삽입정렬에 대한 정의를 보고 아무것도 이해하지 못했다...
  • 그래서 삽입정렬을 그림으로 표현한 것을 보았는데

  • 여전히 감이 안잡혀서 여러 블로그를 순회하기 시작했다.
  • 삽입정렬의 핵심은 배열의 모든 요소를 순회하면서 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입하는 방식이라는 것이었다.

구체적인 개념

  • 삽입 정렬은 두 번째 요소부터 시작해서 앞(이미 정렬된 배열 부분)의 요소들과 비교하여 적절한 위치에 삽입하게 되는데, 이때 원래 자리에 있던 요소는 뒤쪽으로 옮긴다.
  • 첫 번째 요소는 이미 정렬이 되어있다고 가정을 하고, 두 번째 요소부터 비교를 시작하게 된다.
  • 두 번째 요소는 이미 정렬된 배열(1번 요소)과 비교를 하고, 다음번으로 세 번째 요소는 이미 정렬된 배열(2번 요소, 1번 요소), 다음으로 네 번째 자료는 이미 정렬된 배열(3번 요소, 2번 요소, 1번 요소)과 비교한 후 자료가 삽입될 위치를 찾게 된다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.
  • 예시

구현 코드(JavaScript)

  1. 내가 구현한 코드
//오름차순 정렬을 삽입 정렬 방식을 이용해 구현해보고자 한다.
var insertionSort = function(array) {
  let j;
  for(let i = 1; i < array.length; i++){ //비교를 시작할 두 번째 요소 지정
    let currentElement = array[i] //새로운 변수에 비교할 값을 담는다.
    //이미 정렬된 배열과 비교해야 하므로, 비교할 값보다는 idx가 낮아야 할 것이다.
    for(j = i-1; j >= 0; j--){ 
        //비교할 값보다 앞선 값이 더 크면
      if(currentElement< array[j]){
          //오른쪽에 할당한다.
        array[j+1] = array[j]
        //비교할 값보다 작으면(잘 정렬이 되어있으면), for문을 나간다.
      }else{
        break;
      }
    }
      //남아 있는 빈칸에 비교할 값을 담는다.
    array[j+1] = currentElement
  }
  return array;
};
  1. 제로초님의 블로그의 예시
var insertionSort = function(array) {
  var i = 1, j, temp;
  for (i; i < array.length; i++) {
    temp = array[i]; // 새로운 숫자를 선택함
    for (j = i - 1; j >= 0 && temp < array[j]; j--) { // 선택한 숫자를 이미 정렬된 숫자들과 비교하며 넣을 위치를 찾는 과정, 선택한 숫자가 정렬된 숫자보다 작으면
      array[j + 1] = array[j]; // 한 칸씩 뒤로 밀어낸다
    }
    array[j + 1] = temp; // 마지막 빈 칸에 선택한 숫자를 넣어준다.
  }
  return array;
};
insertionSort([5, 6, 1, 2, 4, 3]); // [1, 2, 3, 4, 5, 6]


//for문 조건식 안에 비교할 조건문을 넣어버리면,
//그것을 만족하지 못했을 때 곧바로 반복문이 끝나버리기 때문에 
//내가 구현한 코드에서처럼 break를 따로 써줄 필요가 없었다.

참고문헌

profile
다 늦은 밤, 달밤의 개발일기

0개의 댓글