쉘 정렬

쉘 정렬은 삽입 정렬에 전처리과정을 추가한 것

전처리 과정 : 작은 값을 가진 원소들을 배열의 앞 부분으로 옮기며 큰 값을 가진 원소들이 배열의 뒷부분에 자리잡도록 만드는 과정

삽입정렬이 현재 원소를 앞부분에 삽입하기 위해 이웃하는 원소의 숫자끼리 비교하며 한 자리씩 이동하는 단점 보안

전처리과정은 여러 단계로 진행 되며 , 각 단계에서는 일정 간격으로 떨어진 원소들에 대해 삽입 정렬 수행

 

리스트를 일정 간격(gap)의 부분 리스트로 나눔 (이때 간격에 따라 성능이 달라짐)

간격만큼 부분 집합이 만들어짐 간격은 홀수로 해라 이유: 부분 집합이 더 많이 만들어짐 강의 자료 보고 만들어라

쉘 정렬 : 데이터를 부분 집합으로 만들어서 작은 범위의 삽입 정렬을 하는 것

전처리 과정에서는 자리이동이 많이 일어나지 않는다

이거 이동 하는 것은 그림 그려서 보여주는 것이 좋을듯