셸 정렬(정의, 구현방법, 장점 및 시간복잡도)

셸 정렬 정의

삽입정렬을 활용한 정렬이다

구간을 만들어서 정렬하고 이러한 구간을 합쳐 완성된 정렬을 만드는 방법

 

구현방법

1. 맨처음은 크기/2 구간의 리스트를 만들어 그 리스트를 정렬할 수 있도록한다.

2. 정렬 된 것을 다시 나누기 2 구간으로 만들어 리스트를 정렬한다

3. 크기가 1이 되면 정렬이 종료된 것이다

 

장점

삽입 정렬에 비해 교환 횟수가 적어 빠르다

 

시간 복잡도

n^2이나

평균적으로 n^1.5