Interpolation Sort

Interpolation sort is an algorithm for sorting an array of values by inserting each element into its proper position within a sorted sublist of previously sorted elements. It is an extension of binary search to find the position where an element should be inserted.

The algorithm works by estimating the position of the element to be inserted, based on the range of values in the sorted sublist and the value of the element itself. This estimate is obtained using a formula that takes into account the minimum and maximum values in the sublist, as well as the position of the element relative to these values. The estimate is then used to perform a binary search on the sublist to find the correct position for the element.

Interpolation sort has an average case time complexity of O(n log n) and a worst case time complexity of O(n^2), which occurs when the input array is already sorted in reverse order. However, in practice, it tends to perform well on inputs that are already partially sorted, or have a fairly even distribution of values.

Overall, interpolation sort can be a useful sorting algorithm when dealing with certain types of input data, but its performance may not be as good as other sorting algorithms in some cases.

Here given code implementation process.

Java

/*
  Java program
  Interpolation Sort
*/
import java.util.*;
public class Sorting
{
	// Display elements of given sequence
	public void display(int[] sequence, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			System.out.print("  " + sequence[i]);
		}
		System.out.print("\n");
	}
	// Sort elements using interpolation sort
	public void interpolationSort(int[] sequence, int size)
	{
		if (size <= 0)
		{
			return;
		}
		int start = 0;
		int end = size;
		int location = 0;
		int slot = 0;
		// Loop controlling variables
		int i = 0;
		int j = 0;
		// Define min max variable
		int min = 0;
		int max = 0;
		ArrayList < Integer > process = new ArrayList < Integer > ();
		ArrayList < ArrayList < Integer >> bucket = new ArrayList < ArrayList < Integer > > ();
		// Assign the memory of each slot
		for (i = 0; i < size; ++i)
		{
			// Allocate memory
			bucket.add(new ArrayList < Integer > ());
		}
		// Add the size of array
		process.add(size);
		while (process.size() > 0)
		{
			// Get last size
			location = process.get(process.size() - 1);
			// Remove the last element of process
			process.remove(process.size() - 1);
			// Get start location
			start = end - location;
			// Get starting element
			max = sequence[start];
			min = sequence[start];
			// Find minimum and maximum
			for (i = start + 1; i < end; i++)
			{
				if (sequence[i] > max)
				{
					max = sequence[i];
				}
				else if (sequence[i] < min)
				{
					min = sequence[i];
				}
			}
			if (min == max)
			{
				// Change last element
				end = end - location;
			}
			else
			{
				for (i = start; i < end; ++i)
				{
					// Calculate slot
					slot = (int) Math.floor(((sequence[i] - min) / (double)(max - min)) * (location - 1));
					bucket.get(slot).add(sequence[i]);
				}
				for (i = 0; i < location; ++i)
				{
					if (bucket.get(i).isEmpty() == false)
					{
						// When bucket slot not empty
						// Assign the bucket element into actual array
						for (j = 0; j < bucket.get(i).size(); j++)
						{
							sequence[start] = bucket.get(i).get(j);
							start++;
						}
						// This is useful to trace the sort slot elements
						process.add(bucket.get(i).size());
					}
				}
				// Remove the existing bucket element
				for (i = 0; i < size; ++i)
				{
					bucket.get(i).clear();
				}
			}
		}
	}
	public static void main(String[] args)
	{
		Sorting task = new Sorting();
		// Define array of positive integer elements
		int[] s1 = {
			61 , 53 , 42 , 14 , 64 , 2 , -2 , 6 , 17 , 9 , 11 , 3 , 3 , 4 , 7
		};
		int[] s2 = {
			16 , 12 , 6 , 2 , 8 , 5 , 9 , 3 , 5 , 21 , 22
		};
		// Test case A
		int size = s1.length;
		System.out.print("  Before Sort \n");
		task.display(s1, size);
		System.out.print("  After Sorted \n");
		task.interpolationSort(s1, size);
		task.display(s1, size);
		// Test case B
		size = s2.length;
		System.out.print("\n  Array \n");
		task.display(s2, size);
		task.interpolationSort(s2, size);
		System.out.print("  After Sorted \n");
		task.display(s2, size);
	}
}

Output

  Before Sort
  61  53  42  14  64  2  -2  6  17  9  11  3  3  4  7
  After Sorted
  -2  2  3  3  4  6  7  9  11  14  17  42  53  61  64

  Array
  16  12  6  2  8  5  9  3  5  21  22
  After Sorted
  2  3  5  5  6  8  9  12  16  21  22

Interpolation Sort

Output

Comment

New Comment