삽입 정렬이 무엇일까

2023/02/16

4 min read

COMPUTERSCIENCE

삽입 정렬

배열의 두 번째 요소부터 루프를 시작한다 선택한 요소를 이전에 있는 요소들과 비교하면서 선택한 요소보다 작다면 뒤에 위치시킨다 선택한 요소보다 크다면 앞에 위치시킨다

[2,1,9,76,4] 배열을 정렬해보자

[2,1,9,76,4] 1은 2보다 작으니 앞으로 위치시킨다
[1,2,9,76,4] 9는 2보다 크니 뒤에 위치시킨다
[1,2,9,76,4] 76은 9보다 크니 뒤에 위치시킨다
[1,2,4,9,76] 4는 2보다 크니 뒤에 위치시킨다

이런식으로 정렬이 된다

코드로 살펴보자

1
function insertionSort(arr) {
2
  for (let i = 1; i < arr.length; i++) {
3
    let currentValue = arr[i];
4
    let j;
5
    for (j = i - 1; j >= 0 && arr[j] > currentValue; j--) {
6
      arr[j + 1] = arr[j];
7
    }
8
    arr[j + 1] = currentValue;
9
  }
10
  return arr;
11
}

첫 번째 루프이다 첫 번째 루프는 두 번째 요소부터 돌아야 하니 i의 초깃값은 1로 둔다

비교 대상인 값을 currentValue 변수에 할당해 준다 currentValue의 이전의 값들과 비교를 해야 하니 루프를 하나 더 생성해 준다

두번째 루프이다 j는 i-1값을 가진다
루프 조건은 j가 0보다 크거나 같아야 하고, arr[j]는 currentValue보다 커야 한다 j는 루프 밖에서로 사용해야하니 밖으로 꺼내주었다

두 번째 루프 조건에 해당한다면 j의 위치보다 +1 위치에 j의 값을 넣어둔다

그 후에 arr[j+1] 위치에 currentValue값을 넣어준다

여기서 조금 헷갈릴 것 같다

어떻게 움직이는지 보면 쉽게 이해할 수 있을 것이다

예를 들어 [1,2,9,76,4] 배열이고 현재 i는 마지막 index이다 그러므로 currentValue는 4이다 두 번째 루프를 실행해보자

j는 i -1이므로 76과 currentValue인 4를 비교한다 76은 4보다 크기 때문에 두 번째 루프 조건을 충족하여 로직을 실행시키게 된다 arr[j+1] 자리에 arr[j]를 할당한다 그러면 값은 다음과 같다 [1,2,9,76,76] 그다음 루프로 가자
j는 9를 가리킨다 9는 currentValue인 4보다 크기 때문에 루프 조건에 충족하여 로직을 실행시킨다 arr[j+1] 자리에 arr[j]를 할당한다 [1,2,9,9,76] 그다음 루프로 가자
j는 2를 가리키고 있다 2는 currentValue인 4보다 작기 때문에 루프 조건에 충족하지 않아 다음 줄로 간다 arr[j+1]에 currentValue를 집어넣어 준다 j는 현재 2를 가리키고 있고 index +1을 하게 되면 2 다음인 9를 가지고 있는 index에 currentValue인 4를 넣어준다 결과는 [1,2,4,9,76] 나온다

한동룡