기본 정렬 - Insertion sort(삽입 정렬)

[정렬 방법]

전체(n개의 값)에서 arr[1], arr[2], ..., arr[n-1] 순으로 기준값(key)으로 두고 바로 왼쪽 값부터 왼쪽에 있는 값들이 key보다 클 경우 한칸씩 오른쪽으로 옮긴다. 작을 경우엔 멈추고 비교대상이던 값의 오른쪽에 key값을 넣어준다. 이 과정을 arr[n-1]까지 진행하면 정렬된다.

---

[정렬 과정]

 

n 크기의 임의의 배열 arr에서

<1단계> - 1번의 비교

 

arr[1] 값을 key값으로 둔 후,

 

arr[0]와 비교해서 key값이 작으면 arr[1] = arr[0], arr[0] = key, key값이 크면 arr[1] = key

 

<2단계> - 최대 2번의 비교

 

arr[2] 값을 key값으로 둔 후,

 

arr[1]와 비교해서 key값이 작으면 arr[2] = arr[1]로 한 후 (1), key값이 크면 arr[2] = key

(1) arr[0]과 비교하여 key값이 작으면 arr[1] = arr[0], arr[0] = key, key값이 크면 arr[1] = key

.

.

.

 

<n-1단계> - 최대 n-1번의 비교

 

arr[n-1] 값을 key값으로 둔 후,

 

arr[n-2]와 비교해서 key값이 작으면 arr[n-1] = arr[n-2]로 한 후 (1), key값이 크면 arr[n-1] = key

(1) arr[n-3]과 비교하여 key값이 작으면 arr[n-2] = arr[n-3]로 한 후 (2), key값이 크면 arr[n-2] = key

(2) arr[n-4]과 비교하여 key값이 작으면 arr[n-3] = arr[n-4]로 한 후 (3), key값이 크면 arr[n-3] = key

...

(n-2) arr[0]과 비교하여 key값이 작으면 arr[1] = arr[0], arr[0] = key, key값이 크면 arr[1] = key

---

[pseudo code]

insertionSort(arr[], n) {
  for i <- 1 to n-1
    arr[0]-arr[i] 위치에서 맞는 곳에 arr[i]를 삽입
}

---

[코드 구현]

 

public class Insertion {
  private static int[] input = {3, 54, 4, 12, 67, 31, 43, 56, 14, 53}; //예시로 작성한 배열

  public static void main(String[] args) {
    insertionSortMin(input, input.length); //혹은 insertionSortMax(input, input.length);
    for (int i : input) {
      System.out.print(i + " ");
    }
  }

  private static void insertionSortMin(int[] input, int length) { //가장 작은 값부터 삽입 정렬하는 방법
    int tmp;
    for(int i=1; i<length; i++){
      tmp = input[i];
        int j = i-1;
        while(0 <= j && input[j] > tmp){
            input[j+1] = input[j];
            j--;
        }
        input[j+1] = tmp;
    }
  }
  
  private static void insertionSortMax(int[] input, int length) { //가장 큰 값부터 삽입 정렬하는 방법
    int tmp;
    for(int i=length-2; i>=0; i--){ 
      tmp = input[i];
        int j = i+1;
        while(length-1 >= j && input[j] < tmp){
            input[j-1] = input[j];
            j++;
        }
        input[j-1] = tmp;
    }
  }
  
}

---

[시간 복잡도]

정렬이 잘 되어 있는 정도에 따라서

1) 최악의 경우

 

처음에 1번의 비교, 그 다음에 2번의 비교,... n-1번의 비교를 진행하므로

T(n) = ( 1+2+...+n-1 ) = O( n(n-1)/2 ) = O(n^2) 이 된다.

 

2) 최선의 경우

배열이 모두 정렬이 되어있는 경우로 처음부터 매 경우마다 비교 후 바로 끝나기 때문에 시간 복잡도는 O(n)이다.

 

3) 평균

Selection sort(선택 정렬)와 Bubble sort(버블 정렬)과 비교 시 최악의 경우는 같지만  최선의 경우엔 상대적으로 빠르다. 그러므로 평균은 절반 정도이다. 하지만 시간 복잡도는 O(n^2)이라 한다.