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