[알고리즘] 삽입정렬

삽입정렬(Insertion Sort)이란 ?

삽입정렬은 정렬되지 않은 데이터를 앞에서 부터 차례대로 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬 알고리즘입니다

 

5 3 2 4 1 이런 배열이 주어졌을 때

 

3은 5의 앞으로 가야 하기 때문에

3을 빼서 3의 자리로 5를 밀고 원래 5가 있던 자리에 3을 삽입합니다.

3 5 2 4 1

 

그 다음 2는

2는 5보다 앞으로 가야 됩니다

위에서 3이 했던 것과 같이 2를 빼서 5를 밀고

앞에 3이 또 있으니까 3과 비교해 줍니다

3보다도 앞으로 가야 하니까 3을 또 밀어주고 2는 맨 앞으로 가게 됩니다

 

이렇게 앞에 수와 비교해 주면서 맞는 위치에 삽입해 주는 것입니다.

 

public int[] solution(int n, int[] arr) {
    
    for(int i=1; i<n; i++) {
       int tmp = arr[i];
       int j;
       for(j=i-1; j>=0; j--) {
          if(arr[j]>tmp) {
             arr[j+1] = arr[j];
          }
          else break;
       }
       
       arr[j+1] = tmp;
    }
    
    return arr;
}

길이가 n인 정수형 배열 arr을 입력값으로 받았을 때 삽입정렬 코드입니다.

 

옆자리의 원소와 자리를 바꾸는 경우가 삽입 대상이 되는 수가 왼쪽 수보다 작을 때만 일어나기 때문에

작지 않다면 자리를 바꾸지 않고 현재 자리에 삽입됩니다

즉, 삽입 정렬에서는 삽입 대상이 되는 수의 왼쪽 수들은 모두 정렬이 되어 있는 상태이기 때문에 왼쪽 수 보다 클 때, 더 이상 자리를 바꾸지 않고 현재 자리에 삽입하여 정렬시킬 수 있는 것입니다

 

따라서 최악의 경우가 아닐 시 시간복잡도는 O(N^2)보다 작습니다. (최악의 경우 O(N^2))

그러므로 O(N^2)의 시간복잡도를 갖는 선택정렬, 버블정렬중에 가장 빠른 정렬 알고리즘입니다.