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

 

 

💡 삽입 정렬 (Insertion Sort)

: 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 삽입함으로서 정렬을 완성하는 알고리즘이다. 

 

배열이 길어질수록 효율이 떨어지지만 구현이 간단하다는 장점이 있는 정렬 방법이다. 선택 정렬이나 거품 정렬과 같은 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다.

 

 

insertionSort

문제

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

입력

인자 1 : arr

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

출력

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

주의사항

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

입출력 예시

1
2
let output = insertionSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]

Advanced

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

 

💡 JavaScript 코드

 

1. 두번째 값부터 비교 시작

2. 내 앞에 있는 값들과 비교후, 나보다 크면 내가 앞으로 감.

3. 중간에 콘솔이 찍어보면 위 사진과 똑같이 작동하는 것을 확인할 수 있음.

1) 첫 번째 방법

const insertionSort = function (arr) {
    // TODO: 여기에 코드를 작성합니다.

    for (let i = 1; i < arr.length; i++) {
        let temp = arr[i];
        let prev = i - 1;
        while (prev >= 0 && arr[prev] > temp) {
            arr[prev + 1] = arr[prev];
            prev--;
        }
        arr[prev + 1] = temp;
        console.log(arr);
    }
    return arr;
};

2) 두 번째 방법

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

3) 콜백함수를 이용해서 하는 방법

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

 

아직 갈 길이 멀다고 오늘도 느낀다ㅠㅠ

💡 concat ()

: concat() 메소드는 인자로 주어진 배열이나 값들을 기존 배열에 합쳐서 새 배열을 반환

const array1 = ['a', 'b', 'c'];
const array2 = ['d', 'e', 'f'];
const array3 = array1.concat(array2);

console.log(array3);
// expected output: Array ["a", "b", "c", "d", "e", "f"]

 

💡 slice ()

: slice() 메소드는 어떤 배열의 begin 부터 end까지에 대한 얕은 복사본을 새로운 배열 객체로 반환한다. 원본 배열은 바뀌지 않는다.

const animals = ['ant', 'bison', 'camel', 'duck', 'elephant'];

console.log(animals.slice(2));
// expected output: Array ["camel", "duck", "elephant"]

console.log(animals.slice(2, 4));
// expected output: Array ["camel", "duck"]

console.log(animals.slice(1, 5));
// expected output: Array ["bison", "camel", "duck", "elephant"]

console.log(animals.slice(-2));
// expected output: Array ["duck", "elephant"]

console.log(animals.slice(2, -1));
// expected output: Array ["camel", "duck"]

console.log(animals.slice());
// expected output: Array ["ant", "bison", "camel", "duck", "elephant"]