셸 정렬(Shell Sort)

- 셸 정렬은 해당 작업을 반복한다

1. 비교 간격을 정하고 간격 당 값을 그룹화한다

2. 만들어진 그룹을 삽입 정렬을 통해 정렬한다

3. 비교 간격을 절반으로 줄인다

(간격이 1이 될 때까지 진행하며 1일 경우 전체 정렬을 수행하게 되므로 종료)

 

평소에 알고리즘을 공부를 잘 안해서 개인적으로 쉘 정렬이 제일 어려웠다

이참에 정리하면서 도움이 돼 앞으로 더 유연한 사고를 가질 수 있을 것 같다

 

이 글을 보는 사람이 이해가 쉽게 추가로 첨언하자면

 

입력 값인 배열이 [ 3, 5, 1, 2, 6 ]가 존재한다면

괭이질하듯이 gap부터 뒤로 차례대로 이동한다

gap부터 시작하고 배열 끝까지 차례대로 진행

2와 0을 비교 -> 3과 1을 비교 -> 4와 2를 비교

비교할 땐 지금 gap이 있는 값을 key로 저장하고

key 값과 gap만큼 뒤에 있는 것을 계속해서 비교하면서

크다면 복사해서 뒤로 땡겨오고 비교가 전부 끝나면

마지막 복사한 값의 위치에 key 값을 덮어쓴다

그리고 gap을 줄이고 다시 반복

 

밑의 예제는 예제로 짠 코드의 중간 출력으로 도움이 되길 바란다

ex) gap : 2, key : 4
[1, -10, 9, -5, 11, 3, 4, 7, 13]
[1, -10, 9, -5, 11, 3, 11, 7, 13]
[1, -10, 9, -5, 11, 3, 11, 7, 13]
[1, -10, 9, -5, 9, 3, 11, 7, 13]
[1, -10, 4, -5, 9, 3, 11, 7, 13]

 

 

- 자바로 간단한 예제를 짜고 주석을 달아놓고

//n개 입력 값을 받음(입력 값을 모른다는 가정)
int[] array = new int[n];

//비교 간격
int gap = array.length;
//정렬 중인 값
int key;
//비교 번호
int compareIdx;

//비교 간격을 위한 순환(편의상 n/2로 설정)
while((gap >>= 1) > 0) {
    //비교 간격 만큼의 배열을 위한 순환
    for(int i = gap; i < array.length; i++) {
        key = array[i];
        compareIdx = i;
        
        //비교 간격 만큼 떨어진 요소들을 비교하여 정렬
        while(compareIdx >= gap && array[compareIdx - gap] > key) {

            //요소를 이동
            array[compareIdx] = array[compareIdx - gap];
            compareIdx -= gap;
        }
        
        //정렬 할 위치에 값 삽입
        array[compareIdx] = key;
    }
}

//결과 출력
System.out.println(Arrays.toString(array));

 

 

- 마지막으로 시간 복잡도(Big-O)에 대해 말하자면

간격에 따라 시간 복잡도가 정해지며 계산 방법이 어렵다고 하여

일단 챗 지피티한테 정리를 부탁 후 복붙을 해놓겠다

밑에 수열들은 해당 수열을 만든 사람의 이름으로

연구자, 과학자, 수학자들이 실험 및 연구를 통해 나온 성능이므로 이의 없음

 

특이 사항으로 최선(최적) 예를 들어

거의 정렬이 돼있다면 O(NlogN)을 가지며

평균적으로 O(N^1.25) ~ O(N^1.5)을 가지지만

시간 복잡도는 최악인 경우를 상정하여

 

셸 정렬은 O(n^2)의 시간 복잡도를 가진다