201230 - 알고리즘

[토이13]

insertionSort

문제
정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.

입력
인자 1 : arr
number 타입을 요소로 갖는 배열
arr[i]는 정수
arr.length는 1,000 이하

출력
number 타입을 요소로 갖는 배열을 리턴해야 합니다.
배열의 요소는 오름차순으로 정렬되어야 합니다.
arr[i] <= arr[j] (i < j)

주의사항
삽입 정렬을 구현해야 합니다.
arr.sort 사용은 금지됩니다.
입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

Advanced
insertionSort 함수의 두 번째 인자로 callback 함수를 받아서, 그 함수의 리턴값을 기준으로 요소들을 정렬해 보세요.

나의 답

const insertionSort = function (arr) {
  for (let i = 1; i < arr.length; i++) {
    let 현재값 = arr[i]
    let 정렬된부분의현재인덱스 = i - 1
    while (정렬된부분의현재인덱스 >= 0 && arr[정렬된부분의현재인덱스] > 현재값) {
      arr[정렬된부분의현재인덱스 + 1] = arr[정렬된부분의현재인덱스]
      정렬된부분의현재인덱스--
    }
    arr[정렬된부분의현재인덱스 +1] = 현재값
  }
  return arr
};

ref

// naive solution /////////////////////////////////////////////////
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;
};

///////////////////////////////////////////////////////////////////
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;
};

삽입정렬

• 여러개의 섞인 숫자들을, 작은 숫자부터 순서대로 정렬하는 것
• 처음 숫자는 고정하고 그 다음숫자부터 이전에 있던 숫자들과의 크기를 비교해서 알맞은 자리에 정렬한다. (반복)