알고리즘 (3): 쉘 정렬, 힙 정렬

---

쉘 정렬 (Shell Sort)

• 멀리 떨어진 원소끼리 교환하여 정렬 속도를 향상시키는 정렬 알고리즘

• 삽입 정렬을 변형하여 병렬 처리로서 정렬을 수행한다.

• 교환할 원소들의 Gap을 서서히 줄여가면서 최종적으로 i번째 인덱스와 i+1번째 인덱스의 교환들로 정렬이 마무리된다.

• 최대 Gap의 크기를 어떻게 설정하는 가, gap이 1까지 줄어드는 과정에 따라 수행시간이 변화한다.

• 최대 gap의 크기는 2~3개의 원소를 비교하도록 설정하고 비교한 결과단위를 합쳐서 다시 검사하는 Divide & Conquer 방식을 사용한다면 비교회수는 $N^{1.5}$를 넘지 않아 빠른 수행시간을 갖는다는 장점이 있다.

//shellsort 알고리즘
void shellsort(int n,int *array){
    int h,v,i,j;
    //병렬처리의 수를 최대로 할 수 있는 gap찾기
    //2~3개의 원소씩 병렬처리할 gap을 찾아 효율을 높일 수 있다.
    for(h=1; h<n;h=3*h+1); 
    //높은 gap에서부터 병렬처리후 낮은 gap의 병렬처리로 이동
    for(;h>0;h=h/3){    
        //gap만큼 떨어진 원소끼리 삽입정렬
        // i를 h+1부터 n까지로 설정한 이유는 그 이하의 인덱스를 gap만큼 빼면서 검사하기때문.
        for(i=h+1;i<=n;i++){    
            v=array[i]; //shellsort는 삽입정렬을 병렬처리한것.
            j=i;
            //비교 과정에서 삽입정렬과 쉘정렬의 차이는 
            //비교할 원소의 인덱스 차이가 1이냐 그보다 많은가에 있다.
            while(j>h && array[j-h]>v){ 
                array[j] = array[j-h];  
                j=j-h;
            }
            array[j] = v;
        }
    }
}

힙 정렬(HeapSort)

• 힙을 이용해 정렬하는 알고리즘

• 힙은 자식과 부모간의 대소관계 규칙을 갖는 우선 순위 큐(Priority Queue)의 일종

• 루트 노드는 오름차순/내림차순 정렬의 최우선 값을 갖는다.

• 루트 노드를 가져오고 삭제하면서 자식 노드들 중 최대/최소 값을 계산하여 루트노드로 변경하는 작업을 통해 힙의 규칙을 유지

• 리스트의 수만큼 루트노드를 꺼내어 순서대로 리스트를 형성하면 정렬된 리스트를 얻을 수 있음

• 힙은 부모-자식간의 규칙이 있지만 같은 깊이의 노드들에 대해 규칙이 존재하지 않는다. 따라서 같은 값에 대해 입력순서가 지켜지지 않아 불안정적이다.

• 같은 깊이의 노드들은 $2^{깊이}$ 만큼의 노드를 가질 수 있다. 정렬시 자식과의 비교만이 이루어지므로 N개의 원소의 정렬에 대하여 $N \log{N}$의 수행시간을 갖는다.

//힙정렬 알고리즘
void inplaceHeap(int* arr,int length){
    //배열은 1~(length)까지있음
    //heapify (leaf노드들은 어짜피 자식 노드가 없으므로 leaf의 부모 노드들부터 자식노드들과 비교)
    for(int i=length/2; i>=1;i--){
        heapify(arr,i,length);
    }
    //힙으로 만든 배열을 오름차순으로 배열화
    for(int i=length-1;i>=1;i--){ //swap으로 보낸 root는 건들지 않는다.
            //마지막 원소를 root와 swap하는것으로 오름차순으로 맨 뒤에서부터 fix한다.
            int temp = arr[1];
            arr[1] = arr[i+1];
            arr[i+1] = temp;
            heapify(arr,1,i);
    }

}
//heapify-현재 값을 자식 노드들과 비교하며 swap한다.
void heapify(int* arr, int h, int m){
    int v = arr[h];
    int j =2*h;//leftchild의 위치를 찾는다.
    for(; j<=m;j=2*j){  //child로 내려가면서 값을 비교한다.
        if(j<m && arr[j]>arr[j+1]) j=j+1;  //leftchild rightchild 비교해서 더 작은 값과 비교

        if(v<=arr[j]) break; //상위 값이 자식값보다 크다면 더이상 볼필요없음

        else arr[j/2] = arr[j]; //부모노드로 이동

    }
    arr[j/2] = v;

}