[JavaScript] 정렬 (3) 선택 정렬과 삽입 정렬

선택 정렬

정의

선택 정렬이란 가장 작은 항목을 찾아서 해당 항목을 배열의 현 위치에 삽입하는 정렬법을 말한다.
앞서 설명했던 거품 정렬보다는 그나마 나은 방법이다.

코드

선택 정렬을 구현하는 코드는 다음과 같다.

function selectionSort(items) {
  
  // 배열간 element를 교환해주는 함수 생성
  const swap = (array, index1, index2) => {
    const temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
  }
  
  let min;
  for (let i=0;i<items.length;i++) {
    min = i;
    // 더 작은 항목이 있는지 배열의 나머지를 확인한다.
    for (let j=i+1;j<items.length;j++) {
      if (items[j] < items[min]) min = j;
    }
    // 현재 위치가 최소항목 위치가 아니라면 항목 교환
    if (i != min) swap(items, i, min);
  }
  return items;
}
  

선택 정렬도 거품정렬과 마찬가지로 이중 반복문을 사용하였기 때문에 시간복잡도는 O(N^2)이다.

삽입 정렬

정의

삽입 정렬이란 배열을 순차적으로 검색하면서 정렬되지 않은 항목들을 배열의 왼쪽의 정렬된 부분으로 이동시키는 정렬방법이다. 아래는 삽입 정렬을 이미지로 나타낸 것이다.

코드

삽입 정렬을 코드 작성하면 다음과 같다.

const insertionSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  
  // value; // 현재 비교중인 값
  // i; // 정렬 X 인덱스
  let j; // 정렬 o 인덱스

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

위의 코드는 선택정렬 함수의 인자에 배열만 들어간 경우이다.
삽입 정렬 함수도 Array.prototype.sort()함수처럼 콜백 함수를 넣을 수도 있다.
아래는 인자로 콜백 함수를 추가한 코드이다.

const insertionSort = function (arr, transform = (item) => item) {
    let sorted = [arr[0]];
    for (let i = 1; i < arr.length; i++) {
      if (transform(arr[i]) >= transform(sorted[i - 1])) {
        sorted.push(arr[i]);
      } else {
        for (let j = 0; j < i; j++) {
          if (transform(arr[i]) <= transform(sorted[j])) {
            const left = sorted.slice(0, j);
            const right = sorted.slice(j);
            sorted = left.concat(arr[i], right);
            break;
          }
        }
      }
    }
  
    return sorted;
  };

위의 코드는 아래의 코드에서 arr[i]부분을 콜백함수의 함수값으로 변형한 것이다.

const insertionSort = function (arr) {
  let sorted = [arr[0]];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] >= sorted[i - 1]) {
      sorted.push(arr[i]);
    } else {
      for (let j = 0; j < i; j++) {
        if (arr[i] <= sorted[j]) {
          const left = sorted.slice(0, j);
          const right = sorted.slice(j);
          sorted = left.concat(arr[i], right);
          break;
        }
      }
    }
  }

  return sorted;
};