Bogosort

/ Published in: Java

My implementation of the best sorting algorithm ever: Bogosort!

Test code:

int[] deck = {64, 25, 12, 22, 11}; Bogosort.verboseBogosort(deck);

Output:

64 25 12 22 11 22 64 25 11 12 12 11 22 64 25 12 64 25 22 11 64 25 12 11 22 12 25 22 64 11 12 22 11 64 25 12 22 64 11 25 25 12 11 22 64 64 25 11 12 22 11 22 12 64 25 25 12 11 64 22 12 22 11 64 25 25 64 22 12 11 22 12 64 11 25 22 64 25 11 12 12 64 25 11 22 12 64 25 11 22 64 25 11 22 12 11 64 22 12 25 12 25 64 22 11 11 25 22 12 64 11 64 22 12 25 25 22 64 11 12 64 22 25 12 11 12 22 64 11 25 22 64 25 12 11 12 11 22 25 64 64 25 12 11 22 12 64 25 11 22 22 64 25 11 12 25 22 64 12 11 22 25 11 12 64 22 64 25 11 12 11 12 22 64 25 22 12 25 11 64 25 22 12 11 64 64 22 12 11 25 25 12 22 64 11 11 12 64 25 22 25 11 64 12 22 64 22 11 12 25 12 11 64 25 22 64 11 25 12 22 25 12 22 64 11 11 64 25 22 12 11 22 64 12 25 11 22 64 25 12 11 12 22 64 25 25 64 12 22 11 12 11 25 22 64 12 11 25 22 64 11 12 64 22 25 11 12 22 25 64 11 12 22 25 64

`import java.util.*; public class Bogosort {	private final static Random r = new Random(); 	public static int[] verboseBogosort(int[] deck){		System.out.println(toString(deck));		do{			deck = shuffle(deck);			System.out.println(toString(deck));		} 	while (!inOrder(deck));		System.out.println(toString(deck));		return deck;	} 	private static boolean inOrder(int[] deck){		for (int i = 0; i < deck.length - 1; i++){			if (deck[i] > deck[i + 1]){				return false;			}		}		return true;	} 	// assumes that the deck has at least two values	private static int[] shuffle(int[] deck){		int[] shuffledDeck = new int[deck.length];		LinkedList ll = new LinkedList(deck[0]);        for (int i = 1; i < deck.length; i++){        	ll.addNode(deck[i]);        }        //System.out.println(ll.toString());        for (int count = 0; count < deck.length; count++){        	shuffledDeck[count] = ll.deleteNode(r.nextInt(ll.size()));            //if (ll.size() > 0) System.out.println(ll.toString());            //try{Thread.sleep(3000);} catch(Exception e){}        }		return shuffledDeck;	} 	private static String toString(int a[]){		StringBuilder result = new StringBuilder();		for (int i = 0; i < a.length - 1; i++){			result.append(a[i] + " ");		}		result.append(a[a.length - 1]);		return result.toString();	} } class LinkedList{	private int size;	private Node firstNode;	private Node lastNode; 	public LinkedList(int firstValue){		this.firstNode = this.lastNode = new Node(firstValue);		this.size = 1;	} 	public int size(){return this.size;} 	public void addNode(int value){		Node newNode = new Node(value);		lastNode.setNextNode(newNode);		lastNode = newNode;		size++;	} 	public int deleteNode(int nthNode){		//Node prevNode = null;		//Node currNode = null;		int result = -99999;		if (nthNode == 0){			result = this.firstNode.getValue();			this.firstNode = firstNode.getNextNode();		}		else if (nthNode == this.size - 1){			Node tempNode = this.firstNode;			result = this.lastNode.getValue();			for (int i = 1; i < size - 1; i++){				tempNode = tempNode.getNextNode();			}			lastNode = tempNode;			lastNode.setNextNode(null);		}		else{			Node prevNode = this.firstNode;			Node currNode = this.firstNode.getNextNode();			for(int i = 1; i < nthNode; i++){				prevNode = currNode;				currNode = currNode.getNextNode();		    }			result = currNode.getValue();			prevNode.setNextNode(currNode.getNextNode());		}		size--;		return result;	} 	public String toString(){		StringBuilder result = new StringBuilder();		for(Node currNode = this.firstNode; currNode.getNextNode() != null; currNode = currNode.getNextNode()){			result.append(currNode.getValue() + " -> ");		}		result.append(lastNode.getValue());		return result.toString();	} 	private class Node{		private int value;		private Node nextNode; 		public Node(){			this.value = -1;			this.nextNode = null;		} 		public Node(int value){			this.value = value;			this.nextNode = null;		} 		public Node(int value, Node nextNode){			this.value = value;			this.nextNode = nextNode;		} 		public int getValue(){return this.value;}		public Node getNextNode(){return this.nextNode;} 		public void setValue(int value){this.value = value;}		public void setNextNode(Node nextNode){this.nextNode = nextNode;}	}}`