삽입정렬(Insertion_Sort)
Wikipedia Insertion_Sort Animation
복잡도
요약
리스트의 1 번째를 선택한 후 선택 수의 이전 번 째까지를 비교해 해당 위치에 값을 삽입.
선택정렬과 유사하나 원하는 위치를 발견 시, 다음 반복으로 넘어간다는 점에서 다르다.
- Can stable
- 대부분 정렬 되어 있을 경우 빠르다.
- 해당 위치 뒤의 배열 값들도 이동시켜야 한다.
( n의 길이에서 i의 위치에 삽입시, n-i ~ n 까지 값의 이동정렬이 필요.
선택정렬(Selection Sort)
Wikipedia Selection Sort Anim
복잡도
요약
리스트의 1번째 요소를 기준으로 배열을 전체 탐색 후 더 작은 값 탐색시 위치 교환.
이를 리스트의 길이 n 번 까지 반복.
- none-stable
- 정해진 횟수
버블정렬(Bubble_Sort)
a b c d e
\1. a - b 교환
\2. b - c 교환
...
복잡도
O(n^2)
요약
인접한 수와 값을 비교하여 위치 교환.
- 선택정렬과 유사하나 자리이동이 많이 일어나 선호하지 않음.
'공부 > 알고리즘공부' 카테고리의 다른 글
| Radix Sort (0) | 2025.04.29 |
|---|---|
| 2진수의 사칙연산 (0) | 2025.03.01 |
| In-place & Stable ? (0) | 2022.05.01 |
| Two Point 알고리즘 (0) | 2022.04.29 |
| 시/공간 복잡도 (0) | 2022.04.23 |