Skip to main content

Interpolation Sort

Here given code implementation process.

/*
  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




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment