[알고리즘/정렬 알고리즘] 셸 정렬 (Shell sort) Java, Python

셸 정렬(Shell sort) 알고리즘의 개념

• 셸 정렬(Shell sort)은 삽입 정렬의 장점은 살리고 단점은 보안하여 좀 더 빠르게 정렬하는 알고리즘으로 D. L. Shell이 고안했다.
• 먼저 정렬할 배열의 요소를 그룹으로 나눠 각 그룹 별로 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법이다.

셸 정렬(Shell sort) 알고리즘 세부 과정

1. 정렬할 배열을 일정한 기준(간격)에 따라 분류
2. 각 부분 배열을 삽입 정렬로 정렬
3. 다시 전체 배열을 더 적은 개수의 부분 배열로 분류
4. 위의 과정(2,3)을 부분 배열의 길이가 1이 될 때까지 반복

셸 정렬(Shell sort) 알고리즘 예제

• 배열의 요소가 8, 1, 4, 2, 7, 6, 3, 5 순으로 저장돼있고 오름차순을 기준으로 정렬할 때 예를 확인해보자

첫 번째 정렬 : 간격 - 4칸, 부분 배열 - 4개

 

두 번째 정렬 결과

• 간격(gap)은 정렬할 배열의 길이 / 2
• 생성된 부분 배열의 개수는 gap의 크기와 같다.
• 위와 같은 과정을 1개의 부분 배열이 나올 때 까지 하면 된다. 

[Java 코드]

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8, 1, 4, 2, 7, 6, 3, 5};
        int N = arr.length;
        
        for(int h = N / 2; h > 0; h /= 2) {           //간격
            for(int i = h; i < N; i++) {            //삽입 정렬을 하기 위해 부분 배열의 두 번째 값을 가지고 값을 비교한다.
                int j;
                int temp = arr[i];                    //ex 간격이 4이면 처음 arr[i]는 7이다. 7 ~ 5까지 삽입 정렬 시작
                
                for(j = i - h; j >= 0 && arr[j] > temp; j -= h) {  //부분 배열끼리 연산하도록 j = i - h 
                    arr[j + h] = arr[j];                           //삽입 정렬을 위해 한칸 씩 미뤄준다.
                }
                arr[j + h] = temp;                                   //조건문을 빠져나온 j는 이미 j-h연산이 끝났으므로 다시 +h를 해준다.
            }
        }
        
        for(int a : arr) {
            System.out.print(a +" ");
        }
    }
 
}

 

[Python 코드]

def shell_sort(arr):
    N = len(arr)
    h = N // 2
    while h > 0:
        for i in range(h, N):
            temp = arr[i]
            j = i - h
            while j >= 0 and arr[j] > temp:
                arr[j + h] = arr[j]
                j -= h
            arr[j + h] = temp
        h //= 2
 
    print(arr)
 
 
arr = [8, 1, 4, 2, 7, 6, 3, 5]
shell_sort(arr)