[알고리즘] 정렬 3 - 삽입정렬, 셸 정렬

목차

정렬

삽입 정렬 Insert Sort

삽입 정렬은 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방식으로 정렬을 수행한다. 삽입 정렬에서는 정렬할 자료가 두 개의 부분집합 S(Sorted Subset)와 U(Unsorted Subset)로 나뉘고 정렬된 앞부분의 원소는 부분집합 s가 되고, 아직 정렬하지 않은 나머지 원소는 부분집합 U가 된다.

정렬하지 않은 부분 집합 U의 원소를 앞에서부터 하나 하나 꺼내서 이미 정렬한 부분 집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입하는 방식이다. 따라서 삽입 정렬을 수행할 때마다 부분집합 S의 원소는 하나씩 늘어나는 반면, 부분집합 U의 원소는 하나씩 줄어든다.

삽입 정렬 작동 과정의 예

주어진 배열: {69, 10, 30, 2, 16, 8, 31, 22}

첫 번째 단계 (i=1):

• 배열의 두 번째 원소부터 시작합니다. 현재 원소는 10이다.
• 10을 그 앞의 원소와 비교하여 위치를 조정한다. 69보다 작으므로 위치를 바꾼다.
• 배열: {10, 69, 30, 2, 16, 8, 31, 22

두 번째 단계 (i=2):

• 현재 원소는 30이다.
• 30을 그 앞의 원소와 비교하여 위치를 조정한다. 69보다 작고, 10보다 크므로 10과 30의 위치를 바꾼다.
• 배열: {10, 30, 69, 2, 16, 8, 31, 22}

세 번째 단계 (i=3):

• 현재 원소는 2이다.
• 2를 그 앞의 원소와 비교하여 위치를 조정한다. 69보다 작고, 30보다 작으며, 10보다 작으므로 앞의 원소들과 위치를 계속 바꾼다.
• 배열: {2, 10, 30, 69, 16, 8, 31, 22}

네 번째 단계 (i=4):

• 현재 원소는 16이다.
• 16을 그 앞의 원소와 비교하여 위치를 조정한다. 69보다 작고, 30보다 작으며, 10보다 크므로 위치를 바꾼다.
• 배열: {2, 10, 16, 30, 69, 8, 31, 22}

다섯 번째 단계 (i=5):

• 현재 원소는 8이다.
• 8을 그 앞의 원소와 비교하여 위치를 조정한다. 69보다 작고, 30보다 작으며, 16보다 작으며, 10보다 작으므로 위치를 계속 바꾼다.
• 배열: {2, 8, 10, 16, 30, 69, 31, 22}

여섯 번째 단계 (i=6):

• 현재 원소는 31이다.
• 31을 그 앞의 원소와 비교하여 위치를 조정한다. 69보다 작고, 30보다 크므로 위치를 바꾼다.
• 배열: {2, 8, 10, 16, 30, 31, 69, 22}

일곱 번째 단계 (i=7):

• 현재 원소는 22이다.
• 22를 그 앞의 원소와 비교하여 위치를 조정한다. 69보다 작고, 31보다 작으며, 30보다 작으며, 16보다 크고, 10보다 크으므로 위치를 바꾼다.
• 배열: {2, 8, 10, 16, 22, 30, 31, 69}

 

모든 단계를 거친 후에는 배열이 정렬이 끝난다.

#include <stdio.h>

void insertionSort(int a[], int size) {
	int i, j, t, temp;

	for (i = 1; i < size; i++) {
		temp = a[i];
		j = i;
		while ((j > 0) && (a[j - 1] > temp)) {
			a[j] = a[j - 1];
			j = j - 1;
		}
		a[j] = temp;
		printf("\n %d단계 : ", i);
		for (t = 0; t < size; t++) printf("%3d ", a[t]);
    }
}

int main(void) {
	int i, list[8] = { 69, 10, 30, 2, 16, 8, 31, 22 }; // 정렬할 원소 
	int size = sizeof(list) / sizeof(list[0]); 	// list 배열의 원소 개수
	printf("\n정렬할 원소 : ");
	for (i = 0; i < size; i++)  printf("%d ", list[i]); // 정렬 전의 원소 출력
	printf("\n\n<<<<<<<<<< 삽입 정렬 수행 >>>>>>>>>>\n");
	insertionSort(list, size);  // 삽입 정렬 함수 호출

	getchar();  return 0;
}
------------------------------------

정렬할 원소 : 69 10 30 2 16 8 31 22 

<<<<<<<<<< 삽입 정렬 수행 >>>>>>>>>>

 1단계 :  10  69  30   2  16   8  31  22 
 2단계 :  10  30  69   2  16   8  31  22 
 3단계 :   2  10  30  69  16   8  31  22 
 4단계 :   2  10  16  30  69   8  31  22 
 5단계 :   2   8  10  16  30  69  31  22 
 6단계 :   2   8  10  16  30  31  69  22 
 7단계 :   2   8  10  16  22  30  31  69

이 삽입 정렬의 시간복잡도 또한 선택 정렬, 버블 정렬 그리고 퀵 정렬의 최악의 경우와 동일하다.

셸 정렬 Shell Sort

셸 정렬은 일정한 간격으로 떨어져 있는 자료들끼리 부분집합을 구성하고, 각 부분 집합에 있는 원소에 대해 삽입 정렬을 수행하는 작업을 반복하여 전체 원소를 정렬하는 방법이다.

이러한 셸 정렬은 전체 원소에 대해 삽입 정렬을 수행하는 것보다 부분집합으로 나누어 삽입 정렬하면 비교 연산과 자리 이동 연산의 횟수를 줄일 수 있다.

 

삽입 정렬의 작동 과정의 예

셀 정렬에서 부분 집합을 만드는 기준이 되는 간격을 매개변수 h에 저장한 후에 한 단계가 수행될 때마다 h값을 감소시키고 셸 정렬을 순환 호출하는데, 결국 h가 1이 될 때까지 반복하면서 정렬을 완성한다.

이러한 셸 정렬의 성능은 매개변수 h값에 따라 달라지는데 일반적으로 사용하는 h값은 원소 개수의 1/2을 사용하고 한 단계를 수행할 때마다 h값을 반으로 감소시키면서 반복 수행한다.

주어진 배열: {69, 10, 30, 2, 16, 8, 31, 22}

첫 번째 단계 (h=4):

• 배열을 4개의 부분 배열로 나눕니다: {69, 16}, {10, 8}, {30, 31}, {2, 22}
• 각 부분 배열을 삽입 정렬로 정렬합니다:
  • {69, 16}을 정렬: {16, 69}
  • {10, 8}을 정렬: {8, 10}
  • {30, 31}을 정렬: {30, 31}
  • {2, 22}을 정렬: {2, 22}
• 정렬된 배열을 합칩니다: {16, 8, 30, 2, 69, 10, 31, 22}

두 번째 단계 (h=2):

• 배열을 2개의 부분 배열로 나눕니다: {16, 30, 69, 31}, {8, 2, 10, 22}
• 각 부분 배열을 삽입 정렬로 정렬합니다:
  • {16, 30, 69, 31}을 정렬: {16, 30, 31, 69}
  • {8, 2, 10, 22}을 정렬: {2, 8, 10, 22}
• 정렬된 배열을 합칩니다: {16, 2, 10, 22, 8, 30, 69, 31

세 번째 단계 (h=1):

• 배열을 하나의 부분 배열로 나눕니다 (전체 배열).
• 전체 배열을 삽입 정렬로 정렬합니다: {2, 8, 10, 16, 22, 30, 31, 69}

이러한 과정을 거치면 최종적으로 배열이 정렬됩니다. 여기서 간격 h가 계속해서 감소하면서 삽입 정렬이 수행되는 것을 볼 수 있다.

#include <stdio.h>

void intervalSort(int a[], int begin, int end, int interval) {
	int i, j, item;
	for (i = begin + interval; i <= end; i = i + interval) {
		item = a[i];
		for (j = i - interval; j >= begin && item < a[j]; j = j - interval)
			a[j + interval] = a[j];
		a[j + interval] = item;
	}
}

void shellSort(int a[], int size) {
	int i, interval;
	interval = size / 2;
	while (interval >= 1) {
		for (i = 0; i < interval; i++)  intervalSort(a, i, size - 1, interval);
		printf("\n interval=%d >> ", interval);
		for (i = 0; i < size; i++) printf("%d ", a[i]);
		printf("\n");
		interval = interval / 2;
	}
}

int main(void) {
	int list[8] = { 69, 10, 30, 2, 16, 8, 31, 22 };
	int size = sizeof(list) / sizeof(list[0]); 	// list 배열의 원소 개수
	printf("\n정렬할 원소 : ");
	for (int i = 0; i < size; i++)  printf("%3d ", list[i]);
	printf("\n\n<<<<<<<<<< 셸 정렬 수행 >>>>>>>>>>\n");
	shellSort(list, size);  // 쉘 정렬 함수 호출

	getchar();  return 0;
}
---------------------------------
정렬할 원소 :  69  10  30   2  16   8  31  22 

<<<<<<<<<< 셸 정렬 수행 >>>>>>>>>>

 interval=4 >> 16 8 30 2 69 10 31 22 

 interval=2 >> 16 2 30 8 31 10 69 22 

 interval=1 >> 2 8 10 16 22 30 31 69

 

 

이러한 셸 정렬의 시간복잡도는 시간 복잡도: O(n log n) - O(n^2)로 기존의 선택 정력, 버블 정렬,  퀵의 최악의 경우, 삽입 정렬의 시간 복잡도: O(n^2)보다 개선된 방법이다.