Bogosort

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;}
	}
}