Java - 정렬 알고리즘 - 8 (셸 정렬)

◎셸 정렬

삽입 정렬이 어느 정도 정렬되어 있는 배열에 대해서는 대단히 빠르다는 점을 이용하여, 삽입 정렬을 보완한 알고리즘

---

◎삽입 정렬의 문제점

삽입 정렬은 타깃 원소가 앞의 숫자보다 작으면 앞의 원소들을 모두 교환해야 한다는 단점을 가지고 있다.

ex. [1,2,3,4,0]인 배열이 있다고하면, 맨 마지막 원소인 0 때문에,

[0,2,3,4,1]

[0,1,3,4,2]

[0,1,2,4,3]

[0,1,2,3,4]

의 과정을 거치며 모든 원소들을 교환하는 비효율적인 상황이 발생한다

---

◎셸 정렬의 특징

 

1.  비교 정렬(comparison sort)

 셸 정렬은 데이터를 비교하면서 찾는다.

 

2. 제자리 정렬(in-place sort)

정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않는다.

 

3. 불안정 정렬(unstable sort)

정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지되지 않는다.

 

---

 

◎셸 정렬의 동작

셸 정렬은 원래의 배열을 gap의 크기로 나누어 정렬함으로써, 정렬이 되어있을수록 시간 복잡도가 O(n)에 가까워지는 선택 정렬의 장점을 가지고, 원소들의 대략적인 위치들을 잡아줌으로써 선택 정렬의 단점은 줄였다.

출처: https://st-lab.tistory.com/209

round 1에서는 gap이 4이므로, index (0,4), (1,5), (2,6), (3,7) 끼리 선택 정렬한다

round 2에서는 gap이 2이므로, index (0,2,4,6), (1,3,5,7) 끼리 선택 정렬한다

round 3에서는 gap이 1이므로, 전체 원소를 대상으로 선택 정렬한다.

round가 늘어날수록 원소들의 대략적인 위치들이 잡히기 때문에 정렬된 배열에서 최대의 성능을 발휘하는 선택정렬의 장점을 극대화할 수 있다.

---

◎셸 정렬, gap의 크기

gap의 크기에 따라 셸 정렬의 성능이 달라지기 때문에 gap의 크기를 잘 정하는 것이 중요하다.

하지만 어떤 gap크기가 제일 효율적인지는 검색해봐도 정확히 나와있지 않다.

 

1. Array.length/2를 초기 gap의 크기로 정하는 방법

2. Array.length/2를 초기 gap의 크기로 정하지만, gap의 크기가 짝수일 경우 홀수로 만들어주는 방법

3. 효율적이라고 알려진 { 1, 4, 10, 23, 57, 132, 301, 701, 1750, 3937, 8858, 19930, 44842, 100894, 227011, 510774,1149241, 2585792, 5818032, 13090572, 29453787, 66271020, 149109795, 335497038, 754868335, 1698453753} 배열의 값을 gap의 크기로 쓴 방법

 

※무엇이 더 좋은 방법인지는 잘 안나와있지만, 2번 방법을 사용하여 셸 정렬을 구현하였다

---

◎셸 정렬의 구현

 

package SortAlgorithm;

public class sort {
	//셸 정렬-1
	private void shellsort(int[] numarr) {
		
		//gap이 홀수 일때 효율적이라고 알려져있다.
		int gap = numarr.length / 2;
		if(gap != 0 && gap % 2 ==0 ) {
			gap++;
		}
		
		while(gap>= 1) { //gap이 1일때가 마지막 회차
			for(int i=0; i<gap; i++) {
				//gap만큼 idx가 차이나는 원소끼리 선택정렬
				//ex. gap이 3이면, 0,3,6,9.... 원소끼리 선택정렬한다
				innershellsort(numarr, gap, i);
			}
			
			gap = gap / 2;
			if(gap != 0 && gap % 2 ==0 ) {
				gap++;
			}
			
		}
		
		print(numarr, "셸 정렬");
		
	}
	
	//셸 정렬(셸 정렬 내부에서 사용하는 선택정렬 구현) -2 
	private void innershellsort(int[] numarr, int gap, int start) {
		for(int i = start; i< numarr.length -1; i=i+gap) {
			int min = i;
			for(int j = i+gap; j<numarr.length; j=j+gap) {
				// 최솟값을 가진 인덱스 찾기
				if (numarr[j] < numarr[min]) {
					min = j;
				}
			}
			// i 번째 값과 최솟값을 교환
			swap(numarr, i, min);
		}
	}
	
	// swap
	private void swap(int[] numarr, int i, int j) {
		int temp = numarr[i];
		numarr[i] = numarr[j];
		numarr[j] = temp;
	}

	// 출력
	private void print(int[] numarr, String sortname) {
		System.out.println(sortname + "로 정렬된 배열:" + Arrays.toString(numarr));
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] numarr = { 5, 1, 3, 4, 2, 6 }; // 정렬할 배열
		System.out.println("원래 배열:" + Arrays.toString(numarr));

		sort Sort = new sort();

		Sort.shellsort(numarr);

	}
}

실행 결과:

원래 배열:[5, 1, 3, 4, 2, 6]
셸 정렬로 정렬된 배열:[1, 2, 3, 4, 5, 6]

---

◎Sorting algorithm 시간 복잡도(time complexity) & 평균 정렬 속도(average sorting rate)

Sorting algorithm 시간복잡도(time complexity) & 평균 정렬 속도(average sorting rate) 출처:     https://st-lab.tistory.com/195

 

 

---

◎정렬 알고리즘 구현-github

github.com/jerry-ryu/java_problemsolving_algorithm/tree/main/sorting_algorithm