Toy_ #13. insertionSort

삽입정렬

• 삽입정렬

  • 한 번에 한 항목 씩 정렬 된 배열을 작성한다.
  • 1회전을 수행할 때마다 인덱스가 증가하며 해당 인덱스까지 요소들의 정렬이 끝난다.

• 시간 복잡도

  • 최선의 경우 : O(N)
  • 최악의 경우 : O(N^2)
  • 평균 : O(N^2)

• 장점

  • 안정적인 정렬 알고리즘이다.
  • 배열이 대부분 정렬되어 있는 경우에 매우 효율적이다.

• 단점

  • 배열 안의 요소들의 이동 수가 많다.
  • 배열의 크기가 큰 경우 시간이 오래 걸린다.

참고링크: yujo님 벨로그

문제

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴한다

주의

• 삽입 정렬을 구현해야 한다.
• arr.sort 사용은 금지된다.
• (advanced) insertionSort 함수의 두 번째 인자로 callback 함수를 받아서, 그 함수의 리턴값을 기준으로 요소들을 정렬한다.

풀이

const insertionSort = function (arr, transform = (item) => item) {

  // 두 번째 인덱스 수부터 바로 앞 인덱스의 값과 비교하여 정렬한다.

  let aux = [arr[0]];
  // 비교할 첫 번째 요소는 따로 선언해 놓는다.

  for(let i = 1; i < arr.length; i++) {
    if (transform(arr[i]) >= transform(aux[i - 1])) {
      // 현재 요소 값이 비교할 앞 인덱스의 요소보다 크면, 현재 요소 값을 따로 선언한 배열에 push한다.
      aux.push(arr[i])
    }
    else {
      for (let j = 0; j < i; j++) {
        // 그렇지 않은 경우 aux의 배열의 길이만큼 (i의 숫자 크기만큼) for문을 돌려
        if (transform(arr[i]) <= transform(aux[j])) {
          // aux의 전체 요소값 중에 현재 요소 값보다 큰 값이 있는 경우
          const left = aux.slice(0, j);
          // 해당 현재 요소 값을 해당 큰 값 바로 앞에 끼워 넣어야 한다.
          // 큰 값 바로 앞 left
          const right = aux.slice(j);
          // 큰 값 바로 뒤 right로 선언하고
          aux = left.concat(arr[i], right)
          // 사이에 현재 요소 값을 넣어 준다.
          break;
          // swap한 후 else 반복문을 멈춘다.
        }
      }
    }
  }
  return aux
};

삽입 정렬에 대해 공부를 하고 요소의 값을 비교하며 swap하는 방식으로 문제를 풀을려고 했지만 advanced 풀이가 잘 되지 않았다. 결국 레퍼런스를 참조했다.

1. 레퍼런스 코드는 인자로 받은 배열의 요소의 자리를 바꾸는 방식보다는, 따로 aux 배열을 만들었고 인자로 받은 배열의 첫 번째 요소를 넣어 놓고 실제 인자 배열에는 두 번째 요소부터 확인을 한다.

2. callback 함수 transform = (item) => item로 넣는 것이 아직 확실하게 이해가 되지 않지만, 현재 callback의 경우 인자를 값으로 그대로 리턴하기 때문에 callback 함수가 따로 밖에서 지정되지 않을 경우에도 함수 내부의 식이 제대로 돌아가고, 따로 밖에서 지정이 되면 그 callback으로 내부의 식이 돌아간다고 이해가 되었다.