Shell Sort

참고문헌

<C언어로 쉽게 풀어쓴 자료구조 내용 >

 

삽입정렬의 문제점

삽입정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동한다는 것이다. 
만약 삽입되어야할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다.
쉘 정렬에서는 요소들이 멀리 떨어진 위치로도 이동할 수 있다.

 

구현 방식

삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안한 방법이다.

Shell정렬은 삽입 정렬보다 빠르다.

삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동한다는 것이다.

만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면

많은 이동을 해야만 제자리로 갈 수 있다.

쉘정렬에서는 요소들이 멀리 떨어진 위치로도 이동할 수 있다.

삽입 정렬과는 다르게 쉘 정렬은 전체의 리스트를 한 번에 정렬하지 않는다.

대신에 먼저 정렬해야할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다.

모든 부분 리스트가 정렬되면, 쉘 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에

알고리즘을 되풀이 한다.

위의 과정은 부분 리스트의 개수가 1이 될 때까지 되풀이 한다.

부분 리스트를 구성할 때는 주어진 리스트의 각 k번째 요소를 추출하여 만든다.

이 k를 간격 (gap)이라고 한다.

쉘 정렬에서는 각 스텝마다 간격k를 줄여가므로 수행과정이 반복될 때마다 하나의 부분 리스트에 속하는 레코드들의 개수는 증가된다.

마지막 스텝에서는 간격의 값이 1이 된다.

예를 들어 입력 리스트가 { 10,8,6,20,4,3,22,1,0,15,16 } 일 때, 쉘 정렬이 수행되는 과정은

아래의 [그림 1] 과 같다.

[그림 1]의 (a)와 같이 입력 리스트의 각 5번째 요소를 추출하여 부분 리스트들을 만든다.

첫 번째 부분 리스트는 10, 3, 16으로 구성되며 두 번째 부분 리스트는 8, 22 로 구성되고,

이런식으로 부분 리스트들이 구성된다.다음으로 각 각의 부분 리스트에 대하여 삽입 정렬이 수행된다.

부분 리스트들이 정렬된 후에는 전체 리스트도 약간은 정렬이 된 것을 확인할 수 있다.

여기서 실제로 부분 리스트들이 만들어지는 것은 아니고 일정한 간격으로 삽입 정렬을 수행하는 것 뿐이다. 따라서 추가적인 공간은 필요없다.

 

[그림 1 : 쉘 정렬의 첫 번째 패스]

쉘 정렬의 첫 번째 패스가 끝나면 비슷한 방식으로 다시 부분 리스트를 구성하는데,

이번에는 간격을 줄여서 입력 배열의 각 3번째 요소를 추출하여 부분 리스트를 만든다.

마지막 패스는 간격을 1로 줄여서 모든 요소가 1개의 부분 리스트에 포함된다.

쉘 정렬의 전체 과정은 아래 [표 1]을 참고하자.

 

[표 1 : 쉘 정렬의 전체 과정]

아래의 프로그램을 먼저 살짝 이야기하면

간격(Gap)은 처음에는 데이터의 개수의 반으로 하고, 각 패스마다 간격을 절반으로 줄이는 방식을 사용.

ShellSort함수 내에 정의한 변수 Gap이 간격을 나타낸다.

ShellSort함수는 Gap이 1이 될 때 까지 Gap을 반으로 줄이면서 반복한다.

이 때, 부분 리스트의 개수 또한 Gap이 된다.

 

구현 version1

아래의 ShellSort함수를 보면 앞 장의 삽입 정렬 함수를 while문으로 감싼 느낌을 받을 것이다.

프로그램 실행결과

소스 파일

main.c

0.00MB

 

구현 version2

각 부분 리스트에 대하여 일정한 간격으로 떨어져 있는 요소들을 삽입하는 함수인

InsertionSort 를 호출한다.

InsertionSort 함수는 앞 내용의 삽입정렬함수와 비교하여 보면 쉽게 알 수 있다.

만약 간격이 짝수라면 1을 더하는 것이 좋은 것으로 분석되어서 1을 더함.

프로그램 실행결과

소스 파일

main.c

0.00MB