[JavaScript 알고리즘] 정렬(Sorting) - 3. Insertion Sort

여러분 호옥시 반장하셨거나 과대하셨거나, 아니면 선생님이시거나 하신 분들,

번호순서대로 과제 취합해보신 적 있으신가요?

 

일단 다 걷어놓고 1번부터 끝번호까지 정렬할 때,

우리는 Insertion Sort를 씁니다.

 

Insertion Sort에 대해서 배워보겠습니다.

https://visualgo.net/en/sorting

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

Insertion Sort가 어떻게 동작하는지 보고 오세요.

번호순으로 과제 정리하던 때가 떠오르시죠?

 

[3,44,38,5,47,15] 이 사람들의 과제를 정리해봅시다.

자 어찌됐든 앞이 적은 번호, 뒤가 큰 번호 순으로 갈테니까 일단 3 뒤에 44를 놓자.

어? 38은 44보다 작으니까 44 앞에 놓고..

5번은 44보다 작은 38보다 작네?

하지만 3보다 크니까 딱 28 앞에다 놓으면 되겠다.

47은 44보다 크네? 오키 그럼 여기.

15는 47보다 작은 44보다 작은 38보다 작네?,

하지만 5보다 크니까 딱 38 앞에다 놓자.

 

이게 바로 Insertion Sort입니다.

 

의사코드

배열에서 두번째 요소를 집어드는 걸로 시작해요.

이제 그 두번째 요소와 그 바로 앞의 요소를 비교해요. 필요하다면 Swap합시다!

그 다음 요소를 집어듭시다.

왼쪽 방향으로 계속 비교합니다. 그리고 왼쪽이 작고 오른쪽이 크게 되는 자리로 그 요소를 배치합니다.

모두 정렬될 때까지 반복합니다. 

 

 

function insertionSort(arr) {
  for(let i = 1; i < arr.length; i++) {
    let currentVal = arr[i];
    console.log(`currentVal : ${currentVal}`);
    
    for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
      console.log(`the original arr is ${arr}`);
      console.log(`${arr[j+1]} has replaced to ${arr[j]}!`);
      arr[j+1] = arr[j];
      
      console.log(`now, the arr is ${arr}`);
    }
    console.log(`${arr[j+1]} has replaced to currentVal:${currentVal}!`);
    arr[j+1] = currentVal;
    
    console.log(arr);
  }
  return arr;
}

// IDE에 옮겨서 실행해보세요! 어떻게 동작되는지 console에서 알 수 있습니다.

 

아래와 같이 구현할 수도 있네요

function insertionSort2(arr) {
  for(let i = 1; i < arr.length; i++) {
    let currentVal = arr[i];
    console.log(`currentVal : ${currentVal}`);
    
    for(var j = i - 1; j >= 0 && currentVal < arr[j]; j--) {
      console.log(`the original arr is ${arr}`);
      console.log(`${arr[j]} has replaced to ${arr[j+1]}!`);
      console.log(`${arr[j+1]} has replaced to currentVal:${currentVal}!`);
      let temp = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = temp;
      
      console.log(`now, the arr is ${arr}`);
    }
    console.log(arr);
  }
  return arr;
}

insertionSort2([2,1,9,76,4]);

 

 

Insertion Sort의 Big O Notation은

O(n^2)입니다 ^^