Interpolation sort

In-Place Interpolaion Tag Sort
Class	Sorting Algorithm
Data structure	Array
Worst-case performance
Best-case performance
Average performance
Worst-case space complexity
Optimal

Interpolaion Tag Sort
Class	Sorting Algorithm
Data structure	Array
Worst-case performance
Best-case performance
Average performance
Worst-case space complexity
Optimal

Interpolaion Sort
Class	Sorting Algorithm
Data structure	Array
Worst-case performance
Best-case performance
Average performance
Worst-case space complexity
Optimal

Interpolation sort is a sorting algorithm that uses interpolation formulas to disperse data and manipulates the recursive method with label arrays.Interpolation sort is a recursive sorting method for bucket sort variant histogram sort under the distribution sorts class.

Algorithm

Interpolation sort (or histogram sort). ^[1] It is a sorting algorithm that uses the interpolation formula to disperse data divide and conquer. Interpolation sort is also a variant of bucket sort algorithm. ^[2] The interpolation sort method uses an array of record bucket lengths corresponding to the original number column. By operating the maintenance length array, the recursive algorithm can be prevented from changing the space complexity to $O(n^{2})$ due to memory stacking. The segmentation record of the length array can using secondary function dynamically declare and delete the memory space of the array. The space complexity required to control the recursive program is $O(3n)$ . Contains a two-dimensional array of dynamically allocated memories and an array of record lengths. However the execution complexity can still be maintained as an efficient sorting method of $O(n+k)$ . ^[3] Array of dynamically allocated memory can be implemented by linked list, stack, queue, associative array, tree structure, etc. An array object such as JavaScript is applicable. The difference in data structure is related to the speed of data access and thus the time required for sorting.When the values in the ordered array are uniformly distributed approximately the arithmetic progression, the linear time of interpolation sort ordering is $O(n)$ . ^[4]

Interpolation sort algorithm

Set a length array to record the length of the uncompleted sorting bucket,Set a quantitative array as an empty bucket.
The main sorting program determines whether the length array is emptied.Not cleared execution divide.
Take a length from the end of the length array to perform divide.If the maximum value is equal to the minimum value, the sequence sorting is completed to stop the divide.
Search for the sequence and place the items one by one into the bucket corresponding to the interpolation.
Put the items back into the original sequence one by one from a bucket that is not empty.And put the length array into the length of the bucket linked list.
Recursive return to the main sorting processing.

Practice

JavaScript code:

Array.prototype.interpolationSort = function(){
	var divideSize = new Array();
	var end = this.length;
	divideSize[0] = this.length;
	while (divideSize.length > 0) divide(this);

	function divide(A){
		var size = divideSize.pop();
		var start = end - size;
		var min = A[start];
		var max = A[start];
		for ( i = start + 1; i < end; i++)
			if (A[i] < min) min = A[i];
			else if (A[i] > max) max = A[i];
		if (min == max) end = end - size;
		else{
			var p = 0;
			var bucket = new Array(size);
			for ( i = 0; i < size; i++)
				bucket[i] = new Array();
			for ( i = start; i < end; i++){
				p = Math.floor(((A[i] - min ) / (max - min ) ) * (size - 1 ));
				bucket[p].push(A[i]);
			}
			for ( i = 0; i < size; i++){
				if (bucket[i].length > 0) {
					for ( j = 0; j < bucket[i].length; j++){
					    A[start++] = bucket[i][j];
					    divideSize.push(bucket[i].length);}
				}
			}
		}
	}
};

Variant

Interpolation Tag Sort

Interpolation Tag Sort is a variant of Interpolation Sort. Applying the bucket sorting and dividing method, the array data is distributed into a limited number of buckets by mathematical interpolation formula, and the bucket then recursively the original processing program until the sorting is completed.

Bucket[ p ] is interpolation corresponding position. Interpolation formula: p = ( A[ i ] - minimum) / (maximum - minimum) * (size - 1)

