Records rather than Memories

삽입 정렬 Insertion sort 본문

Software/JAVA

삽입 정렬 Insertion sort

Downer 2019. 11. 8. 21:01

삽입 정렬은 각 숫자를 왼쪽 인덱스 값들과 비교해 적절한 위치에 삽입하는 방식으로 정렬하게 된다. 필요할 때만 위치를 바꾸며 한 번 위치를 바꿀 때 마다 왼쪽 값들은 정렬이 된다.

 

다음과 같이 무작위로 섞인 배열이 있을 때 오름차순으로 정렬하려고 한다.

 

 

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 = {4103168};
        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