[자료구조] 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
- A[1, ... , N] 의 N개 data로 이진 탐색 트리 (BST)를 구성 : O(Nlg N)
- 이 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
-
radix (기수) Sort ( = Bucket Sort)
시간은 이익, 공간은 손해
A[1, ... , N]에 N개의 k-digit 10진 정수
-
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)
Author And Source
이 문제에 관하여([자료구조] Chapter 09. 정렬 (Sorting)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@subinnie/자료구조-Chapter-09.-정렬-Sorting저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)