삽입정렬

삽입정렬:

배열의 모든 요소를 현재 위치보다 아래(현재 위치보다 아래의 값들은 이미 정렬된 배열이다.)의 값들과 (대소)비교해가면서,

현재값의 알맞은 위치를 찾아서 넣어줌(삽입) 으로써 정렬하는 알고리즘 

1) 원리

•  배열의 모든 요소에 대해서 위의 정의를 진행한다. 
•  맨 첫번째 값은 자신의 위치(currIndex:0)보다 아래의 위치가 없으니까 두번째 값(currIndex:1)부터 시작한다. 
•  1. 자신의 위치(currIndex)의 아래 위치((currIndex-1)~0)의 값을 자신과 비교한다. 
•  2. 오름차순으로 정렬할 것이면,
  • 2-1. 자신의 값이 아래위치의 값보다 작으면 자신은 그보다 이전의 자리에 위치해야하므로 아래위치의 값을 뒤로 보낸다. 
  •  2-2. 반대로 자신의 값이 아래위치의 값보다 크면 그 자리가 알맞은 자리라는 뜻이므로 자리를 바꿀 필요 없이 다음 차례의 currIndex로 가서 1~2을 반복한다. 
•  이렇게 배열의 모든 요소에 대해서 1~2를 진행하면 정렬이 끝난다. 

출처: https://godgod732.tistory.com/12

2) 구현 - 오름차순 기준

방법 1. 2중 for문 사용

1. 배열의 모든 요소에 대해서 위의 정의를 진행한다. 첫번째 값은 자신의 위치(currIndex:0)보다 아래의 위치가 없으니까 두번째 값(currIndex:1)부터 시작한다.  for(let i=1; i<array.length; i++)

2. 자신의 위치(currIndex)의 아래 위치((currIndex-1)~0)의 값을 자신과 비교한다. 

2-1. 자신보다 큰 값이면 자리 바꾸기 => 이때 자신보다 작은 값이 나올 때까지 계속해서 자신 앞에 있는 숫자과 비교해가면서 자리 바꾸는걸 반복

2-2. 자신보다 작은 값이 나오면 아무것도 하지 않고 다음 차례로!

javascript code

var insertionSort = function (array) {
  for (let i = 1; i < array.length; i++) {
    let inx = i
    for (let j = i - 1; j >= 0; j--) {
      if (array[inx].value < array[j].value) {
        let temp = array[j]
        array[j] = array[inx]
        array[inx] = temp
        inx = j
      } else {
        break
      }
    }
  }
  return array
}

방법2. while문 사용

1. 그런데 크게보면 삽입정렬은 그냥 현재 값이 자신의 앞에 있는 숫자들을 쭉~ 보고 알맞은 자신의 자리를 찾아가는 것이다.

2. 그래서 while문 안에서 자신보다 큰 것은 뒤로 계속 밀면서 알맞은 자리를 찾아주는 과정이 이루어진다. 그리고 딱 찾았을때!

3. while문을 벗어나서 그 자리에 나를 넣는다.

var insertionSort = function (array) {
  for (let i = 1; i < array.length; i++) {
    let curr = array[i]
    let j = i
    while (j > 0 && curr < array[j - 1]) {
      array[j] = array[j - 1]
      j--
    }
    array[j] = curr
  }
  return array
}

3) 시간 복잡도

최선의 경우: 이미 정렬이 되어있다면? 모두 아래의 부분에 걸릴 것이기 때문에 O(n)

else{ //2-2. 자신보다 작은 값이 나오면 아무것도 하지 않고 다음 차례로!
    break
}

최악의 경우: 정렬 기준의 역순으로 정렬되어 있다면?

이만큼씩 다 돌면서 

for(let i=1; i<array.length; i++)

한번도 break되는 일 없이

for(let j=i-1; i>=0; i--){

이걸 모두 돌아야하므로 O(n^2)

 

지금까지 삽입정렬 알고리즘에 대해 정리해 보았다.

아래는 알고리즘 공부필기본이다.

 

꼭 백지코딩으로 복습해보자! (이것 모두 나 자신에게 하는 말 입니더..)

 

Reference

gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html