230619 Today I Learned

오늘 삽입 정렬에 대해 정리하고 직접 구현해보고자 한다.

삽입 정렬(Insertion Sort)

이미 정렬된 앞쪽의 원소들과 순서대로 비교하면서 올바른 위치에 삽입하는 정렬 알고리즘.

이미지 출처 : yun.log

• 과정
  두번째 원소부터 시작한다.(첫 원소는 이미 정렬되어있다고 가정)
  현재 원소를 key로 선택하고, 앞의 원소들과 비교해 삽입할 위치를 찾는다.
  key보다 작은 값을 만나거나 배열의 시작에 도달하면 반복을 멈춘다.
  해당 위치에 key값을 삽입한다.
  배열의 모든 원소가 정렬될 때까지 반복한다.

• 시간복잡도
  최선 - 배열이 이미 정렬되어있는 경우 비교만 하며 이동연산이 필요하지 않기 때문에 O(n)이다.
  평균 및 최악 - 각 원소마다 비교 및 이동 연산이 발생하므로 연산 횟수는 n(n-1)/2로 시간복잡도는 O(n^2)이다.
  최악의 경우는 역정렬 되어있는 경우이다.

• 공간복잡도 : O(1). 주어진 배열 안에서 원소들의 위치를 이동하며 정렬하기 때문에 추가적인 메모리 공간이 필요하지 않다.

• 장점 : 구현이 간단하고 직관적이다.
  추가적인 메모리 공간이 필요없는 제자리 정렬이다.
  안정정렬이다.(stable, 중복된 값을 입력된 순서에 맞게 정렬)
  버블, 선택과 달리 원소가 거의 정렬되어있는 경우 매우 효율적이다.(최선의 경우가 O(n)이다)
  병합정렬과 삽입정렬을 섞어 만든 tim sort 같은 곳에서도 쓰인다.

• 단점 : 평균과 최악의 시간복잡도가 O(n^2)으로 느리다.
  버블, 선택정렬과 마찬가지로 배열의 길이가 길어질수록 비효율적이다.

Java로 삽입 정렬 구현

밖의 for문으로 두번째 값부터 key값을 삼아서 앞의 원소와 비교를 시작한다. 안쪽의 while문으로 key값이 이전 원소들보다 작을 때까지만 원소를 한칸씩 뒤로 미루고, 적합한 위치에 key값을 삽입한다.

  private static void insertionSort(int[] array){
//    두번째 값부터 비교를 시작해서 i=1 부터 시작
    for (int i = 1; i < array.length; i++) {
      int key = array[i];
      int j = i-1;
//      key값이 이전 원소들보다 작을때까지만 반복
      while (j >= 0 && array[j] > key){
//        원소를 한칸씩 뒤로 미룸
        array[j+1] = array[j];
        j--;
      }
//      정렬 위치에 맞게 key값을 삽입
      array[j+1] = key;
    }

이진 삽입 정렬

key값 앞에 있는 배열의 값들은 이미 정렬된 상태이다. 그래서 비교를 할 때 순차탐색으로 n번씩 비교하는 것 보다, 이진탐색을 활용해 탐색 횟수를 줄일 수 있다.

  private static void binaryInsertionSort(int[] array){
    for (int i = 1; i < array.length; i++) {
      int key = array[i];
//      이진탐색으로 앞의 배열 탐색. 최종 위치는 low가 된다.
      int low = 0;
      int high = i-1;
      while(low <= high){
        int mid = (low+high)/2;
        if (key < array[mid]){
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
//      i-1부터 최종 위치까지 원소를 한칸 씩 뒤로 민다
      for (int j = i-1; j >= low; j--){
        array[j+1] = array[j];
      }
//      최종 위치에 key값을 삽입
      array[low] = key;
    }
  }

• 하지만 시간복잡도는 여전히 O(n^2)으로 일반 삽입정렬과 동일하다.

최종 출력

  public static void main(String[] args) {
    int[] array = {1,2,7,5,4,3,9,6,8,10};
    int[] array2 = Arrays.copyOf(array, array.length);
    System.out.print("정렬 전 배열 : ");
    System.out.println(Arrays.toString(array));
    System.out.println("-----------------------------------------");
    insertionSort(array);
    System.out.print("삽입정렬 후 배열 : ");
    System.out.println(Arrays.toString(array));
    System.out.println("-----------------------------------------");
    binaryInsertionSort(array2);
    System.out.print("이진 삽입정렬 후 배열 : ");
    System.out.println(Arrays.toString(array2));
  }