728x90
https://www.youtube.com/watch?v=DRkL5EBZ7KY&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=22
삽입 정렬
- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다
- 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다
삽입 정렬 동작 예시
- [Step 0] 첫 번째 데이터 '7'은 그 자체로 정렬이 되어 있다고 판단하고, 두 번째 데이터인 '5'가 어떤 위치로
들어갈지 판단한다. '7'의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재한다
- [Step 1] 이어서 '9'가 어떤 위치로 들어갈지 판단한다
- [Step 2] 이어서 '0'이 어떤 위치로 들어갈지 판단한다
- [Step 3] 이어서 '3'이 어떤 위치로 들어갈지 판단한다
- 이러한 과정을 반복하면 다음과 같이 정렬이 완료된다
삽입 정렬 소스코드 (Python)
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)):
for j in range(i, 0, -1): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
array[j], array[j - 1] = array[j - 1], array[j]
else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
break
print(array)
실행 결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
삽입 정렬 소스코드 (Java)
import java.util.*;
public class Main {
public static void main(String[] args) {
int n = 10;
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
for (int i = 1; i < n; i++) {
// 인덱스 i부터 1까지 감소하며 반복하는 문법
for (int j = i; j > 0; j--) {
// 한 칸씩 왼쪽으로 이동
if (arr[j] < arr[j - 1]) {
// 스와프(Swap)
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
// 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
else break;
}
}
for(int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}
실행 결과
0 1 2 3 4 5 6 7 8 9
삽입 정렬의 시간 복잡도
- 삽입 정렬의 시간 복잡도는 O(N²) 이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용된다
- 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다
- 최선의 경우 O(N) 의 시간 복잡도를 가진다
- 이미 정렬되어 있는 상태에서 다시 삽입 정렬을 수행하면 어떻게 될까?
728x90
'CodingTest' 카테고리의 다른 글
[이것이 코딩 테스트다 with Python] 24강 계수 정렬 (0) | 2021.01.04 |
---|---|
[이것이 코딩 테스트다 with Python] 23강 퀵 정렬 (0) | 2021.01.04 |
[이것이 코딩 테스트다 with Python] 21강 선택 정렬 (0) | 2021.01.04 |
[이것이 코딩 테스트다 with Python] 20강 DFS & BFS 기초 문제 풀이 (0) | 2021.01.04 |
[이것이 코딩 테스트다 with Python] 19강 BFS 알고리즘 (0) | 2021.01.04 |
댓글