Interpolation tag sort is a recursive sorting method for interpolation sorting. To avoid stacking overflow caused by recursion, the memory crashes. Instead, use a Boolean data type tag array to operate the recursive function to release the memory. The extra memory space required is close to $2n+(n)bits$ . Contains a two-dimensional array of dynamically allocated memory and a Boolean data type tag array. Stack, queue, associative array, and tree structure can be implemented as buckets.

As the JavaScript array object is suitable for this sorting method, the difference in data structure is related to the speed of data access and thus the time required for sorting. The linear time Θ(n) is used when the values in the array to be sorted are evenly distributed.The bucket sort algorithm does not limit the sorting to the lower limit of $O(nlogn)$ . Interpolation tag sort average performance complexity is $O(n+k)$ . ^[5]

Interpolation Tag Sort Algorithm

Set an equal number of tag arrays to initialize to false values.
The main sorting program determines whether all the sections of the original sequence have been recursively completed, Execution bucket sort when not completed.
Execute bucket sort; Stop bucket sort if the section has been sorted.
Set a two-dimensional array as an empty bucket, and the search sequence puts the data one by one into the corresponding bucket.
Put the item back into the original sequence one by one from the empty bucket, and mark the starting position of the section as true in the tag array.
Return the next section header location for the main sorting process.

Practice

JavaScript code:

Array.prototype.InterpolaionTagSort = function()
{//Whale Chen agrees to "Wikipedia: Text of Creative Commons Attribution-ShareAlike 3.0 Unported License." Authorization Date: 2019/06/21//
  var end = this.length; 
  if ( end > 1 ){ 
    var start = 0 ; 
    var Tag = new Array( end ); //Algorithm step-1 (Set an equal amount of Tag array to initialize to a false value)
    for ( i = 0; i < end; i++ ){ Tag[ i ] = false; } 
    Divide( this ); } 
  while ( end > 1 ){ //Algorithm step-2  (The main sorting determines whether all sections of the original sequence have been recursively completed.)  
    while ( Tag[ --start ] == false ){ } //When Tag[start] = true, start is the bucket sort start position (array header)
    Divide( this ); } //Algorithm step-6 (Return the next section header position recursively to the main sorting [Algorithm step-2] processing)

  function Divide( A ){   
    var min = A[ start ]; 
    var max = A[ start ];
    for( i = start + 1; i < end; i++ ){ if ( A[ i ] < min ){ min = A[ i ]; } else{ if ( A [ i ] > max ){ max = A[ i ]; } } }
    if ( min == max ){ end = start; } //Algorithm step-3 (Stop bucket sorting if the array has been sorted)
    else{  //Algorithm step-3 (Perform bucket sorting)                                         
         var p = 0; 
         var size = end - start; 
         var Bucket = new Array( size ); 
         for ( i = 0; i < size; i++ ){ Bucket[ i ] = new Array( ); } //Algorithm step-4 (Set a two-dimensional array as an empty bucket)
         for ( i = start; i < end; i++ ){//Algorithm step-4 (The search sequence puts the number into the bucket corresponding to the interpolation)  
           p = Math.floor ( ( ( A[ i ] - min ) / ( max - min ) ) * ( size - 1 ) ); //(Interpolation computing. p is array pointer position)
           Bucket[ p ].push( A[ i ] ); 
         } 
         for ( i = 0; i < size; i++ ){
           if ( Bucket[ i ].length > 0){//Algorithm step-5 (Put the numbers back into the original array one by one from not empty buckets)     
             Tag[ start ] = true; //Algorithm step-5 (Mark the start position of the section as true in the tag array)
             for ( j = 0; j < Bucket[ i ].length; j++ ){ A[ start++ ] = Bucket[ i ][ j ]; } 
           } 
         }  
    }
  }
};

In-Place Interpolaion Tag Sort

The in-place interpolation tag sort is an in-place algorithm of interpolation sort. In-place Interpolation Tag Sort can achieve sorting by only N times of swapping by maintaining N bit tags; however, the array to be sorted must be a continuous integer sequence and not repeated, or the series is completely evenly distributed to approximate The number of arithmetical progression.

