Java Exercises: Permutation sort Algorithm

Last update on March 13 2025 09:05:34 (UTC/GMT +8 hours)

Write a Java program to sort an array of given integers using the Permutation sort algorithm.

Implement a permutation sort, which generates the possible permutations of the input array/list until discovering the sorted one.

Sample Solution:

Java Code:

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
 
public class PermutationSort 
{
	public static void main(String[] args)
	{
		int[] a={7, -5, 3, 2, 1, 0, 45};
		System.out.println("Unsorted: " + Arrays.toString(a));
		a=pSort(a);
		System.out.println("Sorted: " + Arrays.toString(a));
	}
	public static int[] pSort(int[] a)
	{
		List<int[]> list=new ArrayList<int[]>();
		permute(a,a.length,list);
		for(int[] x : list)
			if(isSorted(x))
				return x;
		return a;
	}
	private static void permute(int[] a, int n, List<int[]> list) 
	{
		if (n == 1) 
		{
			int[] b=new int[a.length];
			System.arraycopy(a, 0, b, 0, a.length);
			list.add(b);
		    return;
		}
		for (int i = 0; i < n; i++) 
		{
		        swap(a, i, n-1);
		        permute(a, n-1, list);
		        swap(a, i, n-1);
		 }
	}
	private static boolean isSorted(int[] a)
	{
		for(int i=1;i<a.length;i++)
			if(a[i-1]>a[i])
				return false;
		return true;
	}
	private static void swap(int[] arr,int i, int j)
	{
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
}

Sample Output:

Unsorted: [7, -5, 3, 2, 1, 0, 45]
Sorted: [-5, 0, 1, 2, 3, 7, 45]

Flowchart:

For more Practice: Solve these Related Problems:

• Write a Java program to implement permutation sort and measure the number of permutations generated before sorting.
• Write a Java program to modify permutation sort to terminate early if a sorted permutation is found within a set time limit.
• Write a Java program to implement permutation sort on a small array and output each permutation tried during the process.
• Write a Java program to simulate permutation sort and compare its efficiency with bogosort on identical input arrays.

Java Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Java program to sort an array of given integers using Pancake sort Algorithm.
Next: Write a Java program to sort an array of given integers Shell Sort Algorithm.