셸 정렬(Shell Sort)프로그래밍 공부/자료구조&알고리즘 공부2022. 7. 19. 15:31
Table of Contents
셸 정렬(Shell Sort)은?
단순 삽입 정렬의 장점은 살리고 단점은 보완한 정렬 알고리즘
도널드 셀(D.L.Shell)이 고안했다.
먼저 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입정렬을 수행하고,
그 그룹을 합치면서 정렬을 반복하여 요소의 이동횟수를 줄이는 방법이다.
퀵정렬이 나오기 전까지는 가장 많이 쓰였다고 한다.
여기서 말하는 단순 삽입정렬의 장점과 단점은
장점
- 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라진다.
단점
- 삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아진다.
셸정렬은 이 단점을 해결하고 장점을 이용하기 위해 만들어졌다.
코드로 만들어보기
//배열 a와 요소의 수 n
void shell(int a[], int n)
{
int h, i, j;
//첫번째 for문
for (h = n / 2; h > 0; h /= 2)
//두번째 for문
for (i = h; i < n; i++)
{
int tmp = a[i];
//세번째 for문
for (j = i - h; j >= 0 && a[j] > tmp; j -= h)
a[j + h] = a[j];
a[j + h] = tmp;
}
}
코드로 짜면 이런 코드가 나온다.
단순 삽입 정렬의 단점을 해결하기 위해 첫번째 for문은 총 요소의 수에서 나누기 2를 해가며 돌아간다.
예를들어 총 요소의 수가 8개라고 한다면 처음 시작은 4 , 그 다음은 2, 마지막으로 1을 대입한다.
밑에 코드를 보면 i는 첫번째 for문의 h와 같고 총 요소의 수까지 돌아가는데,
요약하자면 h가 4일때는 배열에서 4칸만큼 떨어진 곳과 짝을 지어서 정렬하고, {0,4}, {1,5},{2,6},{3,7}
첫번째 for문이 끝나고 나누기 2가되어 h가 2가됐을때는 2칸만큼 떨어진 곳과 짝을 지어 정렬한다.
그리고 h가 마지막 1이 될때는 하나씩 검사하며 최종 정렬을 마친다.
이론상으로는 이해가 되는데 코드가 이해가 안돼서 여러번 본 것 같다.
'프로그래밍 공부 > 자료구조&알고리즘 공부' 카테고리의 다른 글
[C++] 스택 직접 구현해보기 (0) | 2023.04.12 |
---|---|
버블정렬 알고리즘 개선하기 (0) | 2022.07.22 |
단순 선택 정렬 & 단순 삽입 정렬 (0) | 2022.07.18 |
버블 정렬 알고리즘 (0) | 2022.07.17 |
재귀 알고리즘 / 순차곱셈 구하기, 유클리드 호제법 구현 (0) | 2022.07.16 |
@데브준우 :: 개발초보 JW의 성장일기
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!