Permutasiya nizamlaması

Alqoritmin işləmə prinsipi çox sadədir. Alqoritm müəyyən ədədlər massivinin Permutasiyalarını növbə ilə yoxlayır və sıralanmış vəziyyətin tapılması halında öz işini sona çatdırır. Alqoritmi sadə olaraq aşağıdakı formada yazmaq olar: Massiv sıralı olana qədər, Permutasiyasın al.

Nümunə

redaktə

nizamlamaq istədiyimiz massiv aşağıdakı kimi olsun.

1285


Burda massivin permutasiyaları alınaraq, massiv sıralanana qədər davam etdirilir. Bu əməliyyatların sayı n! ilə hesablandığından burda sıralanmanın ən pis ehtimalı 4! = 24-dür.

2 6 8 1

2 8 6 1

2 6 8 1

8 6 2 1

2 6 8 1

2 6 1 8

2 1 6 8

1 2 6 8

Yuxarıdakı permutasiyalardan sonuncusu sıralanmış vəziyyətdədir və alqoritm bu vəziyyətə çatdıqda sonlanır.

Java proqramlaşdırma dilində təsviri

redaktə
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
 
public class PermutationSort 
{
	public static void main(String[] args)
	{
		int[] a={3,2,1,8,9,4,6};
		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;
	}
}

Həmçinin bax

redaktə