728x90
1. 삽입 정렬
- 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식이다.
- 구현이 쉽다.
- 시간 복잡도가 O(n²)으로 느리다.
2. 삽입 정렬 과정
- 현재 index에 있는 데이터 값 선택
- 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색
- 삽입 위치부터 index에 있는 위치까지 shift 연산을 수행
- 삽입 위치에 현재 선택한 데이터를 삽입하고 index++
- 전체 데이터의 크기만큼 index가 커질 때까지 반복
적절한 삽입 위치를 찾는 부분에서 이진 탐색 알고리즘을 사용하면 시간 복잡도를 줄일 수 있다.
3. 예제 문제
[11399] ATM (JAVA)
# 문제 설명 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.
spicyrisotto.tistory.com
[24051] 알고리즘 수업 - 삽입 정렬 1 (JAVA)
# 문제 설명 오늘도 서준이는 삽입 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 서로 다른 양의 정수가 저장된 배열 A가 있다.
spicyrisotto.tistory.com
728x90
'책 > Do it! 알고리즘 코딩 테스트 자바 편' 카테고리의 다른 글
| Day-7 병합 정렬 (0) | 2024.03.27 |
|---|---|
| Day-6 퀵 정렬 (0) | 2024.03.27 |
| Day-5 선택 정렬 (0) | 2024.03.23 |
| Day-5 버블 정렬 (0) | 2024.03.22 |
| Day-4 스택과 큐 (0) | 2024.03.21 |
