Algorithm problem-13

1. 문제

• 삽입 정렬로 오름차순 정렬한 배열을 리턴

2. 시도

• 처음에는 0번을 기준으로 잡고 크면 뒤에, 작으면 앞에 넣도록 풀이하였었음
• 마지막 문항의 시간복잡도를 해결하지 못하였음
• 삽입 정렬의 개념을 이해하려고 구글링을 하다가 다른 언어로 풀이한 내용을 읽음
• 그 내용을 바탕으로 문제를 풀이하였음

3. 수도코드

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

4. 레퍼런스

const insertionSort = function (arr, callback = (n) => n) {
  // 기준을 잡아주기 위해 0번값을 넣고 시작
  let sorted = [arr[0]];
  // 1번부터 시작하여 모든 배열을 순회한다
  for (let i = 1; i < arr.length; i++) {
    // callback 형태로 리턴값을 기준으로 비교한다
    // 배열의 i값과 정렬배열의 i-1 값을 비교하고
    // 크거나 같으면 정렬상태이므로 뒤에 푸쉬 해준다
    if (callback(arr[i]) >= callback(sorted[i - 1])) {
      sorted.push(arr[i]);
    } // 아닌 경우, 즉 작은 경우에는 중간에 삽입해야 하므로
    else { // 정렬배열의 0번부터 i-1번까지의 값들과 비교하여 중간에 넣어준다
      for (let j = 0; j < i; j++) {
        if (callback(arr[i]) <= callback(sorted[j])) {
          const front = sorted.slice(0, j)
          const rear = sorted.slice(j)
          sorted = front.concat(arr[i], rear)
          break; // 정렬 상태에서 위치를 찾아서 넣었으니 브레이크 해준다
        }
      }
    }
  } // 정렬배열을 리턴해준다
  return sorted;
};