The factor column data must not be repeated. For example, sorting 0~100 can be sorted in one step. The number of exchanges is: $O(n)$ , the calculation time complexity is: $O(n)$ , and the worst space complexity is $O(n)bits$ . If the characteristics of the series meet the conditional requirements of this sorting method: "The array is a continuous integer or an arithmetical progression that does not repeat", the in-place interpolation tag sort will be an excellent sorting method that is extremely fast and saves memory space.

In-place Interpolation Tag Sort Algorithm

In-place Interpolation Tag Sort sorts non-repeating consecutive integer series, only one Boolean data type tag array with the same length as the original array, the array calculates the interpolation of the data from the beginning, and the interpolation points to a new position of the array. Position, the position that has been swapped is marked as true in the corresponding position of the tag array, and is incremented until the end of the array is sorted.

Algorithm process:

Set an equal number of tag arrays to initialize to false values.
Visit the array when tag[ i ] is false, calculate the position corresponding to the interpolation=p.
Swap a[ i ] and a[ p ],let tag[ p ] = true.
The tour array is completed and the sorting is completed.

Practice

JavaScript code:

Array.prototype.In-PlaceInterpolaionTagSort = function(a)
{
  var temp = 0;
  var p = 0;
  var n = a.length;
  var tag = new Array( n );
  for ( i = 0; i < n; i++ ){ tag[ i ] = false; }
  var min = a[ 0 ];
  var max = a[ 0 ];
  for ( i = 1; i < n; i++ ){ if ( a[ i ] < min ){ min = a[ i ]; }else{ if (a[ i ] > max){ max = a[ i ]; } } } 
 
  for ( i = 0; i < n; i++ ){
    while ( tag[ i ] == false ){ 
      p = Math.floor(( (a[ i ]-min) / (max-min) ) * (n-1) );
      temp = a[ i ];
      a[ i ] = a[ p ]; 
      a[ p ] = temp;
      tag[ p ] = true; 
    } 
  } 
};

The origin of In-place sorting performed in $O(n)$ time

In "Mathematical Analysis of Algorithms", (Information Processing '71, North Holland Publ.'72) Donald Knuth remarked "... that research on computional complexity is an interesting way to sharpen our tools for more routine problems we face from day to day." ^[6]

The famous American computer scientist Donald Knuth in the mathematical analysis of algorithms pointed out that:"With respect to the sorting problem, Knuth points out, that time effective in-situ permutation is inherently connected with the problem of finding the cycle leaders, and in-situ permutations could easily be performed in $O(n)$ time if we would be allowed to manipulate n extra "tag" bits specifying how much of the permutation has been carried out at any time. Without such tag bits, he concludes "it seems reasonable to conjecture that every algorithm will require for in-situ permutation at least $O(nlogn)$ steps on the average." ^[6]

The In-place Interpolation Tag Sort is one of the sorting algorithms that the Donald Knuth professor said: "manipulate n extra "tag" bits...finding the cycle leaders, and in-situ permutations could easily be performed in $O(n)$ time".

Similar sorting method

Bucket sort mixing other sorting methods and recursive algorithm

Bucket sort can be mixed with other sorting methods to complete sorting. If it is sorted by bucket sort and insert sort，Also a fairly efficient sorting method. But when the series appears a large deviation from the value: For example, when the maximum value of the series is greater than N times the next largest value. After the series of columns are processed, the distribution is that all the elements except the maximum value fall into the same bucket. The second sorting method uses insert sort. May cause execution complexity to fall into $O(n^{2})$ . This has lost the meaning and high-speed performance of using bucket sort.

Interpolation sort is a way of recursively using bucket sort. After performing recursion, still use bucket sort to disperse the series. This can avoid the above situation. If you want to make the recursive interpolation sort execution complexity fall into $O(n^{2})$ ,It is necessary to present a factorial amplification in the entire series. In fact, there is very little chance that a series of special distributions will occur.

It is worth noting that: Bucket sort hybrid insert sort method, The average time complexity of the algorithm is $O(n+n^{2}/k+k)$ . ^[7] When $k=n$ , Use $n$ buckets just like interpolation sort. The average time complexity is $O(3n)$ . However, interpolation sort is a recursive method of bucket sort. The average time complexity of the algorithm is the same as pure bucket sort is only $O(n+k)$ . ^[8] This is still somewhat different in sorting execution efficiency.

