[Sort Algorithm] Insertion sort

삽입정렬이란?

삽입정렬은 배열의 첫번째와 두번째 index를 비교하여 (오름차순 정렬일 경우) 더 작은 값을 앞으로 보낸다.
그 다음에는 배열의 두번째와 세번째 index를 비교하여 세번째 index가 더 작다면 서로 위치를 바꾸고, 다시 첫번째 index와 비교하여 더 작은 값을 앞으로 보낸다. 그렇지 않다면 현재 단계의 프로세스를 중단하고 배열의 세번째와 네번째 index를 비교하는 단계로 넘어간다.
이런식으로 배열의 마지막 index에 도달할때까지 계속 반복한다.

예시
[37, 24, 14, 20, 13] 오름차순 정렬
1차 : 37, 24 비교 & 서로 위치 교환
< 결과 : [24, 37, 14, 20, 13] >
2차 : 37, 14 비교 & 서로 위치 교환, 24, 14 비교 & 서로 위치 교환
< 결과 : [14, 24, 37, 20, 13] >
3차 : 37, 20 비교 & 서로 위치 교환, 24, 20 비교 & 서로 위치 교환, 14, 20 비교 & 위치 교환이 없으므로 3차 작업 종료
< 결과 : [14, 20, 24, 37, 13] >
4차 : 37, 13 비교 & 서로 위치 교환, 24, 13 비교 & 서로 위치 교환, 20, 13 비교 & 서로 위치 교환, 14, 13 비교 & 서로 위치 교환
< 결과 : [13, 14, 20, 24, 37] >

삽입정렬은 최악의 경우엔, (n - 1) + (n -2) …. 1 = n(n-1)/2 번 연산을 수행하기 때문에 시간복잡도가 O(N^2)이다.
그러나 최선의 경우엔, 배열을 한 번 순회만 하고 알고리즘이 종료되기 때문에 시간복잡도가 O(N)이 된다.
알고리즘 구현이 비교적 간단하지만, 배열의 크기가 커질수록 계산속도가 기하급수적으로 느려지는 단점이 있다. 다만, 정렬하려는 배열이 이미 어느정도 정렬이 된 상태라면 버블정렬, 선택정렬보다는 좀 더 효율적이다.

삽입정렬 예시 (출처 : https://en.wikipedia.org/wiki/Insertion_sort)

Java Code

public class InsertionSort {
  public static void main(String[] args) {
    int[] arr = {1, 2, 10, 3, 16, 255, -1, -8, 23, 543, 1, 6, 5, 13};
    int[] result = sort(arr);
    for (int i = 0; i < arr.length; i++) {
      System.out.print(result[i] + ", ");
    }
  }

  public static int[] sort(int[] arr) {
    int length = arr.length - 1;
    for (int i = 0; i < length; i++) {
      int j = i;
      while (j >= 0 && arr[j] > arr[j + 1]) {
        swap(arr, arr[j], arr[j + 1], j);
        j--;
      }
    }
    return arr;
  }

  public static void swap(int[] arr, int firstNo, int secondNo, int index) {
    arr[index] = secondNo;
    arr[index + 1] = firstNo;
  }
}

삽입정렬 시작 전


삽입정렬 종료 후

Github link

https://github.com/kwonminho1992/Algorithm-practice