삽입 정렬 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번째에 삽입된다.

 

이와 같이 정렬된 왼쪽 배열과 비교해 적절한 위치에 삽입되는 방식으로 정렬된다.

 

 

 

 
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(",");
            }
        }
    }
 
}
 

 

자신과 비교해 필요할 때만 교체가 이루어지기 때문에 정렬이 어느정도 이루어져 있다면 효율적인 방식이다.