[자료구조] Chapter 09. 정렬 (Sorting)

🚨 'C언어로 쉽게 풀어쓴 자료구조' 라는 책을 활용했던 과거 수업 필기를 정리한 것입니다.
💡 Chapter 순서는 책과 같지만 교수님의 과거 수업 내용에 따라 일부 책과 다른 내용이 있습니다.

1. Selection Sort (선택 정렬)

시간 = 비교횟수 = (N-1) + (N-2) + ... + 2 + 1 = O(N^2)

2. Insertion Sort (삽입 정렬)

Sorting 된 데이터는 빠르게 마무리

for(k = 2 to N) { // [1 ~ k-1] sorted에 k를 삽입
	m = A[k];
    	for(i = k-1 down to 1) {
        	if(A[i] < m) break;
            	else A[i+1] = A[i] // shift
        }
        A[i+1] = m;
}

3. Bubble Sort (버블 정렬)

인접한 두 원소를 비교하여 교환 반복

for(k = 1 to N-1) {
	count = 0;
    	for(j = N down to k+1) {
        	if(A[j-1] > A[j]) {
            		swap(A[j-1],A[j]);
                    	count++;
                }
        }
        if(count == 0) break; // 완료
}

4. Shell Sort (셸 정렬)

간격(gap)별 sub-list에 삽입 정렬 -> 약간 sorting 된 상태는 빠르게 마무리

for(gap = N/2; gap >0; gap = gap/2){
	if(gap == 짝수) gap++;
    	for(i=1 to gap) insertion - sort(); // gap만큼의 sub-list 존재 -> 삽입정렬
}

5. Merge Sort (합병 정렬)

6. Quick Sort (퀵 정렬)

Sorting 된 데이터는 더 오래 걸림(최악)
현실적으로 가장 빠른 알고리즘 (실험 Data)

QS(1,N);
QS(l,h) {
    if(l >= h) return
    m = partition(l,h);
    QS(l,m-1);
    QS(m+1,h);
}

• 시간분석
  

7. Heap Sort (힙 솔트)

heap 구성 후 반복 삭제 -> O(Nlg N)

8. BST Sort

1. A[1, ... , N] 의 N개 data로 이진 탐색 트리 (BST)를 구성 : O(Nlg N)
2. 이 BST를 In - Order로 방문하여 data를 A에 재수거 O(N)
   -> time = O(Nlg N) + O(N) = O(Nlg N)
   -> space = O(N) : BST

Liner Sort

O(N)에 Sorting

1. radix (기수) Sort ( = Bucket Sort)
   시간은 이익, 공간은 손해
   A[1, ... , N]에 N개의 k-digit 10진 정수
   

2. Hashing에 대한 Sorting
   N개의 정수를 T[0, ..., M-1]에 저장 후 재수거 (MM=k*N (저장 사이즈) >>>>> N데이터 개수)

   1 ) for all integer k, T[k] = k
   2 ) T[i], i = 0~M-1 순서로 data 재수집 -> O(M)
   -> O(M) = O(k*N) = O(N)