[알고리즘] 정렬 - 삽입정렬

1. 개념

배열의 원소를 하나씩 살피면서, 살피는 원소와 살피는 원소 앞에 있는 원소를 비교해서 만약 앞에 있는 원소보다 작다면 살피는 원소를 앞으로 보낸다. 더 이상 앞으로 보낼 수 없을 때까지 반복한다.(오름차순 기준)

 

2. 특징

1) 장점

• 안정한 정렬 방법(정렬하면서 같은 원소가 있어도 위치가 변하지 않는다)
• 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.
• 대부분위 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.

2) 단점

• 비교적 많은 레코드들의 이동을 포함한다.
• 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다.
  
  

3.  시간복잡도

1) 최선(다 정렬되어 들어올 경우)

• 비교횟수
  • target이 target 바로 전 것과 비교되고 비교가 끝나는데, target 시작이 인덱스 1부터니 n-1번, O(n)
• 교환횟수
  • 없음

2) 최악(역순일 경우)

• 비교횟수

첫 번째 target의 비교 횟수 1

두 번째 target의 비교 횟수 2

...

마지막 target의 비교 횟수 n-1

1+2+...+n-1 = n(n-1)/2 -> O(n2)

• 교환횟수

첫 번째 target의 교환 횟수 1

두 번째 target의 교환 횟수 2

...

마지막 target의 교환 횟수 n-1

1+2+...+n-1 = n(n-1)/2 -> O(n2)

 

최선의 시간복잡도는 O(n)

최악의 시간복잡도는 O(n2)

 

4. 코드

// 삽입 정렬 오름차순
public class HelloWorld{

     public static void main(String []args){
        int[] numbers = {3,4,2,6,1};
        
        for(int i = 1; i<numbers.length; i++){
            int target = numbers[i];
            int j = i-1;
            
            while(j >= 0 && target < numbers[j]){
                numbers[j+1] = numbers[j];
                j--;
            }
            
            numbers[j+1] = target; 
        }
        
        
        for(int num : numbers){
            System.out.println(num);
        }
     }
}

// 삽입 정렬 내림차순
public class HelloWorld{

     public static void main(String []args){
        int[] numbers = {3,4,2,6,1};
        
        for(int i = 1; i<numbers.length; i++){
            int target = numbers[i];
            int j = i-1;
            
            while(j >= 0 && target > numbers[j]){
                numbers[j+1] = numbers[j];
                j--;
            }
            
            numbers[j+1] = target; 
        }
        
        
        for(int num : numbers){
            System.out.println(num);
        }
     }
}

 

5. 적합한 때

• 이미 대부분 정렬되어 있으면서 자료의 수가 적은 경우
• 정렬하면서 같은 원소가 있을 때 자료 위치 변하면 안 되는 경우

6. 관련 문제

백준 11399