삽입 정렬과 셸 정렬 (JAVA 예시 코드 포함)

삽입정렬 Insert Sort

부분집합 S: 정렬된 앞 부분의 원소들

부분집합 U: 정렬 아직 안 된 나머지 원소들 (뒷 부분)

(삽입 정렬을 반복하면서 점점 전체가 S가 되고, U가 공집합이 되면 정렬 완료)

 

:: 정렬 과정 ::

- 초기상태: S는 첫번째 원소 하나, 나머지는 U로 가정

- U의 원소를 하나씩 꺼내어 S의 마지막 원소부터 비교해가면서 위치를 찾아 삽입

 

:: 특징 ::

- 메모리 사용공간: 추가로 필요한 메모리 공간이 없음. (n개의 원소에 대해 n개의 메모리 사용)

- 성능(상의 문제): 

     최악의 경우 (모든 원소가 역순으로 되어있어 비교횟수 최대) 시간 복잡도: O(n^2)

     평균 시간 복잡도: O(n^2)

class InsertSort {
	public void sort(int[] a) {
		for (int i = 1; i < a.length; i++) {  
			for (int j = i; j > 0; j--) {     
				if (a[j] < a[j-1]) swap(a, j, j-1);
				else break;
			}
		}
	}
	
	public void swap(int[] arr, int x, int y) {
		int temp = arr[y];
		arr[y] = arr[x];
		arr[x] = temp;
	}
}

---

셸 정렬 Shell Sort

자료들을 일정한 기준으로 부분집합들로 나누고, 각각에 대해 삽입 정렬 수행

부분집합 나누기: 일정한 간격 (h) 만큼 떨어져 있는 원소들을 같은 부분집합으로 만듦

* 전체를 여러 부분들로 나누어 각각에 대해 정렬을 하여 성능 개선 (삽입 정렬의 시간복잡도를 개선한 정렬 방법)

 

:: 정렬 과정 ::

ex) 원소가 8개인 전체 집합

h = 4: 네 개의 부분집합들에 대해 각각 삽입 정렬 수행

h = 2: 두 개의 부분집합들에 대해 각각 삽입 정렬 수행 (셸 정렬 순환 호출)

h = 1: 한 개의 부분집합 (전체 원소)에 대해 삽입 정렬 수행 (셸 정렬 순환 호출)

* 한 단계가 수행될 때마다 h를 감소시키고 셸 순환 호출, h가 1이 될 때까지 반복

 

:: 특징 ::

- 메모리 사용공간: 매개변수 h를 위한 추가 저장공간 필요. (이 외에는 n개의 원소에 대해 n개의 메모리 사용)

- 성능:

    처음 원소의 상태에 관계없이 h에 의해 결정

    일반적인 시간복잡도: O(n^1.25)  =>> 삽입 정렬보다 개선된 정렬 방법

class ShellSort {
	public int h;
	public void sort(int[] a) {
		h = a.length / 2;  
		while (h >= 1) {
			for (int i = h; i < a.length; i++) {     
				for (int j = i; j > 0; j = j - h) {  
					if (a[j] < a[j-h]) swap(a, j, j-h);
					else break;
				}
			}
			h = h / 2;
		}
	}
	public void swap(int[]arr, int x, int y) {
		int temp = arr[y];
		arr[y] = arr[x];
		arr[x] = temp;
	}
}