반응형
2021.08.23 - [자료구조 & 알고리즘] - [알고리즘] 정렬
📎 삽입 정렬
삽입 정렬은 선택한 요소를 앞쪽의 알맞은 위치로 삽입해 정렬하는 알고리즘이다.
이는 사람들이 생각하는 가장 일반적인 정렬이다.
선택 정렬과 비슷해보이지만 선택 정렬은 먼저 가장 최솟값을 선택하고 앞쪽 요소와 SWAP하는 방식이고
삽입 정렬은 두번째 위치한 요소부터 앞쪽 요소들과 비교, 정렬해 알맞은 자리로 삽입하는 방식이다.
삽입정렬의 과정
- 배열의 두번째 요소부터 선택
- 선택한 요소보다 앞쪽에 위치한 요소들과 비교해 알맞은 자리로 삽입
- 마지막 요소까지 반복
자바 코드로 구현해보면 이렇게 된다.
|
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
import java.util.Scanner;
public class InsertionSort {
/*
* 삽입 정렬 : 선택한 요소를 앞쪽의 알맞은 위치로 삽입해 정렬하는 알고리즘
* 일반적인 삽입 정렬의 시간 복잡도는 O(n²)
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("정렬할 요소의 수: ");
int n = sc.nextInt();
int[] arr = new int[n];
//요소 입력받음
for(int i=0; i<n; i++) {
arr[i]=sc.nextInt();
}
sc.close();
insertionSort(arr, n);
System.out.println("삽입 정렬 완료");
//정렬 후 출력
for(int i=0; i<n; i++) {
System.out.print(arr[i]+" ");
}
}
static void insertionSort(int[] arr, int n) {
//두번째 위치한 요소부터 시작
//n개의 요소 -> n번 수행 -> n+1번이면 반복 종료 for(int i=1; i<n; i++) {
int j = i-1;
int tmp = arr[i];
//선택한 i 보다 앞쪽에 위치한 요소들 비교
for(j=i; j>0 && arr[j-1]>tmp; j--) {
//i보다 작으면 요소의 위치를 하나씩 뒤로 보냄
arr[j] = arr[j-1];
}
arr[j] = tmp; //앞쪽 자리는 선택된 요소 i가 차지
}
}
}
|
cs |
|
|
|
삽입 정렬의 성능 분석
삽입 정렬의 시간 복잡도는 O(n²) 이다.
최악의 경우가 n(n-1)/2 로 다른 O(n²) 정렬보다 빠른편이다.
특히 배열의 길이가 작으면 작을 수록 삽입 정렬의 성능은 높아진다.
삽입정렬은 이 반복문의 수행 횟수에 따라 성능이 결정된다.
|
1
2
3
4
5
6
|
//선택한 i 보다 앞쪽에 위치한 요소들 비교
for(j=i; j>0 && arr[j-1]>tmp; j--) {
//i보다 작으면 요소의 위치를 하나씩 뒤로 보냄
arr[j] = arr[j-1];
}
arr[j] = tmp; //앞쪽 자리는 선택된 요소 i가 차지
|
cs |
최선은 배열이 이미 오름차순으로 정렬된 경우이고
최악은 배열이 반대 순서로(내림차순) 정렬되어 있는 경우이다.
이는 앞쪽의 모든 요소를 비교해야해 수행 횟수가 많아지기 때문이다.
반응형
'자료구조 & 알고리즘' 카테고리의 다른 글
| [알고리즘] 다이나믹 프로그래밍 (동적 계획법) (1) | 2021.09.09 |
|---|---|
| [정렬 알고리즘] 병합 정렬 (합병 정렬) (0) | 2021.09.09 |
| [정렬 알고리즘] 버블 정렬 (0) | 2021.09.08 |
| [정렬 알고리즘] 선택 정렬 (0) | 2021.09.07 |
| [알고리즘] 정렬 (0) | 2021.08.23 |
댓글