[알고리즘][정렬] - 쉘 정렬

쉘 정렬이란?

배열을 부분적으로 정렬된 여러 개의 서브 배열로 나누고

각 서브 배열에 대해 삽입 정렬을 수행함으로써

전체 배열을 점진적으로 정렬하여 삽입 정렬을 개선한 정렬 알고리즘

(삽입 정렬에 대한 설명 보러 가기)

 

작동 원리

 1. 배열의 전체 길이에 따라 초기 간격(gap)을 설정한다

(보통 전체 길이의 절반이며, 홀수 권장)

 

2. 설정된 간격만큼 떨어진 요소들을 담은 부분 리스트를 생성한다

(부분 리스트의 개수는 간격과 같다)

 

3. 부분 리스트의 요소들을 비교하여 각각 삽입 정렬한다

 

4. 정렬 후, 간격을 절반으로 축소한다

(축소할 때마다 하나의 부분 리스트에 속한 값들은 증가)

 

5. 간격이 1 에 도달하면 전체 리스트를 삽입 정렬한다

 

작동 예시

쉘 정렬

 

쉘 정렬 메소드 예시

public void shellSort(int[] array) {
    int arrayLength = array.length;
    
    // 초기 간격 4
    for (int gap = 4; gap > 0; gap /= 2) {
    
        // 각 간격에 따른 삽입 정렬 
        for (int i = gap; i < arrayLength; i++) {
            int temp = array[i];
            int j;
            
            for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                array[j] = array[j - gap];
            }
            
            array[j] = temp;
        }
    }
}

 

장점

간단한 코드 구현

삽입 정렬에 비해 더 빠른 속도

추가 메모리 사용이 거의 없음

 

주의점

간격의 선택에 따라 성능이 좌지우지되므로 주의 필요

삽입 정렬에 비해서는 개선됐지만 여전히 대규모 데이터셋에는 비적합

 

 

 

최악의 시간 복잡도: O(n^2)

평균 시간복잡도: O(nlog(n))