Extra link

[1] Donald Knuth

[2] interpolation sort Algorithm--Whale Chen 2012/09/16

[3] interpolation sort (Pascal version available)

[4] 插值標簽排序演算法 Interpolation Tag Sort Algorithm

Reference

^ NIST Algorithm. "interpolation sort". Definition: See histogram sort.
^ en.wikipedia. "Histogram sort". Another variant of bucket sort known as histogram sort or counting sort adds an initial pass that counts the number of elements that will fall into each bucket using a count array. Using this information, the array values can be arranged into a sequence of buckets in-place by a sequence of exchanges, leaving no space overhead for bucket storage.
^ zh.wikipedia. "桶排序（Bucket sort）" (in Chinese). 平均時間複雜度（Average performance） $O(n+k)$
^ Wikipedia. "Bucket sort Average-case analysis". en.wikipedia. Note that if k is chosen to be $k=n$ , then bucket sort runs in $O(n)$ average time, given a uniformly distributed input.
^ zh.wikipedia. "桶排序（Bucket sort）" (in Chinese). 平均時間複雜度（Average performance） $O(n+k)$
^ ^a ^b Karl-Dietrich Neubert (1998). "The FlashSort Algorithm". Retrieved 2007-11-06.
^ en.wikipedia. "Bucket sort Average-case analysis". Wikipedia. Assume insertion sort is used to sort each bucket, then the third step costs $O(\textstyle \sum _{i=1}^{k}\displaystyle n_{i}^{2})$ , where $n_{i}$ is the length of the bucket indexed $i$ . Since we are concerning the average time, the expectation $E(n_{i}^{2})$ have to be evaluated instead. Let $X_{ij}$ be the random variable of element $j$ being placed in bucket $i$ . We have $n_{i}=\sum _{j=1}^{n}X_{ij}$ . Therefore,
${\begin{aligned}E(n_{i}^{2})&=E\left(\sum _{j=1}^{n}X_{ij}\sum _{k=1}^{n}X_{ik}\right)\\&=E\left(\sum _{j=1}^{n}\sum _{k=1}^{n}X_{ij}X_{ik}\right)\\&=E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k\leq n}\sum _{j\neq k}X_{ij}X_{ik}\right)\end{aligned}}$
The last line separates the summation into the case $j=k$ and the case $j\neq k$ . Since the chance of an object distributed to bucket $i$ is $1/k$ , $X_{ij}$ is 1 with probability $1/k$ and 0 otherwise.
$E(X_{ij}^{2})=1^{2}\cdot \left({\frac {1}{k}}\right)+0^{2}\cdot \left(1-{\frac {1}{k}}\right)={\frac {1}{k}}$

$E(X_{ij}X_{ik})=1\cdot \left({\frac {1}{k}}\right)\left({\frac {1}{k}}\right)={\frac {1}{k^{2}}}$
With the summation, it would be
$E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k\leq n}\sum _{j\neq k}X_{ij}X_{ik}\right)=n\cdot {\frac {1}{k}}+n(n-1)\cdot {\frac {1}{k^{2}}}={\frac {n^{2}+nk-n}{k^{2}}}$
Finally, the complexity would be $O\left(\sum _{i=1}^{k}E(n_{i}^{2})\right)=O\left(\sum _{i=1}^{k}{\frac {n^{2}+nk-n}{k^{2}}}\right)=O\left({\frac {n^{2}}{k}}+n\right)$ .
The last step of bucket sort, which is concatenating all the sorted objects in each buckets, requires $O(k)$ time. Therefore, the total complexity is $O\left(n+{\frac {n^{2}}{k}}+k\right)$ . {{cite web}}: line feed character in |quote= at position 555 (help)
^ zh.wikipedia. "桶排序(Bucket sort)" (in Chinese). 平均時間複雜度(average time complexity) $O(n+k)$

Extra References

[1] NIST Algorithm. "interpolation sort". Definition: See histogram sort.

