Posted By

binaryadder on 01/06/12


Tagged

bogosort


Versions (?)

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

  1. import java.util.*;
  2.  
  3. public class Bogosort {
  4. private final static Random r = new Random();
  5.  
  6. public static int[] verboseBogosort(int[] deck){
  7. System.out.println(toString(deck));
  8. do{
  9. deck = shuffle(deck);
  10. System.out.println(toString(deck));
  11. } while (!inOrder(deck));
  12. System.out.println(toString(deck));
  13. return deck;
  14. }
  15.  
  16. private static boolean inOrder(int[] deck){
  17. for (int i = 0; i < deck.length - 1; i++){
  18. if (deck[i] > deck[i + 1]){
  19. return false;
  20. }
  21. }
  22. return true;
  23. }
  24.  
  25. // assumes that the deck has at least two values
  26. private static int[] shuffle(int[] deck){
  27. int[] shuffledDeck = new int[deck.length];
  28. LinkedList ll = new LinkedList(deck[0]);
  29. for (int i = 1; i < deck.length; i++){
  30. ll.addNode(deck[i]);
  31. }
  32. //System.out.println(ll.toString());
  33. for (int count = 0; count < deck.length; count++){
  34. shuffledDeck[count] = ll.deleteNode(r.nextInt(ll.size()));
  35. //if (ll.size() > 0) System.out.println(ll.toString());
  36. //try{Thread.sleep(3000);} catch(Exception e){}
  37. }
  38. return shuffledDeck;
  39. }
  40.  
  41. private static String toString(int a[]){
  42. StringBuilder result = new StringBuilder();
  43. for (int i = 0; i < a.length - 1; i++){
  44. result.append(a[i] + " ");
  45. }
  46. result.append(a[a.length - 1]);
  47. return result.toString();
  48. }
  49. }
  50.  
  51. class LinkedList{
  52. private int size;
  53. private Node firstNode;
  54. private Node lastNode;
  55.  
  56. public LinkedList(int firstValue){
  57. this.firstNode = this.lastNode = new Node(firstValue);
  58. this.size = 1;
  59. }
  60.  
  61. public int size(){return this.size;}
  62.  
  63. public void addNode(int value){
  64. Node newNode = new Node(value);
  65. lastNode.setNextNode(newNode);
  66. lastNode = newNode;
  67. size++;
  68. }
  69.  
  70. public int deleteNode(int nthNode){
  71. //Node prevNode = null;
  72. //Node currNode = null;
  73. int result = -99999;
  74. if (nthNode == 0){
  75. result = this.firstNode.getValue();
  76. this.firstNode = firstNode.getNextNode();
  77. }
  78. else if (nthNode == this.size - 1){
  79. Node tempNode = this.firstNode;
  80. result = this.lastNode.getValue();
  81. for (int i = 1; i < size - 1; i++){
  82. tempNode = tempNode.getNextNode();
  83. }
  84. lastNode = tempNode;
  85. lastNode.setNextNode(null);
  86. }
  87. else{
  88. Node prevNode = this.firstNode;
  89. Node currNode = this.firstNode.getNextNode();
  90. for(int i = 1; i < nthNode; i++){
  91. prevNode = currNode;
  92. currNode = currNode.getNextNode();
  93. }
  94. result = currNode.getValue();
  95. prevNode.setNextNode(currNode.getNextNode());
  96. }
  97. size--;
  98. return result;
  99. }
  100.  
  101. public String toString(){
  102. StringBuilder result = new StringBuilder();
  103. for(Node currNode = this.firstNode; currNode.getNextNode() != null; currNode = currNode.getNextNode()){
  104. result.append(currNode.getValue() + " -> ");
  105. }
  106. result.append(lastNode.getValue());
  107. return result.toString();
  108. }
  109.  
  110. private class Node{
  111. private int value;
  112. private Node nextNode;
  113.  
  114. public Node(){
  115. this.value = -1;
  116. this.nextNode = null;
  117. }
  118.  
  119. public Node(int value){
  120. this.value = value;
  121. this.nextNode = null;
  122. }
  123.  
  124. public Node(int value, Node nextNode){
  125. this.value = value;
  126. this.nextNode = nextNode;
  127. }
  128.  
  129. public int getValue(){return this.value;}
  130. public Node getNextNode(){return this.nextNode;}
  131.  
  132. public void setValue(int value){this.value = value;}
  133. public void setNextNode(Node nextNode){this.nextNode = nextNode;}
  134. }
  135. }

Report this snippet  

You need to login to post a comment.