삽입정렬(Insertion Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI

알고리즘 개념

• 이미 정렬되어 있는 리스트에서 새로운 수를 추가하는 과정이다.
• 비교 대상인 수가 자신의 자리를 찾을 때까지 왼쪽으로 이동한다.

과정

1. 첫 번째에 위치한 수(인덱스 0번 위치의 수)는 이미 정렬이 완료되었다고 가정한다.
2. 정렬 리스트의 오른쪽에 있는 정렬되지 않은 수(인덱스 1번 위치의 수)는 자신의 앞에 있는 수와 크기를 비교하여 앞쪽 수가 더 크면 자리를 바꾼다.
3. 인덱스 2번 위치의 수도 왼쪽으로 전진 하면서 자기 자리를 찾는다.
4. 더 이상 정렬된 대상 원소가 없을 때까지 반복한다.

코드

int j, temp;
    for (int i = 1; i < n; i++){
        // 정렬 대상 원소 저장
        temp = arr[i]; 
        for (j = i - 1 ; j >= 0 && temp < arr[j]; j--){
            arr[j+1] = arr[j];
        }
        arr[j+1] = temp;
    }

장점

• 알고리즘 구현이 간단하고 단순하다.
• 이미 정렬되어 있는 경우 매우 효율적이다.

단점

• 배열이 길수록 효율성이 떨어진다.

시간 복잡도

• 최상의 경우: 이미 정렬이 되어있는 경우 O(n)
• 평균: O(n^2)
• 최악의 경우: 역순으로 정렬 되어있는 경우 O(n^2)

공간 복잡도

• O(n)
• 별도의 메모리 공간이 필요하지 않은 제자리 정렬(in-place sorting)

---

정렬 알고리즘 시간 복잡도 정리

정렬	최선	평균	최악
선택정렬(Selection Sort)	O(n^2)	O(n^2)	O(n^2)
거품정렬(Bubble Sort)	O(n^2)	O(n^2)	O(n^2)
삽입정렬(Insertion Sort)	O(n)	O(n^2)	O(n^2)
퀵정렬(Quick Sort)	O(nlogn)	O(nlogn)	O(n^2)
병합정렬(Merge Sort)	O(nlogn)	O(nlogn)	O(nlogn)
힙정렬(Heap Sort)	O(nlogn)	O(nlogn)	O(nlogn)