Toy_ #13. insertionSort
삽입정렬
-
삽입정렬
- 한 번에 한 항목 씩 정렬 된 배열을 작성한다.
- 1회전을 수행할 때마다 인덱스가 증가하며 해당 인덱스까지 요소들의 정렬이 끝난다.
-
시간 복잡도
- 최선의 경우 : O(N)
- 최악의 경우 : O(N^2)
- 평균 : O(N^2)
-
장점
- 안정적인 정렬 알고리즘이다.
- 배열이 대부분 정렬되어 있는 경우에 매우 효율적이다.
-
단점
- 배열 안의 요소들의 이동 수가 많다.
- 배열의 크기가 큰 경우 시간이 오래 걸린다.
문제
정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴한다
주의
- 삽입 정렬을 구현해야 한다.
- 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 풀이가 잘 되지 않았다. 결국 레퍼런스를 참조했다.
- 레퍼런스 코드는 인자로 받은 배열의 요소의 자리를 바꾸는 방식보다는, 따로 aux 배열을 만들었고 인자로 받은 배열의 첫 번째 요소를 넣어 놓고 실제 인자 배열에는 두 번째 요소부터 확인을 한다.
- callback 함수
transform = (item) => item
로 넣는 것이 아직 확실하게 이해가 되지 않지만, 현재 callback의 경우 인자를 값으로 그대로 리턴하기 때문에 callback 함수가 따로 밖에서 지정되지 않을 경우에도 함수 내부의 식이 제대로 돌아가고, 따로 밖에서 지정이 되면 그 callback으로 내부의 식이 돌아간다고 이해가 되었다.
Author And Source
이 문제에 관하여(Toy_ #13. insertionSort), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jonghwan2_y/Toy-13.-insertionSort저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)