[알고리즘 개념] Insertion Sort 삽입정렬 알고리즘 - JAVA

1. 삽입정렬 개념

- 배열의 모든 요소를 바로 왼쪽의 요소와 차례대로 비교하며 자신의 위치를 찾아 삽입한다.

- 배열의 두 번째 요소부터 연산을 시작한다. (바로 왼쪽의 요소와 비교해야 하므로)

- 시간 복잡도 : O(n^2)

아래와 같이 int형 배열이 주어져있을 때 <삽입정렬>로 정렬해보자

4

2

3

5

1

1)

아래와 같이 바로 왼쪽의 요소와 비교해야 하므로 배열의 arr[1](두 번째 요소)부터 연산을 시작한다.

우선, arr[1]의 값인 기준값 2를 temp라는 변수에 저장한다. (int temp = arr[1])

temp

2

아래와 같이 temp와 arr[1]의 바로 왼쪽 요소인 arr[0] 값을 비교하고, 4가 temp값인 2보다 더 크기 때문에 4를 arr[1] 자리에 넣는다. (arr[1] = arr[0])

temp

2

4

2

3

5

1

4

4

3

5

1

그 다음은 왼쪽에 더 비교할 값이 없기 때문에 아래와 같이 temp 값을 arr[0]에 넣는다. (arr[0] = temp)

temp

2

2

4

3

5

1

2)

그 다음은 배열의 arr[2]의 연산을 시작한다.

우선, arr[2]의 값인 기준값 3를 temp라는 변수에 저장한다. (int temp = arr[2])

temp

3

아래와 같이 temp와 arr[2]의 바로 왼쪽 요소인 arr[1] 값을 비교하고, 4가 temp값인 3보다 더 크기 때문에 4를 arr[2] 자리에 넣는다. (arr[2] = arr[1])

temp

3

2

4

3

5

1

2

4

4

5

1

그 다음은 아래와 같이 temp와 arr[0] 값을 비교하고, 2는 temp 값인 3보다 더 크지 않기 때문에 temp 값인 3을 arr[1] 자리에 넣는다. (arr[1] = temp)

temp

3

2

4

4

5

1

2

3

4

5

1

3)

그 다음은 배열의 arr[3]의 연산을 시작한다.

우선, arr[3]의 값인 기준값 5를 temp라는 변수에 저장한다. (int temp = arr[3])

temp

5

아래와 같이 temp와 arr[3]의 바로 왼쪽 요소인 arr[2] 값을 비교하고, 4가 temp값인 5보다 크지 않기 때문에 5를 그대로 arr[3] 자리에 넣는다. (arr[3] = temp)

temp

5

2

3

4

5

1

3)

그 다음은 배열의 arr[4]의 연산을 시작한다.

우선, arr[4]의 값인 기준값 1을 temp라는 변수에 저장한다. (int temp = arr[4])

temp

1

아래와 같이 temp와 arr[4]의 바로 왼쪽 요소인 arr[3] 값을 비교하고, 5가 temp값인 1보다 더 크기때문에 5를 arr[4] 자리에 넣는다. (arr[4] = arr[3])

temp

1

2

3

4

5

1

2

3

4

5

5

그 다음은 아래와 같이 temp와 arr[2] 값을 비교하고, 4가 temp값인 1보다 더 크기때문에 4를 arr[3] 자리에 넣는다. (arr[3] = arr[2])

temp

1

2

3

4

5

5

2

3

4

4

5

그 다음은 아래와 같이 temp와 arr[1] 값을 비교하고, 4가 temp값인 1보다 더 크기때문에 4를 arr[2] 자리에 넣는다. (arr[2] = arr[1])

temp

1

2

3

4

4

5

2

3

3

4

5

그 다음은 아래와 같이 temp와 arr[0] 값을 비교하고, 2가 temp값인 1보다 더 크기때문에 2를 arr[3] 자리에 넣는다. (arr[1] = arr[0])

temp

1

2

3

4

4

5

2

2

3

4

5

그 다음은 왼쪽에 더 비교할 값이 없기 때문에 아래와 같이 temp 값을 arr[0]에 넣는다. (arr[0] = temp)

temp

1

2

2

3

4

5

1

2

3

4

5

2. 예제

public class Main {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        Scanner sc = new Scanner(System.in);
 
        int[] intArr = new int[5]; //크기가 5인 int형 배열 생성         
        
        for(int i=0; i<5; i++) {
            intArr[i] = sc.nextInt(); //숫자들을 입력받아 배열에 저장 
        }
        
        insertionSort(intArr); //삽입정렬 함수 호출
        
        for(int i=0; i<caseNum; i++) {
            System.out.println(intArr[i]); //배열 요소 출력  
        }
 
    }
    
    //삽입 정렬 
    public static int[] insertionSort(int[] arr) {
        for(int i=1; i<arr.length; i++) {
            int temp = arr[i];  //연산 할 기준값을 temp에 저장
            int aux = i-1;  //비교할 요소의 인덱스 값
            
            while(aux >= 0 && arr[aux] > temp) {
                arr[aux+1] = arr[aux];  //왼쪽의 값이 오른쪽의 값보다 클 경우 왼쪽 값을 오른쪽으로 이동
                aux--;  //비교할 요소의 인덱스 값을 하나 감소시킴
            }
            arr[aux+1] = temp;  //비교할 요소의 인덱스 값이 0보다 작게 되었거나 temp값이 더 클 경우 temp값을 저장
        }
        
        return arr;
    }
 
}