Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- C++
- 코로나19
- know
- 형변환
- if조건절
- 변수
- 게임QA
- keep -ing
- counldn't have
- end up ing
- Realtime Rendering
- html
- I'm glad
- it's a good thing
- by until
- ISTQB
- java
- for ing
- 제5인격
- gameQA
- happen to
- continue to
- by any chance
- 명세기반테스트
- UE4
- might have p.p
- sort함수
- metascore
- 명절 표현
- relif
Archives
- Today
- Total
Records rather than Memories
삽입 정렬 Insertion sort 본문
삽입 정렬은 각 숫자를 왼쪽 인덱스 값들과 비교해 적절한 위치에 삽입하는 방식으로 정렬하게 된다. 필요할 때만 위치를 바꾸며 한 번 위치를 바꿀 때 마다 왼쪽 값들은 정렬이 된다.
다음과 같이 무작위로 섞인 배열이 있을 때 오름차순으로 정렬하려고 한다.
1. 0번째 인덱스 값인 4를 정렬이 된 수라고 가정하고 1번 째 값인 10과 비교한다.
4 < 10 이므로 그대로 둔다.
2. 1번 째 인덱스 값인 3과 0번 째 3, 1번 째 10을 비교한다.
3 < 4, 10 이므로 0번 째와 바꾼다.
3. 3번째 인덱스 1과 왼쪽 배열 3, 4, 10을 비교해 0번째에 삽입된다.
이와 같이 정렬된 왼쪽 배열과 비교해 적절한 위치에 삽입되는 방식으로 정렬된다.
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
|
public class Insertionsort {
public void sort(int[] data) {
int temp;
int size = data.length;
for(int i=1; i<size; i++) {
for(int j=i; j>0; j--) {
if(data[j]<data[j-1]) {
temp = data[j];
data[j] = data[j-1];
data[j-1] = temp;
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Insertionsort numbers = new Insertionsort();
int[] data = {4, 10, 3, 1, 6, 8};
numbers.sort(data);
for(int i=0; i < data.length; i++) {
System.out.print(data[i]);
if(i != data.length-1) {
System.out.print(",");
}
}
}
}
|
cs |
첫 번째 for문에서 i는 정렬된 왼쪽의 배열 칸을 하나씩 늘림과 동시에 비교해야할 대상을 하나씩 늘려준다.
두 번째 for문에서는 현재 인덱스 값에서 왼쪽에 있는 값들을 하나씩 비교하며 만약 자신보다 큰 값이 있다면 자신과 바꾼다.
자신과 비교해 필요할 때만 교체가 이루어지기 때문에 정렬이 어느정도 이루어져 있다면 효율적인 방식이다.
'Software > JAVA' 카테고리의 다른 글
합병 정렬 Merge sort (0) | 2019.11.09 |
---|---|
퀵 정렬 Quick sort (0) | 2019.11.08 |
버블 정렬 Bubble sort (0) | 2019.11.07 |
선택정렬 Selection sort (0) | 2019.11.07 |
Object 자바에서 Object라는 클래스는? (0) | 2019.11.06 |
Comments