0x08.정렬 알고리즘(2):쉘 정렬

3. 쉘 정렬(Shell Sort)

Shell이라는 사람이 삽입 정렬의 장점을 활용하여 개발한 알고리즘인데 만약 배열이 어느정도 정렬이 되어있다면 효율이 좋다.

이 방식은 배열의 데이터들을 몇 개의 그룹으로 나눈 다음, 각 그룹의 같은 위치의 데이터들을 비교하여 삽입정렬하고 그룹의 크기를 줄여나가는 방식을 사용한다.

위 그림은 크기가 8인 배열의 전체적인 쉘 정렬 순서를 나타낸 것이다. 색이 같은 부분들은 같은 그룹을 뜻하고, 회색으로 표시된 칸들은 비교대상이 된다. 즉 그림의 맨 첫 배열에서는 1,5,8,3이라는 값을 가진 배열칸들이 같은 그룹을 형성하고 6,2,0,7을 뜻하는 나머지 배열칸들이 다른 그룹을 형성해 그룹의 개수가 총 2개가 된다. 두 그룹의 같은 위치에 있는 1과 6데이터를 가진 배열의 칸의 크기를 비교하여 정렬을 실시하고, 차례대로 다음 칸들도 같은 방식으로 실행한다.

그 다음으로는 배열의 데이터들을 그룹의 크기가 2로 다시 재 분리하여 위와 같이 같은 위치에 속한 배열의 값들을 비교하고 정렬한다. 마지막으로 전체적인 칸에 대한 삽입정렬을 실행하여 마지막과 같은 결과값을 얻게 되는 방식이다.

void shellSort(int *array, const int length, const int div)   //array==배열, length==배열의 크기, div==간격의 크기를 줄일 배수

{

int target;

int i,j;

for(int interval=length/2; interval>0; interval /=div) // 간격의 크기를 조절 ; 첫 간격의 크기는 배열의 크기의 1/2

{

for(int group=0; group<interval; group++) // 그룹을 나타냄

{

int base=group;

for(i=base+interval; i<length; I+=interval)

{

target=array[i];

for(j=i-interval; j>=base&&target<array[j]; j-=interval)  //삽입 정렬

{

array[j+interval]=array[j];

}

array[j+interval]=target;

}

}

}

}

}

위의 소스코드를 예로 설명하자면 array의 크기인 length는 8이 되고 1/2크기로 줄여왔기에 div값은 2가 된다. interval의 초기값은 8/2인 4가 되고 점점 div의 크기만큼 줄어드는데 이는 그룹의 크기가 4,2,1 순으로 줄어드는 것을 의미한다.

i의 크기는 그림의 첫 배열의 모습에서는 데이터값 6이 들어간 array[4]를 뜻하고 이는 target값이 된다. j의 값에는 다른 그룹의 array[4]가 속한 위치의 값인 array[0]이 들어가게 되는데, 그 둘의 값을 비교하여 삽입 정렬이 수행된다. 이와 같이 반복되고 나면, interval의 크기가 2가 되고 다시 새로운 그룹 크기에 대한 삽입 정렬이 수행되며, 마지막에는 그룹의 크기가 1이 되기 때문에 전체 배열에 대한 삽입정렬이 수행되면서 쉘 정렬이 끝나게 된다.