Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Hill sorting

The essence of Hill sort is insertion sort. If it is a large array of random numbers, insertion sort will be slow because it only swaps adjacent elements. And the idea of hill sort is that you sort h elements randomly, and then you sort globally. The time complexity can be improved from O(n ^ 2) to O()

H value logic

, for example, for a large-scale ordinal group, to 22 interval value sorting, namely every 22 elements, an element, then put these elements to sort, and then take every 10 interval elements, again, so on and then 4 interval, the interval 1 global sorting, so h value is 1, 4, 10, 22. Wikipedia provides a table of formulas for calculating h

The more commonly used formula is the one in the red box, where k is the natural number 1,2,3,4… N is the length of the array

Example analysis of Hill sort

Let’s say I have an array of length 16According to the formula

  • k1,2,3,4,5… The natural numbers satisfyh < N/3Is [1, 4].
  • At this time, the first interval 4 sort: at this time the first fetchindex=4Elements with 51index=0Element 34 comparison,51 > 34, so do not do any operation; And then takeindex=5withidnex=1The comparison,34 > 22, also do not do operations, and so on. Let’s say that when we go to the last elementindex=15, will be in turnThe index,7,3 = 11The corresponding element is sorted

code

    // h is calculated
    const geth = function(N) { // N is the array length
        let hList = [] // h is an array of values
        let k = 1
        let h = 1
        while(h <= N/3) {
            h = (Math.pow(3, k) - 1) / 2
            if ( h > N/3) break
            hList.push(h) / / 1 and 4
            k++
        }
        return hList
    }
    // Hill sort
    const shellsort = function(arr) {
        let hList = geth(arr.length) // Get the value of h
        for(let k = hList.length - 1; k >= 0; k--) { // h is traversed in reverse order
            let h = hList[k]
            // Put the array in order with h intervals
            for(let i = h; i < arr.length; i++) {
                for(let j = i; j >= h; j = j - h) {
                    if (arr[j] < arr[j - h]) {
                        let temp = arr[j]
                        arr[j] = arr[j - h]
                        arr[j - h] = temp
                    } else {
                        break
                    }
                }
            }
        }
    }
Copy the code

Related to recommend

Thoroughly understand insertion sort, selection sort, bubble sort and optimization