JS implementation of Hill sort of graphic insertion sort [with source code]

Introduce

        In the previous article, we introduced the characteristics of insert sort and the performance optimization of binary insert , Next, let's look at another variant of insert sort ：【 Shell Sort 】. According to the previous experience, we know that the time complexity of insertion sorting is O(n)-O(n^2), Although it seems that the performance is very high , However, when the data we insert for sorting is in complete reverse order or there are too many reverse data, the number of times we need to compare for inserting and sorting will become infinitely close O(n^2), In the last article, we performed binary insertion to reduce the number of comparisons by analyzing that the insertion sort is an ordered array when the insertion is completed , This time we will learn another variant of his thinking .

Ideas

        Hill sort also takes into account that the number of comparisons increases when there are too many data in reverse order , So Hill sort chooses to sort the overall data into an orderly state by jumping in a large area , Finally, it gradually becomes an insert sort , When the insert sort is finally performed, the array ordering is gradually formed, so the number of comparisons will be reduced , But Hill sort also belongs to unstable sort , Therefore, its time complexity is not as high as that of the fastest case of insertion sorting ：O(n^(1.3—2)) 

The illustration

        Hill sort is equivalent to performing multiple insert sorts to sort the array , So we need to define a step size first , Usually, we will define the step length as half of the array length for rounding , Then the step size will be /2 The final step is 1 The last insertion sort is performed when . We still take the previous array data as an example .

let arr = [13,2,7,21,8,65,2,0,1,9,14,7,63]

The sorting process of this array is shown in the following figure .

For the first time Math.floor(arr.length/2) Step size to perform grouping insertion sorting

After this insertion, the array will look like the following

 

Next, we continue to reduce the step size step=Math.floor(step/2), Group insertion sort again . Pictured .

 

Looking at the figure above, we can see that we have divided the array into 3 The group performs an insert sort , The three groups are orderly . Next we will  step=Math.floor(step/2), here step The value of has been reduced to 1, That is, it becomes a normal insertion sort

 

Here we have successfully sorted the data , And we find that the comparison times of the last insertion sort are very close to the length of the array . In this way, you can further improve the performance of insert sorting in scenarios that are not suitable for insert sorting .

Code implementation

let arr = [13,2,7,21,8,65,2,0,1,9,14,7,63]
/**
 *  Shell Sort 
 * @param {Object} arr  Array 
 */
function sort(arr){
	// Define the default step size as half of the array 
	let step = Math.floor(arr.length/2)
	// Let the step size 2 The order decreases to 0
	while(step>0){
		// Define the starting insertion sort point 
		let i = 0+step
		// Perform insertion sorting by step distance 
		while(i<arr.length){
			// Record the data to be compared 
			let temp = arr[i]
			// Define the data to start the comparison 
			let j = i-step
			// Move the pointer and j Start comparison. As long as the current data is smaller than the previous data, move the previous data to the right 
			while(arr[j]>temp&&j>=0){
				arr[j+step] = arr[j]
				j-=step
			}
			// Finally, insert the data into the position after the move 
			arr[j+step] = temp
			// Move to the right to continue group insertion 
			i++
		}
			console.log(arr)
		//2 Step decrement 
		step = Math.floor(step/2)
	}
}

  summary

        Among many sorting algorithms, Hill sort is a very classic sort , He used the principle of insertion sort to make further variants and realized a new sort idea , So we should not rigidly adhere to a mode and idea in programming to record fixed answers ,“ Programming has only the optimal solution for a particular situation , There is no standard answer .” Understanding this sentence is of great help to improve our programming thinking . This sharing is over .