티스토리 뷰
코딩테스트/알고리즘 & 자료구조 개념
[알고리즘 | JS] sorting algorithm(정렬 알고리즘)3 - insertion sort
blueprint-12 2023. 2. 21. 20:54Insertion sort (삽입 정렬)
삽입 정렬은 버블 정렬 및 선택 정렬과 꽤 비슷하다. 기초 sort 알고리즘으로 이 3가지가 묶임
몇 가지 주요 차이점이 있고, 사실상 삽입 정렬이 더 유리한 지점이 있다.
- 삽입 정렬이 잘 작동하는 상황이 존재한다는 소리 -> 거의 정렬된 데이터에 새로운 데이터가 들어올 때
- 상황 예시: 라이브 & 스트리밍 방식으로 들어온 데이터를 즉시 입력해야 하는 상황, 데이터가 들어와서 계속 재정렬하고 실행중인 정렬을 유지하여 최신 상태로 두어야 할 상황
2. 삽입 정렬의 동작 방식
이 정렬은 배열의 과반을 점차적으로 만들어 정렬을 구축하며, 과반은 항상 정렬되어 있다.
따라서 하나씩 이동하거나, 한 번에 가장 큰 요소를 찾거나 한 번에 가장 작은 요소를 찾는 대신 각 요소를 취하여 정렬되어 있는 절반 속 해당되는 위치에 배치한다.
- 그림을 보면 한 번에 하나의 항목을 올바른 위치에 삽입해서 배열의 정렬도니 부분을 점진적으로 구축하는 것을 볼 수 있다.
- 한 번에 하나의 요소만 취해서 올바른 위치에 삽입하기 때문에 삽입 정렬이라 하는 것이다.
- 유의점: 배열의 가장 맨 처음 요소는 정렬된 부분으로 간주한다.
insertionSort.js
function insertionSort(arr) {
for (var i = 1; i < arr.length; i++) {
var currentVal = arr[i];
for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
arr[j + 1] = arr[j];
console.log(arr);
}
arr[j + 1] = currentVal;
}
return arr;
}
insertionSort([2234, 634, 2, 156, 343]);
- 한번 보고 이해가 잘 가지 않아서 i와 j의 값이 어떻게 들어오는 지 확인해보는 방식이 필요할 거 같다.
3. 삽입 정렬의 시간 복잡도
최적의 경우 O(n) 최악의 경우 O(n^2) 평균적으로 O(n^2)이다.
- 하지만 시간 복잡도는 최악의 경우를 기준으로 간주하기 때문에 O(n^2)가 삽입 정렬의 시간 복잡도이다.
Basic Sorting Algorithms 정리
- 버블 정렬과 삽입 정렬은 데이터가 거의 다 정렬되어 있는 상태라면 좋은 선택이 될 수 있지만 선택 정렬은 그렇지 못하다.
- 선택 정렬의 장점은 이해하기 쉽다는 점이다.
- 삽입 정렬의 특별한 점은 데이터를 계속 정렬해야 할 경우 효과가 좋다는 것이다. 새 요소를 추가할 때, 모든 데이터가 준비된 일종의 일회성 작업일 때를 말한다.
- 위의 3가지 sorting 알고리즘은 아주 작은 데이터 집합에서 잘 작동한다. -> data set이 작을 때, 효과적이다.
'코딩테스트 > 알고리즘 & 자료구조 개념' 카테고리의 다른 글
[알고리즘 | JS] sorting algorithm(정렬 알고리즘)5 - quick sort (1) | 2023.02.23 |
---|---|
[알고리즘 | JS] sorting algorithm(정렬 알고리즘)4 - merge sort (0) | 2023.02.22 |
[알고리즘 | JS] sorting algorithm(정렬 알고리즘)2 - selection sort (1) | 2023.02.21 |
[알고리즘 | JS] sorting algorithm(정렬 알고리즘) - bubble sort (0) | 2023.02.20 |
[알고리즘 | JS] 검색과 검색 알고리즘(search algorithm) (0) | 2023.02.19 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- float 레이아웃
- D 플래그
- 원티드 프리온보딩 FE 챌린지
- is()
- nvm 설치순서
- 틸드와 캐럿
- 타입스크립트 장점
- grid flex
- 원티드 프리온보딩 프론트엔드 챌린지 3일차
- getServerSideProps
- 형제 요소 선택자
- nvm경로 오류
- 부트캠프항해
- 항해99프론트
- fs모듈 넥스트
- 항해99프론트후기
- aspect-ratio
- getStaticPaths
- tilde caret
- && 셸 명령어
- 프리렌더링확인법
- text input pattern
- 항해99추천비추천
- 원티드 FE 프리온보딩 챌린지
- ~ ^
- Prittier
- 원티드 3월 프론트엔드 챌린지
- 프리온보딩 프론트엔드 챌린지 3월
- 타입스크립트 DT
- reactAPI
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
글 보관함