삽입 정렬

이번에는 삽입 정렬에 대해서 정리해보려고한다.

삽입 정렬이란?

• 삽입 정렬은 두 번째 자료부터 시작해서 그 앞의 자료와 비교하여 교환하는 방식의 알고리즘이다.
• 두 번째는 첫 번째 자료와 비교하여 교환하고, 세 번째는 두 번째와 첫 번째자료와 비교하여 교환하는 방식으로 진행된다는 것이다.
• 이미 정렬된 부분과 비교하여 교환하면서 자기 자리를 찾아 삽입하기에 삽입 정렬이라고 불린다.
• 예를 들어 살펴보자. (8 5 6 2 4)
  • 1회전
    • 8 5 6 2 4 → 5 8 6 2 4
  • 2회전
    • 5 8 6 2 4 → 5 6 8 2 4
  • 3회전
    • 5 6 8 2 4 → 5 6 2 8 4 → 5 2 6 8 4 → 2 5 6 8 4
  • 4회전
    • 2 5 6 8 4 → 2 5 6 4 8 → 2 5 4 6 8 → 2 4 5 6 8
• 위처럼 선택된 인덱스의 앞에 있는 요소와 비교하여 교환하는 방식으로 이루어진다.
• 각 회전에 대한 설명은 다음과 같다.
  • 1회전에서는 두 번째 자료부터 시작하므로 8과 5를 비교하여 교환한다.
  • 2회전에서는 세 번쨰 자료부터 비교를 하게되고 8과 6을 비교하여 교환한다.
  • 3회전에서는 네 번째 자료부터 비교를 하게되고 8과 2를 비교하여 교환하고, 6과 2를 비교하여 교환하고, 5와 2를 비교하여 교환하게 된다.
  • 4회전에서는 다섯 번째 자료부터 비교를 하게되고 8과 4를 비교하여 교환하고, 6과 4를 비교하여 교환하고, 5와 4를 비교하여 교환하여 정렬이 완료되게 된다.

코드 (Java)

for(int i = 1; i < number; i++){
    int tmp = numArr[i], j;
    for(j = i-1; j >= 0; j--){
        if(numArr[j] > tmp){
            numArr[j+1] = numArr[j];
        }else{
            break;
        }
    }
    numArr[j+1] = tmp;
}

• 코드에서도 볼 수 있다싶이 두 번째 자료부터 시작해서 이전의 정렬되어있는 자료들과 비교하는 로직으로 짜여있다.
• 추가로 j를 상위해서 선언하여 위치를 기억하고 값을 변경하는 구조로 되어있다.

시간복잡도

• 삽입 정렬의 시간복잡도는 평균적으로는 O(n^2)으로 이루어진다.
• 최선의 상황에서는 비교만 이루어지고 교환은 이루어지지 않아 O(n)의 시간복잡도를 가진다.
• 최악의 상황(역순으로 되어있는 경우)에서는 for문을 통해 전체를 탐색하고 2중 for문을 통해 전체를 비교하고 교환하게 되면서 O(n^2)이 되게 된다.

참고 -

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html