반응형
void InsertionSort(vector<int>& v, int f,int n, int h) {
int i, j,temp;
for (i = f + h;i < n;i+=h) { //h 만큼의 격차를 벌림 h가 작으면 작을수록 셸이 작아짐
temp = v[i];
for (j = i-h;f <= j && temp < v[j]; j -= h) {
v[j + h] = v[j];// 셸의 개수만큼 반복하여 삽입정렬
}
v[j + h] = temp; //for 의 조건을 만족하지 못한다면 재할당
}
}
void ShellSort(vector<int>& v, int n) {
int i, h;
for (h = n / 2;h > 0;h /= 2) {
if (h % 2 == 0) h++;//2의 배수일 경우 1증가 맨마지막에 h 가 1일경우 존재위해
for (i = 0;i < h;i++) InsertionSort(v, i, n , h);// i 값을 증가시키면서 셸 변경
}
}
시간 복잡도
최선시간 복잡도 O(n)
최악시간 복잡도 O(n1.5)
제자리성 : 제자리 정렬
안정성 : 불안정
인접하지 않은 원소끼리의 비교
알고리즘
1. h 의 격차를 두고 셀 설정
2. 셀 내부에서 삽입정렬
3. i 값을 늘리면서 셀 변경
4. for 문을 통해 다시 삽입정렬
5. for 문을 통해 h 변경
반응형
'Lecture > Algorithm' 카테고리의 다른 글
[정렬] 힙 정렬 (Heap Sort ) (0) | 2021.05.09 |
---|---|
[정렬] 병합정렬 ( Merge Sort ) (0) | 2021.05.09 |
[정렬] 삽입정렬 ( Insertion Sort ) (0) | 2021.05.09 |
[정렬] 버블정렬 ( Bubble Sort ) (0) | 2021.05.09 |
[정렬] 선택정렬( Selection sort ) (0) | 2021.05.08 |