7. 삽입 정렬 (Insertion Sort)

삽입 정렬은 선택한 요소를 더 앞쪽의 위치에 삽입을 하는 작업을 반복하는 정렬 알고리즘이다.

선택정렬은 제일 작은 값을 선택하는 점에 있어서 차이점이 있다.

 

6

4

1

7

3

9

4

6

1

7

3

9

삽입 정렬을 2번째 요소부터 진행을 한다. 오름차순 정렬에 있어, 4는 6보다 앞에 있어야 하기에, 4를 앞쪽에 삽입하고,

6을 오른쪽으로 밀면 2번째 배열의 형태처럼 이루어진다.

 

모든작업을 수행하는 데 있어서 n-1회 반복하면 정렬을 마치게된다.

for(i=1;i<n;i++)
{
	tmp = a[i];
}

기본적인 틀은 위와 같다.  전체 배열 크기 n에서 반복 횟수는 n-1 이기에 i를 1부터 시작하게 된다.

그렇게 되면 위의 예시에서 a[i] = 4가 처음으로 설정될 것이다. 

자, 이제 여기서 반복 제어용 변수 j를 선언할텐데, j에 i-1을 대입해서 아래의 두 조건이 만족할 때까지 j를 감소시키며 반복한다.

 

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

2. tmp보다 작거나 같은 key를 찾는 항목 a[j]를 발견

 

여기서 j를 감소시킬때 계속 감소시키면 j는 음수가 되기에 j>0의 조건을 걸어주고 a[j-1]이 tmp보다 클때까지의 조건도 같이 걸어주어야 한다.

a[j-1]이 tmp보다 클 때라는 것의 의미로는, 위의 배열을 예로 들어보면 처음 반복문에서 a[j-1]은 4가 된다. 그리고 tmp는 a[i] 이기에 4가 되는데 a[j]에 a[j-1]을 바꾸는 것이 삽입 정렬의 정의 임으로, a[j-1]은 tmp보다 커야한다.

 

#include <stdio.h>
#include <stdlib.h>

void insert(int a[], int n)
{	
	int i,j;
	for(i=1;i<n;i++)
    {
    	int tmp = a[i];
        for(j=i;j>0&&a[j-1]>tmp;j--)
        	a[j] = a[j-1];
        a[j] = tmp;
    }

}

int main(void) {
	
	int i, nx;
	int* x;

	printf("요소 개수 : ");
	scanf("%d", &nx);
	x = (int*)calloc(nx, sizeof(int));

	for (i = 0; i < nx; i++)
	{
		scanf("%d", &x[i]);
	}
	insert(x, nx);

	puts("오름차순으로 정렬");
	for (i = 0; i < nx; i++)
	{
		printf("x[%d] = %d\n",i,x[i]);
	}
	free(x);
	
	return 0;
}

 

 

def insertSort(list_data):
	for i in range(1, len(list_data)):
    	k = data[i]
        j = i -1
        
        while data[j]>k and j>=0:
        	data[j+1] = data[j]
            j-=1
        data[j+1] = k
        
   return list_data