[C언어/파이썬] Insertion Sort Algorithm C와 Python으로 구현해보기

 

- 배열 맨 처음 정렬된 부분에 정렬되지 않은 다음 항목들을 반복적으로 삽입하는 방식이다.

- 즉 미리 정렬된 리스트에 새 항목을 추가할 때 좋은 정렬 알고리즘이다.

- 데이터의 크기가 작고 리스트가 이미 정렬되어있으면 다른  merge sort 나 quick sort 같은 고급 알고리즘보다 성능이 좋음

- 최선의 경우 시간복잡도 O(n)

- 평균과 최악의 경우 시간복잡도 O(n^2)

 

 

 

 1. insertion sort ( 삽입 정렬 ) 알고리즘 process

 

index  0          1         2          3          4          5

11

3

28

43

9

4

 를 정렬한다고 가정

 

 outer loop i :    0 ~ 5

0 번부터 5번 인덱스 i 가 차례로 리스트에 추가된다고 가정한다.

인덱스 i 가 추가될 때에는  0~ i-1  까지는 정렬되어 있다고 가정한다. 

 iner loop j :    i ~ 0

 j = i 부터 시작하여 1 씩 감소해가며 , 이미 정렬되어 있는 0~ i-1 리스트에서 자신의 위치를 찾는다.

 

1) index  i = 0 일 때는 원소가 한개이므로 정렬할 필요가 없다.

11

3

28

43

9

4

2)  index i = 1 

11

3

28

43

9

4

 j = i, 

data[j]가 data[j-1] 번보다 작으므로 자리를 바꾼다

 

3

11

28

43

9

4

 

3)  index i = 2 

 

3

11

28

43

9

4

 

 j = i 

data[j] 가 data [j-1] 보다 값이 크므로 자리를  바꾸지 않는다.

 j-1 이전의  data 값들은 이미 정렬되어 있으므로 

더이상 j 를 감소시켜가며 볼 필요가 없다. 

다음  i 로 넘어가자

 

4)  index i = 3

3

11

28

43

9

4

 j = i

data[j] 가 data [j-1] 보다 값이 크므로 자리를  바꾸지 않는다.

 j-1 이전의  data 값들은 이미 정렬되어 있으므로 

더이상 j 를 감소시켜가며 볼 필요가 없다. 

다음  i 로 넘어가자

 

4)  index i = 4

3

11

28

43

9

4

 j = i

data[j] 가 data [j-1] 보다 값이 작으므로 자리를  바꾼다.

j--

 

3

11

28

9

43

4

data[j] 가 data [j-1] 보다 값이 작으므로 자리를  바꾼다.

j--

 

3

11

9

28

43

4

data[j] 가 data [j-1] 보다 값이 작으므로 자리를  바꾼다.

j--

 

3

9

11

28

43

4

data[j] 가 data [j-1] 보다 값이 크므로 자리를  바꾸지 않는다.

 j-1 이전의  data 값들은 이미 정렬되어 있으므로 

더이상 j 를 감소시켜가며 볼 필요가 없다. 

다음  i 로 넘어가자

 

4)  index i = 5

 

3

9

11

28

43

4

 

 이하 생략

 

 

 

1.  C언어로 구현하기 

 C 언어로  array를 다루는 함수를 작성할 때,  array의 크기를  인자로 받도록 한다. (강제는 아니지만 그게 쉬움ㅎㅎ)

int data[] = { 2, 1, 9, 7, -3, 2, 6, 4, 3, 8 };
int N;
void insert Sort(int N) // 사이즈를 건네줌
{
	for (int i = 1; i < N; i++) {  // outer loop i
		for (int j = i; j >0 ; j--) { // inner loop j
			if (data[j] > data[j-1]) break; // j-1 이전은 전부 정렬되어 있으므로 다음 i 로 건너가자
			
			int tmp = data[j];
		    data[j] = data[j-1];
			data[j-1] = tmp;
			
		}
	}
}

 

 

 

 main 함수와, array print함수를 포함한 전체 코드 

 

 

 

#include <stdio.h>
int data[] = { 2, 1, 9, 7, -3, 2, 6, 4, 3, 8 };
int N;
void insertSort(int N) // 사이즈를 건네줌
{
	for (int i = 1; i < N; i++) {
		for (int j = i; j >0 ; j--) {
			if (data[j] > data[j-1]) break;
			
			int tmp = data[j];
		    data[j] = data[j-1];
			data[j-1] = tmp;
			
		}
	}
}
void printAry(int N)
{
	int i;
	for (i = 0; i < N; i++)
	{
		printf("%d ", data[i]);
	}
	printf("\n");
}
void main(void)
{
	int N = sizeof(data) / sizeof(data[0]);
	printAry(N);
	insertSort(N);
	printAry(N);

}

 

 

 

 

 

2.  파이썬 코드로 구현하기 

def insertion_sort(seq):
	for i in range(1, len(seq)): #  파이썬은 리스트의 length 를 구해주는 메소드가 있다.
		j=i
        while j>0 and seq[j-1]>seq[j]: # j 가 0보다 크거나, 앞에 정렬된 것들 중 제일 큰 애 보다 내가 더 작을 때 -->  나(j)는 비집고 들어가야함
        	seq[j-1],seq[j] = seq[j],seq[j-1]  # 파이썬은 값 교환시 temporary 변수가 필요하지 않음
            j-=1;
  	return seq;