ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Sort] 셸 정렬(Shell Sort)
    CSE/Sort 2015. 6. 12. 15:44

    셸 정렬(Shell Sort)






     


    [출처: 위키]



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

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

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



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



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






    1단계




     


    1단계 정렬 전입니다!!



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


    원소 갯수 / 2 를 통해


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


    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이네요~


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



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


     



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



    어떻게 보면 셸 정렬 ??


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


    할수도 있지 않나요???

    a_bosss_life-21 



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


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


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


     







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


    Worst인 경우!!








    Best 인 경우!!


     


    Average는 


    Gap에 따라 다르다!






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



    ShellMain.java

     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    package Shell;
     
    public class ShellMain {
        public static void main(String[] args) {
            int[] arr = { 69103021683122 };
     
            ShellSort.shellSort(arr);
        }
    }
     
    cs




    ShellSort.java

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
     
    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;
            }
        }
    }
     
    cs

     




    결과는 아래와 같답니다~


     




     


    'CSE > Sort' 카테고리의 다른 글

    [Sort] 힙 정렬(Heap Sort]  (2) 2015.06.12
    [Sort] 기수 정렬(Radix Sort)  (0) 2015.06.12
    [Sort] 합병 정렬(Merge Sort)  (0) 2015.06.12
    [Sort] 퀵 정렬(Quick sort)  (1) 2015.06.12
    [Sort] 삽입 정렬(Insertion sort)  (0) 2015.06.12
    [Sort] 버블 정렬(Bubble Sort)  (0) 2015.06.12

    댓글

Designed by Tistory.