-> 블로그 이전

[Data Structure] 쉘 정렬 - Shell Sort

2022. 1. 1. 17:21ㆍMajor`/자료구조

쉘 정렬 (Shell Sort)

Unstable Sort

  • 정렬할 리스트의 간격에 따라서 각 부분 리스트를 정렬하는 정렬 알고리즘
  • 간격(gap) = 리스트/2/2/2,...... → 계속해서 2로 나눠준다 (1이 될 때 까지)
  • 만약 gap이 짝수이면 1을 더해준다 (간격이 홀수이면 더 성능이 좋다)
  • 부분 리스트의 개수는 gap과 동일하다
  • 보통 전체에서 h/2를 하지만 이보다 h/3 + 1 이 더 빠르다

 

시간복잡도

- 최선 : O(n)

- 평균/최악 : O(n1.5)

 

장점

- Insertion Sort의 단점을 보완하고 개념을 확대해서 만든 정렬

- Insertion Sort보다 성능이 우수하다

- 데이터가 본인의 index에서 멀리 떨어져 있을 경우, 교환을 여러번하는 Bubble Sort의 단점을 해결

 

단점

- 일정한 간격에 따라서 배열을 해석해야하고, 간격을 잘못 설정하면 성능이 저하된다

 

과정

  1. 정렬할 리스트(A)를 간격에 따라서 부분 리스트를 생성 -- (1)
  2. 각 부분 리스트를 정렬 -- (2)
  3. 간격이 1이 될 때 까지 (1), (2) 반복

 

※ Example

배열 A : {10, 8, 6, 20, 4, 3, 22, 1, 0, 15, 16} / 크기 = 11

▶ Gap = 5 (11/2) → 부분 리스트 5개

index 0 1 2 3 4 5 6 7 8 9 10
List 0 10         3         16
List 1   8         22        
List 2     6         1      
List 3       20         0    
List 4         4         15  

- List 0

  • List 0[5] = 3 (value)
  • → gap만큼 아래로 내려가서 해당 요소와 비교 (index = 5-gap)
  • → List 0[index] (10) > List 0[5] (3)
  • → 서로 자리 change → List 0[index+gap] = List 0[index]
  • → 더 이상 내려갈 수 없기 때문에 List 0[index+gap] = value
  • → List 0[5+gap+gap,... < 10] 까지 동일하게 수행
  • List 1,2,3,4도 동일한 방식으로 수행
3 8 1 0 4 10 22 6 20 15 16

 

▶ Gap = 3 (5/2+1) → 부분 리스트 3개

index 0 1 2 3 4 5 6 7 8 9 10
List 0 3     0     22     15  
List 1   8     4     6     16
List 2     1     10     20    

- List 0

  • List 0[first+gap] = List 0[0+3] = List 0[3] = 0 (value)
  • → gap 만큼 내려가서 해당 요소와 비교 (index = 3-gap)
  • → List 0[index] (3) > List 0[3] (0)
  • → 서로 자리 change → List 0[index+gap] = List 0[index] 후, index-=gap
  • → 더 이상 내려갈 수 없기 때문에 List 0[index+gap] = value
  • → List 0[3+gap+gap+,.... < 10] 까지 동일하게 수행

- List 1

  • List 1[first+gap] = List 1[1+3] = List 1[4] = 4 (value)
  • → gap 만큼 내려가서 해당 요소와 비교 (index = 4-gap)
  • → List 1[index] (8) > List 1[4] (4)
  • → 서로 자리 change 후, index-=gap
  • → 더 이상 내려갈 수 없기 때문에 List 1[index+gap] = List 1[1] = value(4)
  • List 1[4+gap] = List 1[7] = 6(value)
  • → List 1[4] (8) > List 1[7] (6)
  • → 서로 자리 cahnge 후, index-=gap
  • → gap만큼 또 내려가면 해당 요소는 value보다 크므로 변화 X
  • 계속해서 반복
0 4 1 3 6 10 15 8 20 22 16
0 1 3 4 6 8 10 15 16 20 22

 

 

▶ Shell Sort

static void shell_sort(int [] A){
        for(int gap = A.length/2; gap>0; gap/=2){
            if(gap%2==0) gap+=1; // gap이 짝수면 홀수로 만들어주기
            System.out.println("## Gap : " + gap);
            for(int i=0; i<gap; i++) { // gap개수만큼 부분 리스트 생성
                gap_list_sort(A, i, A.length, gap);
            }
        }
    }

    static void gap_list_sort(int []A, int first, int last, int gap){
        // gap에 따른 부분 리스트 (부분 리스트개수 = gap)
        for(int i=first+gap; i<last; i+=gap){
            int value = A[i]; // index가 gap인 위치의 요소
            int index = i-gap; // value보다 낮은 위치의 요소들을 비교
            while((index>=0) && (A[index]>value)){
                // value보다 낮은 위치의 요소가 value보다 크면
                A[index+gap] = A[index];
                // 서로 위치를 change
                index-=gap;
                // gap만큼 내려가서 해당 위치의 요소와도 비교
            }
            A[index+gap] = value;
            // index가 gap인 위치에서부터 시작해서 gap만큼 내려가서 해당 위치에 value insert

            /*
            gap = 3, A[0] = 3, A[3] = 0, A[6] = 22, A[9] = 15
            index가 gap인 위치의 요소 = 0 (value)
            0의 index-gap 위치에 있는 요소와 비교 ( A[index-gap](3) > value )
            -> index-gap 위치에 있는 요소와 index-gap+gap에 있는 요소와 서로 change

            index가 gap+gap+,.... 인 요소들도 똑같이 반복
             */
        }
    }

 

 

▶ Full Code

package Sort;

import java.util.Calendar;

public class Shell_Sort_6 {
    public static void main(String[] args) {
        int [] A = new int[11]; // 정렬할 배열 A

        for(int i=0; i<A.length; i++)
            A[i] = (int)(Math.random()*151); // 0~151

        // 정렬 전 A 출력
        System.out.print("A[]");
        for(int i=0; i<A.length; i++){
            if(i%20==0) System.out.println();
            System.out.print(A[i] + "\t");
        }
        System.out.println("\n");
        shell_sort(A);
    }

    static void shell_sort(int [] A){
        Calendar before = Calendar.getInstance();
        for(int gap = A.length/2; gap>0; gap/=2){
            if(gap%2==0) gap+=1; // gap이 짝수면 홀수로 만들어주기
            System.out.println("## Gap : " + gap);
            for(int i=0; i<gap; i++) { // gap개수만큼 부분 리스트 생성
                System.out.println("-> 부분 리스트 " + i + " 정렬 전");
                for(int t=i; t<A.length; t+=gap){
                    //if(t%20==0) System.out.println();
                    System.out.print(A[t] + "\t");
                }
                System.out.println();
                gap_list_sort(A, i, A.length, gap);
                System.out.println("-> 부분 리스트 " + i + " 정렬 후");
                for(int t=i; t<A.length; t+=gap){
                    //if(t%20==0) System.out.println();
                    System.out.print(A[t] + "\t");
                }
                System.out.println("\n");
            }
            System.out.println();
        }
        Calendar after = Calendar.getInstance();

        // 정렬 후 A 출력
        System.out.print("result[]");
        for(int i=0; i<A.length; i++){
            if(i%20==0) System.out.println();
            System.out.print(A[i] + "\t");
        }
        System.out.println("\n");

        int time = after.get(Calendar.MILLISECOND) - before.get(Calendar.MILLISECOND);
        System.out.println("걸린 시간 : " + time + "ms");
    }

    static void gap_list_sort(int []A, int first, int last, int gap){
        // gap에 따른 부분 리스트 (부분 리스트개수 = gap)
        for(int i=first+gap; i<last; i+=gap){
            int value = A[i]; // index가 gap인 위치의 요소
            int index = i-gap; // value보다 낮은 위치의 요소들을 비교
            while((index>=0) && (A[index]>value)){
                // value보다 낮은 위치의 요소가 value보다 크면
                A[index+gap] = A[index];
                // 서로 위치를 change
                index-=gap;
                // gap만큼 내려가서 해당 위치의 요소와도 비교
            }
            A[index+gap] = value;
            // index가 gap인 위치에서부터 시작해서 gap만큼 내려가서 해당 위치에 value insert

            /*
            gap = 3, A[0] = 3, A[3] = 0, A[6] = 22, A[9] = 15
            index가 gap인 위치의 요소 = 0 (value)
            0의 index-gap 위치에 있는 요소와 비교 ( A[index-gap](3) > value )
            -> index-gap 위치에 있는 요소와 index-gap+gap에 있는 요소와 서로 change

            index가 gap+gap+,.... 인 요소들도 똑같이 반복
             */
        }
    }
}

저작자표시 변경금지

관련글

댓글 0

티스토리툴바