정렬, 쉘 정렬(Shell Sort)

1. 쉘 정렬(Shell Sort)

쉘 정렬은 일정한 너비만큼 떨어진 요소를 가져와서 그 둘을 대소비교한 후 바꾸는 방법입니다. 처음에는 큰 간격으로 시작해서 더 적은 가격으로 정렬을 하고 간격의 크기가 1이 되면 삽입 정렬을 수행합니다. 즉, 쉘 정렬은 작은 값을 가진 요소는 오른쪽에서 왼쪽으로 옮기고 큰 값을 가진 요소는 왼쪽에서 오른쪽으로 옮기는 알고리즘입니다.

 

쉘 정렬은 중복된 숫자의 순서가 보장되지 않는 불안정 정렬(not stable sort)입니다. 그리고 리스트 안에서 순서만 바꾸어주기 때문에 in-place 정렬입니다.

 

최악의 경우, 삽입 정렬과 같아지므로 시간 복잡도는 O(n²)입니다. 쉘 정렬의 평균적인 시간 복잡도는 얼마의 간격을 사용했는지에 따라 달라집니다.

 

쉘 정렬은 삽입 정렬을 보완한 알고리즘입니다. 삽입 정렬은 어느 정도 정렬된 배열에서는 정렬 속도가 대단히 빠릅니다. 그러나 삽입 정렬의 문제점은 정렬되지 않은 배열에 대해서는 정렬 속도가 느리다는 점입니다. 이는 삽입 정렬이 정렬을 하기 위해 이웃한 위치로 계속 이동을 하기 때문에 만약 삽입되어야할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있습니다.

 

따라서 쉘 정렬은 삽입 정렬을 보완한 알고리즘으로써 간격에 따른 부분 리스트를 생성하고 부분 리스트에 대해서 삽입 정렬을 수행하여 어느 정도 정렬된 배열을 만드는데 목적을 두고 있습니다.

 

2. 쉘 정렬의 수행과정

쉘 정렬의 수행과정은 다음과 같습니다. 간격을 절반씩 줄일때 간격이 짝수라면 +1하여 홀수로 만들어줍니다. 이유는 간격이 1이 되기전 최대한 많이 부분리스트에서 대소를 비교하여 교환하여야 하기 때문입니다.

 

3. 쉘 정렬 구현

public class ShellSort {
	public static void sort(int[] arr)
	{
		int n = arr.length;
		
		// 큰 간격(배열의 절반 길이)에서 시작하여 간격이 1이 될때까지 절반씩 줄임
		for(int gap = n/2; gap>0; gap/=2)
		{
			if(gap%2==0)
			{
				gap++;	// gap을 홀수로 만듬
			}
			
			// 간격(gap)에 따른 여러개의 부분 리스트들을 생성함
			for(int i=gap;i<n;i++)
			{
				// 한개의 부분리스트에서 삽입 정렬을 수행하기 위한 기준값
				int temp = arr[i];
				
				// 한개의 부분리스트에서 삽입 정렬을 수행
				int j;
				for(j=i; j>=gap && arr[j-gap] > temp; j-=gap)
				{
					arr[j] = arr[j-gap];
				}
				arr[j] = temp;
			}
		}
	}
}

class ShellSortTest {

	@Test
	void test() {
		int[] arr = {7,10,5,3,6,4,1,8,9,2};
		System.out.println(Arrays.toString(arr));
		ShellSort.sort(arr);
		System.out.println(Arrays.toString(arr));
	}
}

[7, 10, 5, 3, 6, 4, 1, 8, 9, 2]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

 

References

source code : https://github.com/yonghwankim-dev/DataStruct/tree/main/sort/shell_sort/implement
[GeeksForGeeks] Shell Sort
https://gmlwjd9405.github.io/2018/05/08/algorithm-shell-sort.html
[부스트코스] 쉘 정렬