[Sort] 셸 정렬(Shell Sort)

셸 정렬(Shell Sort)

 

[출처: 위키]

정의: 일정한 간격으로 떨어져 있는 자료들끼리 부분집합을 구성하고 

각 부분집합에 있는 원소들에 대해서 삽입 정렬을 수행하는 작업을 반복하면서 

전체 원소들을 정렬 하는 방법

부분 집합을 만드는 기준은 원소 개수의 반으로 나누어서 반복 수행한다.

자 정의는 이정도로 하고 시작할까요??

---

1단계

 

1단계 정렬 전입니다!!

자 먼저 부분 집합을 만들기 위해

원소 갯수 / 2 를 통해

4 라는 숫자를 만들어 둡시다.

4라는 숫자를 기준으로 부분 집합을 만들어 봅시다!!

자 이렇게 나옵니다!

 

4개의 부분 집합으로 보이시죠??

{69, 16}, {10, 8}, {30, 31}, {2, 22}

이렇게 색깔 별로 다르게 해서 집합을 4개 표현 했습니다!!!

집합을 하고 나면 집합내에서 

삽입 정렬을 수행합니다!!!!

1. {69, 16}

69가 뒤로 가야 겠죠??? 

둘이 자리가 바뀌게 됩니다!!

 

2. {10, 8}

10이 더 크네요~

바뀌는게 지당하겠죠??

 

3. {30, 31}

은 변동이 없겠네요~~

그럼 Pass~

4. {2, 22}

도 마찬 가지네요~

결국 이상태로 1단계가 끝납니다!!!

 

---

---

2단계

자 그럼 아까는 부분 집합이 4였죠~?

여기에 다시 2로 나눠줍니다!

그럼 이번엔 

부분 집합의 갯수 = 2

아래 처럼 묶이겠네요~

 

그럼 그룹 

{16,30,69,31}

{8,2,10,22} 

로 나뉘어서 그룹별로 삽입정렬을 합니다!!!

삽입 정렬은 앞의 포스팅에 있으니 정렬은 아래처럼 됩니다!

먼저 첫번째 그룹만 삽입정렬!!!

 

그럼 두번째 그룹 삽입정렬!!

 

이렇게 이번 단계가 마무리 되겠네요~?

---

---

3단계

 

자 이번에는 뭘 해야 할지 감이 오시죠??

부분 집합을 또 나눠줘야 합니다!!

그럼 이번엔 1이네요~

전체가 부분집합이 되는거니 걍 삽입 정렬 해야겠네요 ~?

삽입 정렬 하는 거기에 정렬된 결과는 아래와 같습니다~

 

자 이렇게 해서 셸 정렬이 끝입니다!!!

어떻게 보면 셸 정렬 ??

그냥 삽입 정렬 쓰는 거 아닌가?? 

할수도 있지 않나요???

 

여기서 약간의 특혜가 있는겁니다!!

삽입 정렬은 원래! "거의 정렬" 되어 있는 경우 효율적인 특징이 있는데

그걸 이용했다고 보시면 됩니다!

 

---

이 셸 정렬의 시간 복잡도(Time Complexity)는 아래와 같습니다!

Worst인 경우!!

Best 인 경우!!

 

Average는 

Gap에 따라 다르다!

소스 코드로 넘어가 보도록 하겠습니다!!

ShellMain.java

 

package Shell;
 
public class ShellMain {
    public static void main(String[] args) {
        int[] arr = { 69, 10, 30, 2, 16, 8, 31, 22 };
 
        ShellSort.shellSort(arr);
    }
}
 

ShellSort.java

 
package Shell;
 
import Selection.SelectionSort;
 
public class ShellSort {
    public static void intervalSort(int arr[], int begin, int end, int interval) {
        int item = 0;
        int j = 0;
 
        for (int i = begin + interval; i <= end; i = i + interval) {
            item = arr[i];
            for (j = i - interval; j >= begin && item < arr[j]; j -= interval)
                arr[j + interval] = arr[j];
            arr[j + interval] = item;
        }
    }
 
    public static void shellSort(int arr[]) {
        int interval = 0;
        int t = 1;
        int arrSize = arr.length;
 
        interval = arrSize / 2;
 
        while (interval >= 1) {
            for (int i = 0; i < interval; i++)
                intervalSort(arr, i, arrSize - 1, interval);
            System.out.println("셸 정렬 " + t++ + " 단계:  interval => " + interval);
 
            SelectionSort.printArr(arr);
 
            interval /= 2;
        }
    }
}
 

 

결과는 아래와 같답니다~