삽입정렬 일반형

while문을 사용한 삽입정렬의 일반형

 

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

 

 

 

for문을 사용하는 경우 아래와 같다.

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

 

 

오름차순 삽입정렬 로직을 가지고 있는, 배열을 파라미터로 받는 함수의 경우 아래와 같은 로직을 가진다.

• 우선 배열을 순회시킨다. 이 때 인덱스 i의 값은 1로 한다.
• key 변수를 선언한다. 이 변수는 현재 정렬 중인 요소를 나타내며 배열에서 i번째 인덱스인 원소를 할당한다.
• j를 선언한다. 이 변수는 정렬된 부분의 요소들과 key를 비교하는 데 사용될 인덱스다. 이 때 값은 i - 1로 한다.
• j를 이용하여 key 값과 정렬된 부분의 요소들을 비교한다. 이 때 비교 조건은 아래와 같다:
  • j는 0보다 크거나 같다.
  • 배열의 j번째 원소의 값은 key보다 크다.
• 만약 배열의 j번째 원소가 위 조건을 충족하면, j+1번째 원소에 j번째 값을 대입한다. 이 경우에는 오름차순이므로 큰 값이 뒤로 가야 하기 때문이다.(따라서 최초 배열이 [5, 2, 4, 6, 1, 3] 였다면 이 과정을 거치며 [5, 5, 4, 6, 1, 3]으로 바뀐다. 큰 값을 오른쪽으로 미는 과정이라고 봐도 좋다). 마지막으로 j--를 사용한다. 이는 정렬된 부분에서 key보다 큰 값들을 오른쪽으로 이동시키면서 동시에 key가 들어갈 적절한 위치를 찾기 위해서다.
• 위 과정을 반복한다. 만약 j가 0보다 작아지거나, 배열의 j번째 원소가 key값보다 크지 않게 된다면 반복을 멈춘다.
• arr[j+1]에 key값을 집어 넣는다. 이 과정에서 감소한 j에 +1을 해줌으로써 정렬된 부분의 올바른 위치에 현재 값이 삽입된다.
• 이 과정을 i가 배열 길이보다 작을 때까지 반복한다.
• 이 과정에서 현재 값인 key는 계속해서 변하게 된다. key는 현재 정렬 중인 요소를 임시로 저장하고, 이를 기준으로 정렬을 수행하는 핵심 변수다.
• 삽입정렬은 제공되는 배열이 정렬돼 있을수록 효율적이 되는데, 그건 내부 반복문의 arr[j] > key 조건 때문에, 아예 내부 반복문 내에 들어오지 않아서 그런 것이다.

추가

• 삽입 정렬은 "제자리 정렬"이라 부른다. 추가 메모리를 거의 안 쓰고 주어진 배열 내에서 정렬한다는 뜻이다.
• 또한 "안정 정렬"이다. 같은 값을 가진 요소들의 순서가 정렬 후에도 바뀌지 않는다는 뜻이다.
• 최선의 경우(이미 정렬된 배열)엔 O(n), 최악의 경우(역순으로 정렬된 배열)엔 O(n²)의 시간 복잡도를 가진다.

 

 

아래는 조금 더 상세히 정렬과정을 관찰하고자 로그를 출력하도록 작성했다.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    console.log("외부 반복문의 i: ", i)
    let key = arr[i];
    console.log("key: ", key)
    let j = i - 1;

    while (j >= 0 && arr[j] > key) {
      console.log("내부 반복문 내의 j: ", j)
      console.log("내부 반복문의 arr[j+1]: ", arr[j + 1])
      console.log("내부 반복문의 arr[j]: ", arr[j])

      arr[j + 1] = arr[j];
      console.log("내부 반복문 arr: ", arr)
      j--;
    }
    console.log("외부 반복문의 j: ", j)
    console.log("**아래: 여기에서 j와 1을 더해줌으로써 위치를 조정한다.")
    console.log("외부 반복문의 arr[j+1]: ", arr[j + 1])
    arr[j + 1] = key;
    // 만약 내부 반복문에 진입하지 않은 경우라면 j가 -1 되지 않았으므로 인덱스의 변경 없이 key값이 할당된다. 따라서 변경되지 않는다.

    console.log("외부 반복문의 arr: ", arr)
    console.log("---------------------------------")

  }

  return arr;
}

let arr = [5, 2, 4, 6, 1, 3];
console.log("Initial array:", arr.join(', '));
insertionSort(arr);
console.log("Sorted array:", arr.join(', '));



