[자료구조] 셸 정렬(shell sort)...

[자료구조] 셸 정렬(shell sort)...[자료구조] 셸 정렬(shell sort)...

셸 정렬은 일정한 간격으로 떨어져 있는 자료들끼리 부분집합을 구성하고 각 부분집합에 있는 원소들에 대해서 삽입 정렬을 수행하는 작업을 반복하면서 전체 원소들을 정렬하는 방법이다. 전체 원소에 대해서 삽입 정렬을 수행하는 것보다 부분 집합으로 나누어 정렬하게 되면 비교 연산과 교환 연산의 횟수를 줄일 수 있다.

셸 정렬에서 부분집합을 만드는 기준이 되는 간격을 매개변수 h에 저장하고 한 단계가 수행될 때마다 h의 값을 감소시키고 셸 정렬을 순환 호출하는데, 결국 h가 1이 될 때 까지 반복한다. 셸 정렬의 성능은 매개변수 h의 값에 따라 달라진다. 일반적으로 사용하는 h의 값은 원소 개수의 ½을 사용하고 한 단계 수행될 때마다 h의 값을 반으로 감소시키면서 반복 수행된다.

셸 정렬은 n개의 자료에 대한 메모리 공간과 매개변수를 저장할 공간을 사용한다. 비교횟수는 처음 원소의 상태에 상관없이 매개변수 h에 의해 영향을 받기 때문에 알고리즘의 성능을 분석하기가 쉽지 않은데, 일반적으로 셸 정렬의 시간복잡도를 O(n¹¼)로 측정한다.

아래의 동영상을 참고하면 이해가 훨씬 쉬울 것이다.



[자료구조] 셸정렬(shell sort)...[자료구조] 셸정렬(shell sort)...