6-4장 단순 삽입 정렬

1. 단순 삽입 정렬 알아보기 

 

단순 삽입 정렬 (straight insertion sort)

 

- 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입'하는 작업을 반복하여 정렬

- 아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 열의 '알맞은 위치에 삽입'하는 작업을 n-1회 반복 

 

- 배열 {6,4,1,7,3,9,8}의  단순삽입정렬과정

 

ex) 값이 3인 요소를 선택해 앞쪽의 알맞은 위치에 삽입하는 과정 

 

 

 <1~3>

 - 3보다 작은 요소를 만날 때까지 이웃한 왼쪽의 요소를 대입하는 작업을 반복 

 <4>

 - 멈춘 위치에 3을 대입 

 

- 반복 제어용 변수 j에 i 대입

- tmp에 a[i] 대입 (a[i] = 정렬되지 않은 부분의 첫 번째 요소)

- 종료 조건 중 하나를 만날 때까지 j를 1씩 감소하면서 대입하는 작업 반복

 

<종료 조건> OR

1) 정렬된 열의 왼쪽 끝에 도달

2) tmp보다 작거나 같은 key를 갖는 항목 a[j-1]을 발견

 

드모르간 법칙 적용 

 

<계속 조건> AND

 1) j가 0보다 큼 (j>0)

 2) a[j-1]값이 tmp보다 큼 (a[i-1] >tmp) 

  (a[j-1] = 정렬된 부분의 마지막 요소  = 정렬되지 않은 부분의 첫 번째 요소의 인접한 왼쪽요소)

j=i;
tmp = a[i];
while(j>0 && a[j-1] > tmp)
	a[j] = a[j-1];
    j--;
a[j] = tmp;

 

- 단순 삽입 정렬 프로그램

// 단순 삽입 정렬 
#include <stdio.h> 
#include <stdlib.h>

//단순 삽입 정렬 함수 
void insertion (int a[], int n) 
{
	for(int i=1; i<n; i++)
	{
		int tmp = a[i];
		int j;
		for(j=i; j>0 && a[j-1]>tmp; j--)
			a[j]=a[j-1];
		a[j] = tmp;
	}
}

int main()
{
	int nx;
	puts("단순 삽입 정렬");
	printf("요소 개수:");
	scanf("%d",&nx);
	int *x=(int*)calloc(nx,sizeof(int)); //요소의 개수가 nx인 int형 배열 x를 생성
	
	for(int i=0; i <nx; i++) {
		printf("x[%d]:", i);
	    scanf("%d",&x[i]);
	}
	
	insertion(x,nx); //배열 x를 단순 삽입 정렬
	
	puts("오름차순으로 정렬했습니다.");
	for(int i=0; i <nx; i++) 
		printf("x[%d]=%d\n", i, x[i]);
	
	free(x); //배열을 해제 
	
	return 0; 
}