/*



Initial array: 5, 2, 4, 6, 1, 3
외부 반복문의 i:  1
key:  2
내부 반복문 내의 j:  0
내부 반복문의 arr[j+1]:  2
내부 반복문의 arr[j]:  5
내부 반복문 arr:  [ 5, 5, 4, 6, 1, 3 ]
외부 반복문의 j:  -1
**아래: 여기에서 j와 1을 더해줌으로써 위치를 조정한다.
외부 반복문의 arr[j+1]:  5
외부 반복문의 arr:  [ 2, 5, 4, 6, 1, 3 ]
---------------------------------
외부 반복문의 i:  2
key:  4
내부 반복문 내의 j:  1
내부 반복문의 arr[j+1]:  4
내부 반복문의 arr[j]:  5
내부 반복문 arr:  [ 2, 5, 5, 6, 1, 3 ]
외부 반복문의 j:  0
**아래: 여기에서 j와 1을 더해줌으로써 위치를 조정한다.
외부 반복문의 arr[j+1]:  5
외부 반복문의 arr:  [ 2, 4, 5, 6, 1, 3 ]
---------------------------------
외부 반복문의 i:  3
key:  6
외부 반복문의 j:  2
**아래: 여기에서 j와 1을 더해줌으로써 위치를 조정한다.
외부 반복문의 arr[j+1]:  6
외부 반복문의 arr:  [ 2, 4, 5, 6, 1, 3 ]
---------------------------------
외부 반복문의 i:  4
key:  1
내부 반복문 내의 j:  3
내부 반복문의 arr[j+1]:  1
내부 반복문의 arr[j]:  6
내부 반복문 arr:  [ 2, 4, 5, 6, 6, 3 ]
내부 반복문 내의 j:  2
내부 반복문의 arr[j+1]:  6
내부 반복문의 arr[j]:  5
내부 반복문 arr:  [ 2, 4, 5, 5, 6, 3 ]
내부 반복문 내의 j:  1
내부 반복문의 arr[j+1]:  5
내부 반복문의 arr[j]:  4
내부 반복문 arr:  [ 2, 4, 4, 5, 6, 3 ]
내부 반복문 내의 j:  0
내부 반복문의 arr[j+1]:  4
내부 반복문의 arr[j]:  2
내부 반복문 arr:  [ 2, 2, 4, 5, 6, 3 ]
외부 반복문의 j:  -1
**아래: 여기에서 j와 1을 더해줌으로써 위치를 조정한다.
외부 반복문의 arr[j+1]:  2
외부 반복문의 arr:  [ 1, 2, 4, 5, 6, 3 ]
---------------------------------
외부 반복문의 i:  5
key:  3
내부 반복문 내의 j:  4
내부 반복문의 arr[j+1]:  3
내부 반복문의 arr[j]:  6
내부 반복문 arr:  [ 1, 2, 4, 5, 6, 6 ]
내부 반복문 내의 j:  3
내부 반복문의 arr[j+1]:  6
내부 반복문의 arr[j]:  5
내부 반복문 arr:  [ 1, 2, 4, 5, 5, 6 ]
내부 반복문 내의 j:  2
내부 반복문의 arr[j+1]:  5
내부 반복문의 arr[j]:  4
내부 반복문 arr:  [ 1, 2, 4, 4, 5, 6 ]
외부 반복문의 j:  1
**아래: 여기에서 j와 1을 더해줌으로써 위치를 조정한다.
외부 반복문의 arr[j+1]:  4
외부 반복문의 arr:  [ 1, 2, 3, 4, 5, 6 ]
---------------------------------
Sorted array: 1, 2, 3, 4, 5, 6
 



*/

 

 

 

내림차순의 경우는

 

 

function insertionSortDescending(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        
        while (j >= 0 && arr[j] < key) {	//여기의 크기비교 조건에서 부등호만 변경하면 된다.
            arr[j + 1] = arr[j];
            j--;
        }
        
        arr[j + 1] = key;
    }
    
    return arr;
}

 

 

 

예제1

//삽입정렬을 사용해 공격력이 높은 유닛이 아래에 오도록 오름차순 정렬하라.
let units = [
  {name: "질럿", attack: 16},
  {name: "드라군", attack: 20},
  {name: "하이템플러", attack: 0},
  {name: "다크템플러", attack: 40},
  {name: "리버", attack: 100},
  {name: "아칸", attack: 30},
]


