[알고리즘] 기초 정렬 알고리즘 - 쉘 정렬(ShellSort)

 

쉘 정렬

삽입정렬을 이용하여 리스트 전체에 대해 작업하는 대신

처음에 이 리스트를 몇(k)개의 서브리스트로 나누어 각각 삽입 정렬을 하고,

다시 앞의 k보다는 작은 수의 서브리스트가 되도록 나누어 각 서브리스트에 삽입 정렬을 적용시킨다.

 

안정적 알고리즘(삽입정렬을 사용하고 있기때문에 안정적인 제자리 정렬이다.)

제자리 정렬(삽입정렬을 사용하고 있기때문에 안정적인 제자리 정렬이다.)

 

특징

서브리스트로 나눌 때 각 서브리스트는 인덱스의 일정한 간격(interval)을 가진 원소들만 포함

 

가장 많이 사용되는 인덱스 간격 순차는 ..... , 1093, 364, 121, 40, 13, 4, 1 이다.

- 인덱스 간격은 홀수와 짝수가 번갈아 나오는 순차가 되는 것이 좋다.

  (만일 홀수만 나온다던가, 짝수만 나온다면 같은 원소끼리 비교하는 비율이 높아져서 성능 저하 우려가 있다)

- 증가시킬때는 간격 h를 h = 3 * h + 1 로, 감소시킬때는 h = h / 3 으로하면 쉽게 계산할수있다.

 

목적

서브리스트로 나누는 목적은 원소의 비교 연산과 먼 거리로의 원소 이동을 줄이려는 것

 

 

배열 a[]가 0 ~ 15까지 라고 했을 때,

a[0]에는 감시 키(더미키) -1을 넣고,

a[1] ~ a[15]에는 random하게 숫자들이 배치된다.

이 정렬에서 인덱스 간격이 13, 4, 1이라고 하면

간격 변수 h = 13으로 설정하여 정렬을 시작한다.

 

처음에 a[1], a[14]를 삽입정렬 방법으로 정렬하고,

두번째로 a[2], a[15]를 삽입정렬 방법으로 정렬한다.

한번의 실행이 끝나고 간격 변수 h = h / 3이 실행되어 h 값이 4가 되면,

a[1], a[5], a[9], a[13]을 삽입정렬 방법으로 정렬하고,

a[2], a[6], a[10], a[14]를 삽입정렬 방법으로 정렬하고,

a[3], a[7], a[11], a[15]를 삽입정렬 방법으로 정렬한다.

두번째 실행이 끝나고 간격 변수 h = h / 3이 실행되어 h 값은 1이 된다.

이제 인덱스 간격이 1이 되여, 전체 배열에 대한 삽입정렬을 실행하게 된다.

이번 단계에서 배열 전체에 대한 삽입 정렬 기법이 수행되고, 정렬은 종료된다.

 

시간 복잡도는 삽입 정렬 알고리즘의 성능보다 개선된 O(N^1.25)로 측정된다.

 

쉘 정렬(shellsort) 알고리즘

ShellSort(a[], n)     for ( h <- 1 ; h < n ; h <- 3*h+1 ) do {}; // 첫 번째 h 값 계산     for ( ; h > 0 ; h <- h/3 ) do { // h 값을 감소시키며 진행         for ( i <- h + 1 ; i <= n ; i <- i+1 ) do {             v <- a[i];             j <- i;             while ( j > h and a[j-h] > v ) do {                 a[j] <- a[j-h];                 j <- j-h;             } // while end             A[j] <- v;         } // for end     } // for end  end ShellSort()