[알고리즘] 셸 정렬 - 나눠서 삽입정렬을 하다

셸 정렬

주어진 자료에 매개 변수 h 길이를 갖는 부분집합으로 나누고, 삽입정렬 수행

매개변수 h값을 줄이며 반복, 매개 변수 h 값이 1이 되면 정렬 완성

 

부분집합 만드는 방법

1. 부분집합 기준 간격을 h에 저장
2. 한단계씩 h 값을 감소시키고 셸 정렬 호줄
3. h1가 1이 될 때까지 반복

 

예시

44, 88, 62, 38, 19, 49, 27, 73가 있다

매개변수를 원소 개수의 반으로 하는 경우

전체 원소 8개니까 매개 변수 h는 4

 

시작!

4간격씩 떨어져 있는 녀석들을 모아서 부분집합을 만든다

그 말은

44에서 오른쪽으로 4번 떨어진 19를 하나의 부분집합,

88에서 4번 떨어진 49를 부분집합으로

... 나머지도 똑같이

 

부분집합 만들때 중요한 포인트

부분집합 할 때 삽입 정렬을 한다

 

이렇게 만들어진다

19, 49, 27, 38, 44, 88, 62, 73

 

이렇게 한번의 폭풍이 지나가고..

다음은 매개 변수 h를 반으로 나눠서 2로 변경

 

그럼 2 간격씩 떨어진 녀석들을 부분집합으로 만들면서 삽입 정렬을 수행

19, 27, 44, 62 이 무리와

49, 38, 88, 73 이 무리로 부분집합을 해주며 삽입 정렬을 수행

(삽입 정렬 하는 방법은 여기를 클릭)

19, 38, 27, 49, 44, 71, 62, 88 이렇게 바뀐다

 

마지막으로

이제 매개변수 h를 2를 반으로 나눠서 1로 변경(1이 되면 종료)

간격이 1만큼 떨어져 있는 원소를 부분집합으로, 즉 모든 원소에 대해 삽입 정렬 수행

19, 27, 38, 44, 49, 62, 73, 88

 

삽입 정렬은 이미 정리되어 있으면 빠르다

이렇게 잘라서 삽입정렬을 하는 경우 평균적으로 그냥 삽입정렬보다 빠르다

 

셸 정렬의 성능은 매개 변수 h에 달려있다

매개 변수 h를 반으로 줄여가면서 사용하는게 유용할 수 있다.

 

삽입 정렬 이해가 먼저 필요하겠다