function insertionSortAsc(arr) {
  const len  = arr.length;

  for(let i = 1; i < len; i++) {
    let key = arr[i];
    let j = i - 1;

    while(j >= 0 && arr[j].attack > key.attack) {
      arr[j + 1] = arr[j];
      j--;
    }

    arr[j+1] = key;
  }

  return arr;
}


console.log(insertionSortAsc(units))


/*

[
  { name: '하이템플러', attack: 0 },
  { name: '질럿', attack: 16 },
  { name: '드라군', attack: 20 },
  { name: '아칸', attack: 30 },
  { name: '다크템플러', attack: 40 },
  { name: '리버', attack: 100 }
]

*/

 

 

예제2

//배틀크루저를 가장 빠르게 잡을 수 있는 유닛

// 일반형: 소,중,대형 크기 모든 유닛에게 100% 대미지
// 진동형: 대형에 25%, 중형에 50%, 소형에 100% 대미지
// 폭발형: 대형에 100%, 중형에 75%, 소형에 50% 대미지

let units = [
  {name: "드라군", mineral: 125, gas: 50, attackSpeed: 1.25, damage: 20, type: "폭발형"},
  {name: "마린", mineral: 50, gas: 0, attackSpeed: 0.625, damage: 6, type: "일반형"},
  {name: "골리앗", mineral: 100, gas: 50, attackSpeed: 0.916, damage: 20, type: "폭발형"},
  {name: "스카웃", mineral: 275, gas: 125, attackSpeed: 0.916, damage: 28, type: "폭발형"},
  {name: "뮤탈리스크", mineral: 100, gas: 100, attackSpeed: 1.25, damage: 9, type: "일반형"},
  {name: "히드라리스크", mineral: 75, gas: 25, attackSpeed: 0.625, damage: 10, type: "폭발형"},
]


const BATTLE_CRUISER = {
  MAX_HP : 500,
  SIZE: "대형"
}

const MY_MINERAL = 500;
const MY_GAS = 500;

function unitsCanBeProduced(unit) {
  const mineralBased = Math.floor(MY_MINERAL/unit.mineral);
  const gasBased = Math.floor(MY_GAS/unit.gas);
  // 적은 값으로 반환한다.
  return Math.min(mineralBased, gasBased);
}

// 타겟에 따라 유닛이 가지는 데미지 계산
function damageCalculator(unit, target) {

  const damageTypes = {
    "일반형" : {"대형" : 1, "중형": 1, "소형": 1},
    "진동형" : {"대형" : 0.25, "중형": 0.5, "소형": 1},
    "폭발형" : {"대형" : 1, "중형": 0.75, "소형": 0.5}
  }

  const damage = unit.damage * damageTypes[unit.type][target.SIZE];
  return damage;
}

function timeToKill (unit, target) {
  const unitsProduced = unitsCanBeProduced(unit);
  const damagePerAttack = unitsProduced * damageCalculator(unit, target);
  return target.MAX_HP / damagePerAttack * unit.attackSpeed;;
}



function insertionSortAsc(arr) {
  const len  = arr.length;

  for(let i = 1; i < len; i++) {
    let key = arr[i];
    let j = i - 1;

    while(j >= 0 && timeToKill(arr[j], BATTLE_CRUISER) > timeToKill(key, BATTLE_CRUISER)) {
      arr[j + 1] = arr[j];
      j--;
    }

    arr[j+1] = key;
  }

  return arr;
}


console.log(insertionSortAsc(units))



/*

[
  {
    name: '골리앗',
    mineral: 100,
    gas: 50,
    attackSpeed: 0.916,
    damage: 20,
    type: '폭발형'
  },
  {
    name: '마린',
    mineral: 50,
    gas: 0,
    attackSpeed: 0.625,
    damage: 6,
    type: '일반형'
  },
  {
    name: '히드라리스크',
    mineral: 75,
    gas: 25,
    attackSpeed: 0.625,
    damage: 10,
    type: '폭발형'
  },
  {
    name: '드라군',
    mineral: 125,
    gas: 50,
    attackSpeed: 1.25,
    damage: 20,
    type: '폭발형'
  },
  {
    name: '뮤탈리스크',
    mineral: 100,
    gas: 100,
    attackSpeed: 1.25,
    damage: 9,
    type: '일반형'
  },
  {
    name: '스카웃',
    mineral: 275,
    gas: 125,
    attackSpeed: 0.916,
    damage: 28,
    type: '폭발형'
  }
]
*/