Упражнения на Java: алгоритм сортировки шариков

Алгоритм сортировки Java: упражнение-8 с решением

Напишите Java-программу для сортировки массива натуральных чисел с использованием алгоритма сортировки бисера.

Согласно Википедии, «сортировка по бисеру, также называемая гравитационной сортировкой, является естественным алгоритмом сортировки, разработанным Джошуа Дж. Аруланандхамом, Кристианом С. Калуде и Майклом Дж. Диннином в 2002 году и опубликованным в Бюллетене Европейской ассоциации теоретических компьютерных наук». Как цифровые, так и аналоговые аппаратные реализации сортировки по бусинкам могут достигать времени сортировки O (n), однако реализация этого алгоритма, как правило, значительно медленнее в программном обеспечении и может использоваться только для сортировки списков положительных целых чисел. Казалось бы, даже в лучшем случае алгоритм требует O (n2) пробела ».

Пример решения:

Java-код:

public class BeadSort 
{
	public static void main(String[] args)
	{
		BeadSort now=new BeadSort();
		int[] arr=new int[(int)(Math.random()*11)+5];
		for(int i=0;i<arr.length;i++)
			arr[i]=(int)(Math.random()*10);
		System.out.print("Unsorted: ");
		now.display1D(arr);
 
		int[] sort=now.beadSort(arr);
		System.out.print("Sorted: ");
		now.display1D(sort);
	}
	int[] beadSort(int[] arr)
	{
		int max=0;
		for(int i=0;i<arr.length;i++)
			if(arr[i]>max)
				max=arr[i];
 
		//Set up abacus
		char[][] grid=new char[arr.length][max];
		int[] levelcount=new int[max];
		for(int i=0;i<max;i++)
		{
			levelcount[i]=0;
			for(int j=0;j<arr.length;j++)
				grid[j][i]='_';
		}
		/*
		display1D(arr);
		display1D(levelcount);
		display2D(grid);
		*/
 
		//Drop the beads
	
		for(int i=0;i<arr.length;i++)
		{
			int num=arr[i];
			for(int j=0;num>0;j++)
			{
				grid[levelcount[j]++][j]='*';
				num--;
			}
			
		}
		
		System.out.println();
		display2D(grid);
		//Count the beads
		int[] sorted=new int[arr.length];
		for(int i=0;i<arr.length;i++)
		{
			int putt=0;
			for(int j=0;j<max&&grid[arr.length-1-i][j]=='*';j++)
				putt++;
			sorted[i]=putt;
		}
 
		return sorted;
	}
	void display1D(int[] arr)
	{
		for(int i=0;i<arr.length;i++)
			System.out.print(arr[i]+" ");
		System.out.println();
	}
	void display1D(char[] arr)
	{
		for(int i=0;i<arr.length;i++)
			System.out.print(arr[i]+" ");
		System.out.println();
	}
	void display2D(char[][] arr)
	{
		for(int i=0;i<arr.length;i++)
			display1D(arr[i]);
		System.out.println();
	}
}

Пример вывода:

 Unsorted: 8 2 2 3 4 6 7 8 4 0 8 
* * * * * * * * 
* * * * * * * * 
* * * * * * * * 
* * * * * * * _ 
* * * * * * _ _ 
* * * * _ _ _ _ 
* * * * _ _ _ _ 
* * * _ _ _ _ _ 
* * _ _ _ _ _ _ 
* * _ _ _ _ _ _ 
_ _ _ _ _ _ _ _ 
Отсортировано: 0 2 2 3 4 4 6 7 8 8 8 

Блок - схема:

Редактор кода Java:

Внесите свой код и комментарии через Disqus.

Предыдущая: Написать Java-программу для сортировки массива заданных целых чисел с использованием алгоритма сортировки вставками.
Далее: Напишите программу на Java для сортировки массива натуральных чисел, используя алгоритм сортировки BogoSort.