[알고리즘] 정렬-삽입정렬(Insertion Sort)

숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.
참고교재: 쉽게 배우는 알고리즘(문병로)

기본적인 정렬 알고리즘 O(n^2)
1.선택정렬
2.버블정렬
3.삽입정렬

고급 정렬 알고리즘 O(n*logn)
1.병합정렬
2.퀵정렬
3.힙정렬

특수 정렬 알고리즘 O(n)
1.계수정렬
2.기수정렬

 

삽입정렬이란

삽입 정렬(Insertion Sort)은 배열을 정렬하는 또 다른 기본적인 알고리즘입니다. 이 방법은 각 반복에서 하나의 원소를 적절한 위치에 '삽입'하는 방식으로 동작합니다. 삽입 정렬은 일반적으로 소규모 데이터셋에 대해서는 효율적이지만, 큰 데이터셋에 대해서는 그렇지 않습니다.

삽입정렬이 수행되는 과정, 출처: 위키백과

삽입 정렬의 작동 방식은 다음과 같습니다:

1.배열의 두 번째 원소부터 시작하여 현재의 원소를 key 값으로 저장합니다.
2.key 값보다 앞에 있는 배열의 원소들과 비교하여 key가 들어갈 적절한 위치를 찾습니다.
3.비교하는 원소가 key보다 크면, 비교하는 원소를 한 칸 뒤로 옮깁니다.
4.이를 key 값이 들어갈 위치를 찾을 때까지 반복합니다.
5.key 값을 찾아낸 적절한 위치에 삽입합니다.
6.배열의 모든 원소에 대해 위 과정을 반복합니다.

삽입 정렬은 이미 정렬된 부분과 아직 정렬되지 않은 부분으로 구성된다는 점에서 효율적입니다. 이미 정렬된 부분은 검사할 필요가 없으며, 새로운 원소는 이 '정렬된' 부분에 바로 삽입됩니다.
삽입 정렬의 시간 복잡도는 최악의 경우 O(n^2)이지만, 이미 정렬된 데이터에 대해서는 매우 빠르게 동작하며, 안정적인 정렬 방법입니다. 

 

버블정렬 코드 

void insertion_sort(int arr[], int len){
    int i, key, j;
    for (i = 1; i < len; 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;
    }
}

 

테스트 코드 

int main() {
    int arr[] = {20, 30,10,21,5,39,2};
    int len = sizeof(arr)/ sizeof(arr[0]);

    cout<<"before insertion :"<<endl;
    for(int i=0; i<len; i++){
        cout << arr[i] <<" ";
    }

    insertion_sort(arr, len);

    cout<<"\nafter insertion :"<<endl;
    for(int i=0; i<len; i++){
        cout << arr[i] <<" ";
    }

    return 0;
}

테스트 결과

before insertion :
20 30 10 21 5 39 2
after insertion :
2 5 10 20 21 30 39