쉘 정렬

쉘 정렬

삽입 정렬을 이용하여 배열 뒷부분의 작은 숫자를 앞부분으로 빠르게 이동시키고, 동시에 앞부분의 큰 숫자는 뒷부분으로 빠르게 이동시키는 정렬 알고리즘

 

---

간격(gap)을 이용

30 60 90 10 40 80 40 20 10 60 50 30 40 90 80

 

◼ 간격(gap)이 5인 숫자 그룹

그룹1 : [30, 80, 50]

그룹2 : [60, 40, 30]

그룹3 : [90, 20, 40]

그룹4 : [10, 10, 90]

그룹5 : [40, 60, 80]

참고) 알기 쉬운 알고리즘

 

 

각 그룹 별로 삽입 정렬 수행

참고) 알기 쉬운 알고리즘

▶ 30 30 20 10 40 50 40 40 10 60 80 60 90 90 80

처음보다 비교적 큰 숫자가 뒷부분으로, 작은 숫자가 앞부분으로 이동

 

 

그 다음에는 간격을 전에 설정한 것보다 작게 하여 다시 그룹별 삽입 정렬 수행

◼ 간격(gap)이 3인 숫자 그룹

그룹1 : [30, 10, 40, 60, 90]

그룹2 : [30, 40, 40, 80, 90]

그룹3 : [20, 50, 10, 60, 80]

 

각 그룹 별로 삽입 정렬 수행

그룹1 : [10, 30, 40, 60, 90]

그룹2 : [30, 40, 40, 80, 90]

그룹3 : [10, 20, 50, 60, 80]

▶ 10, 30, 10, 30, 40, 20, 40, 40, 50, 60, 80, 60, 90, 90, 80

 

 

마지막에는 반드시 간격을 1로 놓고 삽입 정렬 수행 (그룹별로 서로 비교되지 않는 숫자가 없도록 함)

(삽입정렬 그자체)

◼ 간격(gap)이 1일 때

▶ 10, 10, 20, 30, 30, 40, 40, 40, 50, 60, 60, 80, 80 ,90, 90