쉘정렬
-
쉘 정렬개발 지식/알고리즘 2020. 7. 9. 04:58
JAVA로 작성되었습니다. 쉘 정렬 삽입 정렬을 개산한 알고리즘, 바탕은 삽입정렬을 기본으로 진행한다. 가까운 위치에 삽입되는 (어느정도 정렬이 되어있는) 삽입정렬이 빠른 것을 이용하여 삽입정렬을 하기 전 배열을 어느정도 정렬한 상태에서 삽입정렬을 진행하는정렬 방식이다. 이때 gap이라는 것이 존재하는데 gap만큼 배열을 띄엄띄엄 정렬하는데 사용한다. 갭을 설정한다. 갭의 값은 이전 갭의 절반으로 설정한다. (초기 값은 배열의 크기 / 2 로 설정한다) (홀수를 권장하므로 2로 나누었을 때 짝수가 나온다면 +1을 하여 홀수로 정한다.) 원본 배열에서 다음 요소와 인덱스의 차이가 gap만큼 있는 부분 배열들을 생성한다. (리스트의 길이가 11(0~10)이고 갭이 5라면 (0, 5, 10), (1, 6), ..