[자료구조] 삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

삽입 정렬은 1차원 배열 상에서 정렬된 부분과 정렬되지 않은 부분으로 나누어 정렬을 수행하는 방법이다.

오름차순으로 정렬한다면, 위와 같은 오름차순으로 정렬된 리스트와 정렬되지 않은 리스트로 나누고

정렬되지 않는 리스트에서 첫번째 원소를 정렬된 리스트의 각 값과 비교하여 알맞는 위치에 끼워넣는 방식이다.

 

 

 

위 방식을 구현하기 위해서는 정렬된 리스트와 정렬되지 않는 리스트의 인덱스값이 각각 필요하다.

0부터 정렬된 리스트의 인덱스까지, 그리고 정렬되지 않은 리스트의 인덱스 부터 배열의 끝까지로 나누기 위함이다.

 

위 사항들을 고려해서 코드를 작성해보았다.

 

삽입 정렬 

 

#include <stdio.h>

// 삽입 정렬 함수
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i]; // 정렬할 요소 선택
        j = i - 1;

        // 선택된 요소를 앞의 정렬된 배열 부분과 비교하여 적절한 위치에 삽입
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // 새로운 위치에 삽입
    }
}

void printArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 1, 9, 20, 89};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

 

 

실행 결과

 

 

 

---

 

결과 분석

 

이미 정렬된 데이터

삽입정렬(여기서는 오름차순으로 정렬하는 삽입정렬 함수)은 오름차순으로 이미 정렬된 데이터를 전달하는 경우에 속도가 가장 빠르다

색이 칠해진 부분이 정렬된 부분이고, 흰색인 부분이 정렬되지 않은 부분일때, 2는 1보다 크니까 바로 1의 오른쪽으로 갈 수 있다.

따라서 비교 횟수가 한번이고, 나머지 값들도 모두 1번씩만 비교하면 된다.

 

반대로 정렬된 데이터

여기서는 오름차순으로 정렬하는 삽입 정렬 함수이다. 

이 경우에 완전 반대인 내림차순으로 정렬된 리스트를 입력값으로 준다면 어떻게 될까?

 

4를 비교할 때는 5보다 작으므로 1번만 비교하면 되지만, 그 다음 단계인 3은 5보다 작으니 4와 비교하고, 4보다 작으니 4의 왼쪽으로 가는 2번의 연산이 필요하다.

심지어 2는 더 늘어나 3번의 연산이 필요하다.

 

 

 

결론적으로 삽입 정렬은 정렬이 많이 되어있을수록 좋은 성능을 가진다.