[C++] 삽입 정렬 (Insertion Sort)

[삽입정렬]

각 숫자를 필요할때만 적당한 위치에 삽입하는 방법

[문제]

  1,10,5,8,7,6,4,3,2,9 를 순서대로 정렬하세요

[풀이]

#include <stdio.h>

int main(void) {

int i, j, temp;

int array[10] = { 1,10,5,8,7,6,4,3,2,9 };

for (i = 0; i < 9; i++) {

j = i; //현재 정렬할 원소를 선택하여 적당한 위치에 넣어주기 위함

while (array[j] > array[j + 1]) { //왼쪽이 오른쪽보다 크면 위치를 바꿔줌

temp = array[j];

array[j] = array[j + 1];

array[j + 1] = temp;

j--;

}

}

for (i = 0; i < 10; i++) {

printf("%d", array[i]);

}

}

[문제점]

선택정렬과 버블정렬보다는 효율적이다. 그 이유는 전체를 다 확인해볼 필요가 없고 

1 5 7 8 10 6 4 3 2 9  에서 6을 적당한 위치에 넣어 줄 경우 7 8 10 3번만 확인후에 5 뒤에 넣어주면 되기떄문이다.

그렇지만 시간 복잡도 o(n*n)를 가진다는 점에서 비효율적인 알고리즘에 속한다.