삽입 정렬

삽입 정렬

현재 조사해야할 위치가 k라면 1~k-1까지 정렬된 상태에서

k의 위치를 찾아 1~k를 정렬된 상태로 만들어

최종적으로 전체 원소를 정렬하는 방식

만약 k의 위치가 들어갈 자리가 x라면

1, 2, 3,..... k-1 k 를

1, 2, ... x, x+1, .... k 형태로 만들어 줘야 하므로

x+1, k-1 까지를 한 칸씩 땡기고 x자리에 k번째 원소를 집어 넣는 구조로 진행된다.

소스코드

for(int i=2,j,tmp; i<=n; i++){

tmp = data[i];

for(j=i-1; j>=1; j--){

if(data[j] > tmp){

data[j+1] = data[j];

}

}

data[j+1] = tmp;

}