정렬(sort) - 삽입 정렬(insertion sort)

정렬(sort) - 삽입 정렬(insertion sort)

삽입 정렬은 오른쪽부터 요소를 조사하여 순서에 맞게 삽입하는 방법을 사용한다.

첫 요소는 그대로 놓고, 두 번째 요소를 취하여 두 개의 순서가 다르면 바꾼다. 세 번째 요소를 취하여 세 개의 수를 같은 방법으로 계속 반복 진행한다.

for ( i=1 ; i=0 ; j--){
    // 내림차순이면 부등호를 <로 변경
    if( a[j] > temp )
      a[j+1]=a[j];
    else
      break;
  }
  a[j+1]=temp;
}

삽입정렬 예제

다음은 삽입정렬 예제 소스입니다.

10개의 수를 입력받아서 삽입정렬을 하는 소스입니다.

#include<stdio.h>

#define MAX 10

void swap(int*, int*);

int main()
{
	int arr[MAX];

	int i,j,k,tmp;

	printf("---INPUT---\n");
	printf("Input 10 Integers\n");
	for(i=0;i<MAX ; i++)
		scanf("%d", &arr[i]);
	printf("\n");

	// 정렬 전 배열값 출력
	printf("---BEFORE---\n");
	for(i=0;i<MAX;i++) printf("%3d",arr[i]);
	printf("\n\n");

	printf("------------\n");
	// 삽입정렬
	for ( i=0 ; i<MAX ; i++ ){
		for (j=i+1 ; j<MAX ; j++){    
			if( arr[j] < arr[i] ){
				swap(&arr[i],&arr[j]);
			}
		}
		// 결과 출력
		for(k=0;k<MAX;k++) printf("%3d",arr[k]);
			printf("\n");
	}


	// 버블 정렬 결과 출력
	printf("\n---AFTER---\n");
	for(i=0;i<MAX;i++) printf("%3d",arr[i]);
	printf("\n");

	return 0;   
}

void swap(int *a, int *b)
{
	int temp ;
	temp = *a;
	*a   = *b;
	*b   = temp;
}

실행결과입니다.