[Algorithm]쉘 정렬, 기수 정렬, 트리 정렬

1. 쉘 정렬: 원소 비교 연산과 먼 거리의 이동을 줄이기 위해 서브리스트로 나누어 삽입 정렬을 반복 수행

2. 방법: 정렬에서 사용할 간격(interval) 결정  ->  첫번째 interval에 따라 서브리스트로 분할  -> 각 서브리스트에 대해 삽입 정렬 수행  ->  ... -> 리스트 전체에 대해 삽입 정렬 수행(마지막 interval = 1)

   - 시간 복잡도: O(n^1.25)

 ---------------- 그림 설명 ----------

3. ShellSort Algorithm

shellSort(a[])
	interval <- a.length;
    while(interval > 1) do{
    	interval <- 1+ interval/3;
        for(i<-0; i<interval; i<-i+1) do {
        	intervalSort(a, i, interval);
        }
    }

4. IntervalSort Algorithm

 intervalSort(a, i, interval)
 						// 서브리스트를 삽입 정렬하는 보조함수
 	j<-i+interval;
    while(j<a.length) do {
    	new <- a[j];	// 서브트리의 새로운 원소
        k <- j 			// new 보다 큰 원소는 interval만큼 오른쪽으로 이동, k는 왼쪽으로 이동
        move <- true;
        while(move) dp {
        	if(a[k-interval]<=new) then move <- false;
            else {
            	a[k] <- a[k-interval];
                k <- k - interval;	// k는 왼쪽으로 interval만큼 이동
                if(k=i) then move <- false;
            }
        }
        a[k] <- new;	// 이동해서 생긴 자리에 삽입
        j <- j + interval;	// 다음 서브리스트 원소의 인덱스
    }

---

1. 기수 정렬: 정렬할 원소의 키 값을 나타내는 숫자의 자리수를 기초로 정렬

2. 방법:

   - 첫번째 pass: 정렬할 키의 가장 작은 자리 수를 기준으로 분배 정렬

   - 두번째 pass: 2번째로 작은 자리 수를 기준으로 분배 정렬(키 값이 같을 때, 이전 정렬에서 순서 유지)

   - 가장 큰 자릿 수까지 반복 수행

   - 시간 복잡도: O(n)

   - RadixSort Algorithm

radixSort(a[])
	n <- a.length;
    for(k=1; k<=m; k++) do{  // m은 digit 수, k=1은 가장 작은 자리수
    	for(i=0; i<n; i++) do {
        	kd <= kth - digit(a[i];
            enqueue(Q[kd], a[i]);  // Q(kd)에 a[i]를 삽입
        }
        p <- -1;
        for(i=0; i<=9; i++) do {
        	while(Q[i]!=0) do{   // Q[i]의 모든 원소를 a[]로 이동
            	p <- p+1;
                a[p] <- dequeue(Q[i]);
            }
        }
    }

3. 알고리즘 실행 단계: 초기 리스트-> a=[35, 81, 12, 67, 93, 46, 23, 26]

---

1. 트리 정렬: 이진 정렬 트리 + 중위 우선 순회 

2. 방법:

   - 배열을 이진트리에 삽입: 동일 키 값의 원소 허용, 루트와 같은 키 값은 오른쪽 서브트리에 삽입

   - 중위 우선 순회 통해 원소 하나씩 검색 후 원래 배열에 저장

   - 시간 복잡도: O(nlogn)

   - TreeSort Algorithm

treeSort(a[], n)
	for(i=0; i<=n; i++)
    	insert(T,a[i]);  // T는 이진 정렬 트리
    inorder(T,a,-1);

   - Inorder Algorithm

inorder(T, a[], i)
	if(T=null) then return;
    inorder(T.left, a, i); // T의 왼쪽 서브트리
    i=i+1;
    a[i] <- T.key
    inorder(T.right, a, i); // T의 오른쪽 서브트리

3. 알고리즘 실행 단계