PSD( Private-Self-Development )

쉘 정렬( Shell sort ) 알고리즘 본문

Backend/알고리즘

쉘 정렬( Shell sort ) 알고리즘

chjysm 2022. 12. 13. 15:16

쉘 정렬 알고리즘?

삽입 정렬을 보완한 알고리즘

 

정렬 절차

  1. 먼저 정렬해야 할 리스트를 일정한 기준( ex. 일정 간격 마다 자른다 )에 따라 분류
  2. 연속적이지 않은 여러 개의 부분 리스트를 생성
  3. 각 부분 리스트를 삽입 정렬을 이용하여 정렬
  4. 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 반복
  5. 위의 과정을 부분 리스트의 개수가 1이 될 때까지 반복

 

특징

장점

  • 삽입 정렬 보다 성능이 좋다.
  • 삽입 정렬의 단점인 레코딩 이동이 많은 점을 보완
  • 알고리즘이 간단하여 쉽게 구현 가능하다.

 

구현

public static void shellSort( int[] target ){
    shellSort( target, getGap( target.length ) );
}

public static int getGap( int target ){
    int nextGap = target / 2;
    if( target % 2 == 0 ){
        nextGap++;
    }
    return nextGap;
}

public static void shellSort( int[] target, int gap ){

    // gap 이 1 이면 그만!
    if( gap == 1 ){
        return;
    }

    // 리스트 개수
    int partNum = target.length / gap;
    if( target.length % gap != 0 ){
        partNum++;
    }

    // 리스트 별로 시작, 종료 인덱스 설정 후 삽입 정렬
    for( int i = 0; i < partNum; i++ ){
        int firstIndex = i*gap;
        int endIndex = (i+1)*gap-1;
        if( target.length < endIndex ){
            endIndex = target.length-1;
        }

        // 삽입 정렬
        shell_insertionSort( target, firstIndex, endIndex );
    }

    // 재귀
    shellSort( target, getGap( gap ) );
}

public static void shell_insertionSort( int[] target, int firstIndex, int endIndex ) {
    for( int i = firstIndex + 1; i <= endIndex; i++ ){
        int pick = target[i];
        int j;
        for( j = i-1; j >= 0 && target[j] > pick; j-- ){
            // 오른쪽이동
            target[j+1] = target[j];
        }

        target[j+1] = pick;
    }
}

 

 

시간 복잡도

최상 : n

평균 : n^1.5

최악 : n^2

 


참고 

https://gmlwjd9405.github.io/2018/05/08/algorithm-shell-sort.html

 

[알고리즘] 셸 정렬(shell sort)이란 - Heee's Development Blog

Step by step goes a long way.

gmlwjd9405.github.io