2.2 - 정렬 삽입 - 힐 정렬

참조 링크

정렬 삽입: 힐 정렬 (Shell 's Sort)

백화 고전 알고리즘 시리즈 의 삼 힐 정렬 실현

힐 의 순 서 는 1959 년 에 D. L. Shell 에서 제 기 된 것 으로 직접적인 순 서 는 비교적 개선 되 었 다.힐 정렬 은 축소 증분 정렬 이 라 고도 한다.
기본 사상:

먼저 전체 대기 요소 서열 을 여러 개의 키 서열 로 나 누 었 다 (특정한 '증분' 요소 로 구 성 된). 각각 정렬 을 직접 삽입 했다.

그리고 차례대로 증 량 을 줄 이 고 순 서 를 매 긴 다.

전체 시퀀스 의 요소 가 기본적으로 질서 가 있 을 때 (증 량 이 충분 한 작은 dk =) 전체 요 소 를 한 번 에 정렬 합 니 다.

정렬 을 직접 삽입 하 는 것 은 요소 가 기본적으로 질서 가 있 는 상황 에서 (가장 좋 은 상황 에 가깝다) 효율 이 높 기 때문에 힐 정렬 은 시간 효율 에 있어 서 앞의 두 가지 방법 보다 비교적 높 아 졌 다.

n = 10 의 한 배열 49, 38, 65, 97, 26, 13, 27, 49, 55, 4 를 예 로 들 면
첫 번 째 gap = 10/2 = 5

   49   38   65   97   26   13   27   49   55   4

   1A                       1B

       2A                       2B

             3A                      3B

                  4A                      4B

                       5A                      5B

1A, 1B, 2A, 2B 등 은 그룹 별로 표시 되 고 숫자 는 같은 그룹 에 표시 되 며 대문자 로 는 이 그룹의 몇 번 째 요소 임 을 나타 내 며 매번 같은 그룹의 데 이 터 를 직접 삽입 하여 정렬 합 니 다.즉 5 조 (49, 13) (38, 27) (65, 49) (97, 55) (26, 4) 로 나 뉘 어 각 조 가 순 위 를 매 긴 후 (13, 49) (27, 38) (49, 65) (55, 97) (4, 26) 로 바 뀌 었 다.
두번째 gap = 5/2 = 2
정렬 후

   13   27   49   55   4    49   38   65   97   26

   1A        1B        1C        1D       1E

        2A        2B        2C       2D        2E

세 번 째 gap = 2/2 = 1

   4   26   13   27   38    49   49   55   97   65

   1A   1B   1C   1D   1E   1F   1G   1H    1I   1J

네 번 째 gap = 1/2 = 0 정렬 이 완료 되면 배열 을 얻 을 수 있 습 니 다:

   4   13   26   27   38    49   49   55   65   97

알고리즘 구현:
우 리 는 증분 서열 을 간단하게 처리 합 니 다. 증분 서열 d = {n/2, n/4, n/8..........................................................

먼저 정렬 할 그룹의 기록 을 특정한 증 량 d (n/2, n 은 정렬 할 수의 개수) 에 따라 몇 개의 그룹 서브 시퀀스 로 나 누고 각 그룹 에 기 록 된 아래 표 의 차이 d.

각 그룹의 모든 요 소 를 정렬 한 다음 에 작은 증분 (d/2) 으로 그룹 을 나 누 어 각 그룹 에 직접 정렬 을 삽입 합 니 다.

증 가 량 을 1 까지 계속 줄 였 다.

마지막 으로 정렬 을 직접 삽입 하여 정렬 을 완성 합 니 다.

//   int dk      ，         ，dk=1
    mutating func shellInsertSort(dk: Int) {
        for i in 0 ..< dk {
            /*
                 ，i, i+k, i+k+k, ...     
                         
             */
            var insert = i + dk
            while insert < count {
                var current = insert
                var prev = current - dk
                while prev >= 0 {
                    if self[current] < self[prev] {
                        swap(&self[current], &self[prev])
                    } else {
                        break;
                    }
                    current = prev
                    prev -= dk
                }
                insert += dk
            }
        }
    }
    
    
    mutating func shellSort() {
        /*
                   ：    d = {n/2 ,n/4, n/8 .....1} n         ：
         
         1.                d（n/2,n        ）        ，          d.
         2.                 ，           （d/2）      ，             。
         3.            1，
         4.               。
         */
        if count < 2 {
            return
        }
        var dk = count / 2
        while dk >= 1 {
            shellInsertSort(dk)
            dk /= 2
        }
    }

위의 셸 sort 코드 는 힐 의 순 서 를 직관 적 으로 이해 하 는 데 도움 이 되 지만 코드 의 양 이 너무 많아 간결 하고 뚜렷 하지 않다.따라서 개선 과 최 적 화 를 진행 합 니 다. 두 번 째 순 서 를 예 로 들 면 매번 1A 에서 1E, 2A 에서 2E 로 바 꿀 수 있 습 니 다. 1B 부터 1A 와 비교 한 다음 에 2B 와 2A 를 비교 한 다음 에 1C 를 취하 여 앞의 자기 그룹 내의 데이터 와 비교 할 수 있 습 니 다.이러한 매번 배열 의 두 번 째 gap 요소 부터 모든 요소 와 자신의 그룹 내의 데 이 터 를 직접 삽입 하여 정렬 하 는 것 도 정확 하 다.

mutating func shellInsertSortBetter(dk: Int) {
    //    dk     
    for i in dk ..< count {
        var insert = i
        var prev = i - dk
        while prev >= 0 {
            if self[insert] < self[prev] {
                swap(&self[insert], &self[prev])
            } else {
                break
            }
            insert = prev
            prev -= dk
        }
    }
}