Дата публикации: 05.11.2013 15:42:09
My friend pointed me to the page with the BeadSort algorithm implemented in different programming languages. He noted that the Python implementation is compact and beautiful, while the Java implementation is excessive and ugly. Let's look at this unreadable junk.
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(); } }
Seems this code is written by a man who learned about Java syntax, but understood nothing. Let's refactor this code in accordance with the Code Conventions and remove the debugging output.
import java.util.*; public class BeadSort { public static void main(String[] args) { Random random = new Random(); int[] array = new int[random.nextInt(11) + 5]; for (int i = 0; i < array.length; i++) { array[i] = random.nextInt(10); } System.out.println(Arrays.toString(array)); System.out.println(Arrays.toString(beadsort(array))); } public static int[] beadsort(int[] array) { int max = array[0]; for (int i = 1; i < array.length; i++) { if (max < array[i]) { max = array[i]; } } int[] counter = new int[max]; boolean[][] grid = new boolean[array.length][max]; for (int value : array) { for (int j = 0; value > 0; value--, j++) { grid[counter[j]++][j] = true; } } int[] sorted = new int[array.length]; for (int i = 0; i < array.length; i++) { for (int j = 0; j < max && grid[i][j]; j++) { sorted[i]++; } } return sorted; } }
Now, we can see what's what. Obviously, there is no need in using a two-dimensional array, which requires a lot of memory. Remove it and see how compact the code becomes. Unfortunately, there is no any library method in Java to calculate minimal value of array.
public static int[] beadsort(int[] array) { int max = array[0]; for (int i = 1; i < array.length; i++) { if (max < array[i]) { max = array[i]; } } int[] sorted = new int[array.length]; int[] counter = new int[max]; for (int value : array) { for (int j = 0; value > 0; value--, j++) { sorted[counter[j]++]++; } } return sorted; }
At this point, you can use this code on an amateur page for languages comparison. However, it is not applicable for professional use, as it can not sort the negative integers. Besides, it spends a lot of resources to compare a couple of very large numbers. Fix this drawback and add sorting in ascending order.
public static int[] beadsort(int[] array, boolean reverse) { Objects.requireNonNull(array, "array"); if (array.length == 0) { return array; } int max = array[0]; int min = array[0]; for (int i = 1; i < array.length; i++) { if (max < array[i]) { max = array[i]; } if (min > array[i]) { min = array[i]; } } int[] sorted = new int[array.length]; for (int i = 0; i < sorted.length; i++) { sorted[i] = min; } int[] counter = new int[max - min]; for (int value : array) { for (int i = 0; value > min; value--, i++) { int index = counter[i]++; if (!reverse) { index = sorted.length - index - 1; } sorted[index]++; } } return sorted; }
It has been a funny theoretical exercise that proved that well-formatted code works better and is easier to maintain. The source file of the example is available.
PS. Use Dual-pivot Quicksort introduced in Java 7: java.util.Arrays.sort(array); which is very fast.