Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- error
- 타입스크립트
- 토이프로젝트
- 협업
- web
- C++
- 분할메모리할당
- Operating System
- 백준
- Java
- 스프링
- 기초100제
- 파이썬
- 프로그래머스
- Spring
- react
- 코드업
- 알고리즘
- Redux
- 리덕스장바구니
- 일상
- OS
- CPU 스케줄링
- 자료구조
- memory
- js to ts
- 공부
- 정렬
- codeup
- react-redux
Archives
- Today
- Total
감자튀김 공장🍟
[C++] 쉘 정렬 (Shell Sort) 본문
반응형
쉘 정렬
- 쉘 정렬은 삽입 정렬의 O(n^2)보다 빠르다.
- 셀 정렬은 정렬해야할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다.
- 모든 부분 리스트가 정렬되면 쉘 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 되풀이 한다.
- 위 과정을 부분 리스트의 개수가 1일 때까지 반복한다.
- 부분 리스트 구성 방법
- 주어진 리스트의 각 k번째 요소를 추출하여 만든다. 이 k를 간격(gap)이라고 한다.
- 각 스텝마다 간격 k를 줄여가므로 수행과정이 반복될 때마다 하나의 부분 리스트에 속하는 레코드들의 개수는 증가된다.
쉘 정렬의 과정
- 1단계
- 간격(gap)을 5로 잡고 {10, 3, 16}, {8, 22}, {6, 1}, {20, 0}, {4, 15} 의 부분 리스트를 만든다.
- 각 부분 리스트마다 삽입 정렬을 시도하여 {3, 10, 16}, {8, 22}, {1, 6}, {0, 20}, {4, 15} 와 같이 정렬한다.
- 각 부분 리스트를 합치게 되면 {3, 8, 1, 0, 4 ,10, 22, 6, 20, 15, 16} 으로 정렬이 된다.
- 2단계
- 1단계와 똑같이 간격을 5로 잡으면 정렬 진행이 안되기 때문에 3으로 잡는다.
- 3으로 잡은 후 {3, 0, 22, 15}, {8, 4, 6, 16}, {1, 10, 20} 의 부분 리스트를 만든다.
- 각 부분 리스트마다 삽입 정렬을 시도하여 {0, 3, 15, 22}, {8, 4, 6, 16}, {1, 10, 20}으로 정렬한다.
- 각 부분 리스트를 합치게 되면 {0, 4, 1, 3, 6, 10, 15, 8, 20, 22, 16}으로 정렬이 된다.
- 3단계
- 간격이 3까지 좁혀졌기 때문에 간격을 1로 설정한다.
- 단계 2의 결과에서 삽입 정렬을 시도한다.
- 부분 리스트의 개수가 1개이기 때문에 정렬을 종료한다.
코드 구현
#include <iostream>
using namespace std;
void shellSort(int arr[], int len) {
int i, j, temp;
int gap = len / 2;
while (gap > 0) {
for (i = gap; i < len; i++) {
temp = arr[i];
j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
gap /= 2;
}
}
int main() {
int arr[] = { 10,8,6,20,4,3,22,1,0,15,16 };
int len = sizeof(arr) / sizeof(int);
cout << "정렬 전: ";
for (int x : arr)
cout << x << " ";
cout << endl;
shellSort(arr, len);
cout << "정렬 후: ";
for (int x : arr)
cout << x << " ";
cout << endl;
}
시간 복잡도
- 최악의 경우에는 O(n^2)이지만 평균적인 경우에는 O(n^1.5)로 나타낸다.
반응형
'Algorithm > 정렬' 카테고리의 다른 글
[python] 선택 정렬(Selection sort) (0) | 2022.03.20 |
---|---|
[python] 버블 정렬(Bubble sort) (0) | 2022.03.19 |
[C++] 버블 정렬(Bubble Sort) (0) | 2021.08.27 |
[C++] 삽입 정렬(Insertion Sort) (0) | 2021.08.24 |
[C++] 선택 정렬(Selection Sort) (0) | 2021.08.23 |
Comments