[2] .wikipedia. "Histogram sort". Another variant of bucket sort known as histogram sort or counting sort adds an initial pass that counts the number of elements that will fall into each bucket using a count array. Using this information, the array values can be arranged into a sequence of buckets in-place by a sequence of exchanges, leaving no space overhead for bucket storage.

[3] zh.wikipedia. "桶排序（Bucket sort）" (in Chinese). 平均時間複雜度（Average performance） $O(n+k)$

[4] Wikipedia. "Bucket sort Average-case analysis". en.wikipedia. Note that if k is chosen to be $k=n$ , then bucket sort runs in $O(n)$ average time, given a uniformly distributed input.

[5] zh.wikipedia. "桶排序（Bucket sort）" (in Chinese). 平均時間複雜度（Average performance） $O(n+k)$

[neubert_code-6] Karl-Dietrich Neubert (1998). "The FlashSort Algorithm". Retrieved 2007-11-06.

[7] .wikipedia. "Bucket sort Average-case analysis". Wikipedia. Assume insertion sort is used to sort each bucket, then the third step costs $O(\textstyle \sum _{i=1}^{k}\displaystyle n_{i}^{2})$ , where $n_{i}$ is the length of the bucket indexed $i$ . Since we are concerning the average time, the expectation $E(n_{i}^{2})$ have to be evaluated instead. Let $X_{ij}$ be the random variable of element $j$ being placed in bucket $i$ . We have $n_{i}=\sum _{j=1}^{n}X_{ij}$ . Therefore,
${\begin{aligned}E(n_{i}^{2})&=E\left(\sum _{j=1}^{n}X_{ij}\sum _{k=1}^{n}X_{ik}\right)\\&=E\left(\sum _{j=1}^{n}\sum _{k=1}^{n}X_{ij}X_{ik}\right)\\&=E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k\leq n}\sum _{j\neq k}X_{ij}X_{ik}\right)\end{aligned}}$
The last line separates the summation into the case $j=k$ and the case $j\neq k$ . Since the chance of an object distributed to bucket $i$ is $1/k$ , $X_{ij}$ is 1 with probability $1/k$ and 0 otherwise.
$E(X_{ij}^{2})=1^{2}\cdot \left({\frac {1}{k}}\right)+0^{2}\cdot \left(1-{\frac {1}{k}}\right)={\frac {1}{k}}$

$E(X_{ij}X_{ik})=1\cdot \left({\frac {1}{k}}\right)\left({\frac {1}{k}}\right)={\frac {1}{k^{2}}}$
With the summation, it would be
$E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k\leq n}\sum _{j\neq k}X_{ij}X_{ik}\right)=n\cdot {\frac {1}{k}}+n(n-1)\cdot {\frac {1}{k^{2}}}={\frac {n^{2}+nk-n}{k^{2}}}$
Finally, the complexity would be $O\left(\sum _{i=1}^{k}E(n_{i}^{2})\right)=O\left(\sum _{i=1}^{k}{\frac {n^{2}+nk-n}{k^{2}}}\right)=O\left({\frac {n^{2}}{k}}+n\right)$ .
The last step of bucket sort, which is concatenating all the sorted objects in each buckets, requires $O(k)$ time. Therefore, the total complexity is $O\left(n+{\frac {n^{2}}{k}}+k\right)$ . {{cite web}}: line feed character in |quote= at position 555 (help)

[8] zh.wikipedia. "桶排序(Bucket sort)" (in Chinese). 平均時間複雜度(average time complexity) $O(n+k)$

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

v t e Sorting algorithms
Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Proportion extend sort Quicksort
Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Kirkpatrick–Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort
Impractical sorts	Stooge sort Slowsort Bogosort

Algorithm

Interpolation sort algorithm

Practice

Variant

Interpolation Tag Sort

Interpolation Tag Sort Algorithm

Practice

In-Place Interpolaion Tag Sort

In-place Interpolation Tag Sort Algorithm

Practice

The origin of In-place sorting performed in O ( n ) {\displaystyle O(n)} time

Similar sorting method

Bucket sort mixing other sorting methods and recursive algorithm

Extra link

Reference

Extra References

The origin of In-place sorting performed in $O(n)$ time