API tools faq
paste
Advertisement
Guest User

Bogosort

a guest
Nov 19th, 2017
92
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 20.03 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. Andi ******
  3.  
  4. I implemented HeapSort and SelectionSort, and reused my earlier implementation of BubbleSort. I also, for some reason, implemented Bogosort.
  5.  
  6. Here's each algorithm's expected time complexity:
  7.  
  8. HeapSort        O(NlogN)
  9. SelectionSort   O(N^2)
  10. BubbleSort      O(N^2)
  11. BogoSort        A((N+1)!) (worst-case is unbounded)
  12.  
  13. And each algorithm's auxiliary space complexity:
  14.  
  15. HeapSort        O(1)
  16. SelectionSort   O(1)
  17. BubbleSort      O(1)
  18. BogoSort        O(1)
  19.  
  20. So all four algorithms are in-place.
  21. That's one area Bogosort isn't nearly bad enough, at least.
  22.  
  23. Next, an analysis of the implementation's actual runtime. Rather than just measuring the clock time before and after the function call, this time I used a counter variable to measure the number of comparisons, allowing for more meaningful comparisons against the algorithm's theoretical complexity.
  24.  
  25. Rather than list the times from a bunch of single runs, I accumulated the times from a bunch of runs and took the average.
  26.  
  27. Heapsort:
  28. N=10:       Average 86 over 10000 runs          NlogN = 23
  29. N=100:      Average 947 over 10000 runs         NlogN = 460
  30. N=1000:     Average 9584 over 10000 runs        NlogN = 6907
  31. N=10000:    Average 95989 over 1000 runs        NlogN = 92103
  32. N=100000:   Average 960028 over 1000 runs       NlogN = 1151292
  33. N=1000000:  Average 9600172 over 100 runs       NlogN = 13815510
  34. N=10000000: Average 96006971 over 10 runs       NlogN = 161180956
  35.  
  36. SelectionSort:
  37. N=10:       Average 81 over 1000 runs           N^2 = 100
  38. N=100:      Average 9801 over 1000 runs         N^2 = 10000
  39. N=1000:     Average 998001 over 1000 runs       N^2 = 1000000
  40. N=10000:    Average 99980001 over 1000 runs     N^2 = 100000000
  41. N=100000:   Average 9999800001 over 10 runs     N^2 = 10000000000
  42.  
  43. Bubblesort:
  44. N=10:       Average 99 over 100000 runs         N^2 = 100
  45. N=100:      Average 9999 over 10000 runs        N^2 = 10000
  46. N=1000:     Average 999999 over 1000 runs       N^2 = 1000000
  47. N=10000:    Average 99999999 over 100 runs      N^2 = 100000000
  48. N=100000:   Average 9999999999 over 10 runs     N^2 = 10000000000
  49.  
  50. Bogosort:
  51. N=2         Average 1 over 10000 runs           (N+1)! = 6
  52. N=3         Average 12 over 1000 runs           (N+1)! = 24
  53. N=4         Average 68 over 1000 runs           (N+1)! = 120
  54. N=5         Average 438 over 1000 runs          (N+1)! = 720
  55. N=6         Average 3400 over 1000 runs         (N+1)! = 5040
  56. N=7         Average 27415 over 1000 runs        (N+1)! = 40320
  57. N=8         Average 240061 over 1000 runs       (N+1)! = 362880
  58. N=9         Average 3247018 over 100 runs       (N+1)! = 3628800
  59. N=10        Average 24817337 over 100 runs      (N+1)! = 39916800
  60. N=11        Average 227220673 over 10 runs      (N+1)! = 479001600
  61. N=12        Average 629836304 over 2 runs       (N+1)! = 6227020800
  62.  
  63. I'll start with Heapsort. For low values of N, this implementation performed worse than the expected O(NlogN); this makes sense as the algorithm is technically O(N+NlogN). As N increased in size, however, the implementation quickly drew level and gradually outpaced the expected worst-case. Since Heapsort is NlogN in both the worst case and the average case, it makes sense that its performance remains near the worst case.
  64.  
  65. Next, Bubblesort and SelectionSort. Both had very predictable runtimes as N increased, sticking very close to N^2 with hardly any variance. Bubblesort is O(n) in the best case, but SelectionSort is O(n^2) in all cases. I would have expected this variance to show up somewhat in Bubblesort's trials, but it didn't.
  66.  
  67. Finally, Bogosort. Oh, Bogosort. The dyed-black sheep of the sorting algorithm family. Bogosort displayed the most variance out of any of the algorithms tested, which is hardly surprising given its non-deterministic nature. It also displayed the worst runtimes out of any of the algorithms tested, which is, again, hardly surprising. Surprisingly, though, it averaged a runtime better than the expected A((N+1)!) in almost every case, and I suspect that it would have continued to do so in the last case had I continued gathering data. My guess is that the figure of (N+1)! is accounting for another operation I wasn't measuring, most likely swaps.
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74. Sample runs follow:
  75.  
  76.  
  77. andi@ubuntu:~/Desktop/BinarySearch$ ./heapsort
  78. Converting list of size 31 to max heap
  79. Time:            7 ms
  80. Ops:           158
  81. N:              31
  82. NlogN:         106
  83.  
  84.  
  85. 5-Level Heap:
  86.                 99                
  87.         91                90        
  88.     82        91        48        79    
  89.   18    79    63    24    43    30    59    36  
  90.  02 01 00 73 23 32 05 02 21 36 19 21 55 29 13 01
  91.  
  92.  
  93.  
  94. andi@ubuntu:~/Desktop/BinarySearch$ ./heapsort
  95. Converting list of size 1000000 to max heap
  96. Time:       173912 ms
  97. Ops:       5887396
  98. N:         1000000
  99. NlogN:    13815510
  100.  
  101. Following a path from the root to a random leaf:
  102. arr[ 0]=99  Next: LEFT
  103. arr[ 1]=99  Next: LEFT
  104. arr[ 3]=99  Next: LEFT
  105. arr[ 7]=99  Next: RIGHT
  106. arr[16]=99  Next: RIGHT
  107. arr[34]=99  Next: RIGHT
  108. arr[70]=99  Next: LEFT
  109. arr[141]=99 Next: LEFT
  110. arr[283]=99 Next: RIGHT
  111. arr[568]=99 Next: RIGHT
  112. arr[1138]=99    Next: RIGHT
  113. arr[2278]=99    Next: RIGHT
  114. arr[4558]=99    Next: LEFT
  115. arr[9117]=97    Next: RIGHT
  116. arr[18236]=95   Next: RIGHT
  117. arr[36474]=94   Next: RIGHT
  118. arr[72950]=78   Next: RIGHT
  119. arr[145902]=66  Next: RIGHT
  120. arr[291806]=19  Next: RIGHT
  121. arr[583614]=25  Next: RIGHT
  122. No child found; done
  123.  
  124.  
  125.  
  126. andi@ubuntu:~/Desktop/BinarySearch$ ./heapsort
  127. Converting list of size 10000000 to max heap
  128. Time:      1689601 ms
  129. Ops:      58867754
  130. NlogN:   161180956
  131.  
  132. Following a path from the root to a random leaf:
  133. arr[ 0]=99  Next: LEFT
  134. arr[ 1]=99  Next: LEFT
  135. arr[ 3]=99  Next: LEFT
  136. arr[ 7]=99  Next: LEFT
  137. arr[15]=99  Next: LEFT
  138. arr[31]=99  Next: RIGHT
  139. arr[64]=99  Next: LEFT
  140. arr[129]=99 Next: RIGHT
  141. arr[260]=99 Next: RIGHT
  142. arr[522]=99 Next: RIGHT
  143. arr[1046]=99    Next: RIGHT
  144. arr[2094]=99    Next: LEFT
  145. arr[4189]=99    Next: RIGHT
  146. arr[8380]=99    Next: RIGHT
  147. arr[16762]=99   Next: RIGHT
  148. arr[33526]=99   Next: RIGHT
  149. arr[67054]=99   Next: LEFT
  150. arr[134109]=98  Next: LEFT
  151. arr[268219]=97  Next: RIGHT
  152. arr[536440]=94  Next: LEFT
  153. arr[1072881]=93 Next: RIGHT
  154. arr[2145764]=84 Next: RIGHT
  155. arr[4291530]=58 Next: LEFT
  156. arr[8583061]=57 Next: LEFT
  157. No child found; done
  158.  
  159.  
  160.  
  161. andi@ubuntu:~/Desktop/BinarySearch$ ./heapsort
  162. Converting list of size 10 to max heap
  163.  
  164. Time:            5 ms
  165. Ops:              56
  166. N:                10
  167. O(NlogN):         23
  168.  
  169.  
  170. 4-Level Heap:
  171.     93    
  172.   73    78  
  173.  73 68 13 42
  174.  42 34 53
  175.  
  176. Sorting list of size 10 with Selection Sort...
  177.  
  178. Time:              1 ms
  179. Ops:              36
  180. N:                10
  181. O(N^2):          100
  182.  
  183.  
  184. And finally, attempting to sort the list with Bogosort in
  185. 3
  186. 2
  187. 1
  188. Is THIS sorted?                     (3)  [ 13 53 73 78 42 42 34 73 93 68 ]
  189.         No.
  190. Is THIS sorted?                     (5)  [ 53 42 34 78 13 68 93 73 42 73 ]
  191.         Noo!
  192. Is THIS sorted?                     (5)  [ 42 42 78 68 13 93 73 53 73 34 ]
  193.         Nooo.
  194. Is THIS sorted?                     (5)  [ 34 68 93 73 13 53 42 78 73 42 ]
  195.         Noooo.
  196. Is THIS sorted?                     (5)  [ 42 68 13 93 78 53 42 73 73 34 ]
  197.         NOO.....
  198. Is THIS sorted?                     (3)  [ 42 34 93 42 53 68 73 73 78 13 ]
  199.         For the 6th time, no!
  200. Is THIS sorted?                     (4)  [ 42 34 73 73 78 93 53 13 68 42 ]
  201.         NOOOOO!!!!!!
  202. Is THIS sorted?                     (5)  [ 53 73 34 42 78 68 93 73 42 13 ]
  203.         NOOO!!
  204. Is THIS sorted?                     (4)  [ 53 34 13 42 78 93 73 73 42 68 ]
  205.         For the 9th time, no!
  206. Is THIS sorted?                     (4)  [ 73 42 93 53 73 13 68 78 34 42 ]
  207.         NOO.
  208. Is THIS sorted?                     (4)  [ 34 73 73 78 42 93 42 68 53 13 ]
  209.         NOOO!!!!
  210. Is THIS sorted?                     (4)  [ 42 53 93 42 34 13 73 68 73 78 ]
  211.         For the 12nd time, no!
  212. Is THIS sorted?                     (4)  [ 53 73 42 73 42 68 78 34 13 93 ]
  213.         NO.
  214. Is THIS sorted?                     (5)  [ 93 42 68 13 78 73 34 42 73 53 ]
  215.         NOO.
  216. Is THIS sorted?                     (5)  [ 93 13 73 42 68 53 34 73 42 78 ]
  217.         NOOOO!!!!!
  218. Is THIS sorted?                     (4)  [ 42 68 73 53 93 42 13 78 34 73 ]
  219.         For the 16th time, no!
  220. Is THIS sorted?                     (4)  [ 42 93 42 73 34 68 53 78 13 73 ]
  221.         NOO....
  222. Is THIS sorted?                     (6)  [ 34 73 42 13 78 73 53 93 68 42 ]
  223.         For the 18th time, no!
  224. Is THIS sorted?                     (4)  [ 42 13 78 34 73 73 53 68 93 42 ]
  225.         No..
  226. Is THIS sorted?                     (5)  [ 53 78 73 42 42 34 93 68 73 13 ]
  227.         NOO!!!!!!
  228. Is THIS sorted?                     (5)  [ 34 73 42 42 93 78 73 68 13 53 ]
  229.         For the 21st time, no!
  230. Is THIS sorted?                     (4)  [ 42 42 73 93 68 73 53 78 34 13 ]
  231.         For the 22nd time, no!
  232. Is THIS sorted?                     (6)  [ 68 53 13 73 42 34 78 93 73 42 ]
  233.         Noo!!
  234. Is THIS sorted?                     (4)  [ 73 42 13 34 78 68 73 93 42 53 ]
  235.         No!!!
  236. Is THIS sorted?                     (5)  [ 34 73 42 73 68 93 53 78 42 13 ]
  237.         Noo......
  238. Is THIS sorted?                     (5)  [ 73 53 42 42 93 78 13 34 73 68 ]
  239.         NOO!
  240. Is THIS sorted?                     (3)  [ 42 42 73 73 34 13 78 53 68 93 ]
  241.         For the 27th time, no!
  242. *
  243. Is THIS sorted?                     (6)  [ 68 34 93 73 73 42 13 78 53 42 ]
  244.         NOOOOO!!!!
  245. Is THIS sorted?                     (3)  [ 73 13 42 68 73 78 93 34 53 42 ]
  246.         Nooo!!!!
  247. Is THIS sorted?                     (5)  [ 73 42 42 34 73 68 13 93 53 78 ]
  248.         NOOO!
  249. Is THIS sorted?                     (4)  [ 34 42 13 78 53 73 93 68 42 73 ]
  250.         NOO!!
  251. Is THIS sorted?                     (5)  [ 73 78 13 53 73 68 42 93 42 34 ]
  252.         Nooo...
  253. Is THIS sorted?                     (5)  [ 93 68 73 42 53 13 73 42 34 78 ]
  254.         NO..
  255. Is THIS sorted?                     (3)  [ 42 34 93 42 78 13 53 68 73 73 ]
  256.         Nooo!
  257. Is THIS sorted?                     (4)  [ 73 13 53 34 42 93 68 73 78 42 ]
  258.         For the 175097th time, no!
  259. Is THIS sorted?                     (6)  [ 53 42 13 78 73 42 93 68 73 34 ]
  260.         No!
  261. Is THIS sorted?                     (4)  [ 42 68 53 73 73 34 78 42 13 93 ]
  262.         No!!!!!
  263. Is THIS sorted?                     (4)  [ 53 93 34 73 78 73 42 13 42 68 ]
  264.         NO!!
  265. Is THIS sorted?                     (4)  [ 68 53 34 73 73 93 42 42 78 13 ]
  266.         Noo!!!!
  267. Is THIS sorted?                     (2)  [ 13 53 68 42 73 73 34 42 78 93 ]
  268.         For the 175102nd time, no!
  269. Is THIS sorted?                     (4)  [ 68 34 73 78 93 42 73 42 53 13 ]
  270.         NOOO!!!!!
  271. Is THIS sorted?                     (4)  [ 42 73 93 68 34 13 53 73 42 78 ]
  272.         For the 175104th time, no!
  273. Is THIS sorted?                     (3)  [ 34 42 68 42 53 73 73 93 78 13 ]
  274.         For the 175105th time, no!
  275. Is THIS sorted?                     (4)  [ 42 73 13 42 93 34 78 73 53 68 ]
  276.         NO.....
  277. Is THIS sorted?                     (5)  [ 93 78 34 53 68 13 73 42 73 42 ]
  278.         NO!!!
  279. Is THIS sorted?                     (4)  [ 73 42 42 68 93 78 53 73 13 34 ]
  280.         For the 175108th time, no!
  281. Is THIS sorted?                     (3)  [ 42 68 78 34 13 73 93 42 53 73 ]
  282.         Noo....
  283. Is THIS sorted?                     (4)  [ 73 13 34 68 78 73 42 42 93 53 ]
  284.         NOOOO....
  285. Is THIS sorted?                     (4)  [ 42 68 13 53 73 42 93 73 78 34 ]
  286.         Nooo!!!
  287. Is THIS sorted?                     (4)  [ 34 93 42 73 42 13 78 53 68 73 ]
  288.         For the 175112nd time, no!
  289. Is THIS sorted?                     (2)  [ 34 42 68 93 13 53 73 73 42 78 ]
  290.         For the 175113th time, no!
  291. Is THIS sorted?                     (5)  [ 73 68 53 42 13 34 42 78 93 73 ]
  292.         Noo!!!!
  293. Is THIS sorted?                     (5)  [ 78 42 13 42 93 73 73 68 34 53 ]
  294.         Nooo!!!
  295. Is THIS sorted?                     (5)  [ 73 34 78 73 53 13 42 93 42 68 ]
  296.         For the 175116th time, no!
  297. Is THIS sorted?                     (5)  [ 93 78 73 34 53 13 73 42 42 68 ]
  298.         NO!!!!
  299. Is THIS sorted?                     (4)  [ 73 78 73 53 68 13 34 42 93 42 ]
  300.         NOO!!!
  301. Is THIS sorted?                     (5)  [ 42 34 68 13 73 73 93 78 53 42 ]
  302.         For the 175119th time, no!
  303. Is THIS sorted?                     (5)  [ 73 78 42 73 42 68 53 13 93 34 ]
  304.         NO!
  305. Is THIS sorted?                     (6)  [ 42 73 34 68 53 93 78 73 42 13 ]
  306.         NOO!!!
  307. Is THIS sorted?                     (4)  [ 42 34 73 73 13 68 53 78 42 93 ]
  308.         For the 175122nd time, no!
  309. Is THIS sorted?                     (0)  [ 13 34 42 42 53 68 73 73 78 93 ]
  310.         NOOO!!!
  311.         Wait, yes! Haha, it's finally over!
  312. Yaaaaay!
  313.  
  314.  
  315. Time:      2257139 ms
  316. Ops:         1576107
  317. N:                10
  318. O((N+1)!):    362880
  319.  
  320.  
  321.  
  322.  
  323.  
  324.  
  325.  
  326. */
  327. //-----------------------------------------------------------------------------------------
  328. //Code follows
  329. //-----------------------------------------------------------------------------------------
  330.  
  331.  
  332.  
  333. #include <time.h>
  334. #include <stdlib.h>
  335. #include <stdio.h>
  336. #include <math.h> //compile with -lm
  337. #include <unistd.h>
  338.  
  339. //Change N here and recompile, because I was too lazy to make it take input
  340. #define SIZE 1000
  341. //Which algorithm to use
  342. #define SORT heapSort
  343. //Number of trials
  344. #define TESTS 0
  345. //Max value (+1) for random numbers
  346. #define RSIZE 100
  347.  
  348.  
  349.  
  350.  
  351.  
  352.  
  353. //Swap two elements in the list
  354. static inline void swap(int arr[],int a,int b) {
  355.     int temp = arr[a];
  356.     arr[a] = arr[b];
  357.     arr[b] = temp;
  358.     return;
  359. }
  360.  
  361.  
  362.  
  363. //Generate random unsorted list
  364. //Call srand(time(NULL)) first, exactly once
  365. int * makeList(int size) {
  366.     static int list [SIZE];
  367.     for(int i=0; i<size; i++) {
  368.         list[i] = rand()%RSIZE;
  369.     }
  370.     return list;
  371. }
  372.  
  373. int ops = 0; //count basic operation (comparisons)
  374. #define COUNT ++ops;
  375. #define COUNTS(n) ops+=n;
  376.  
  377.  
  378.  
  379.  
  380.  
  381. //---------------------------------------------------------------------------
  382. //Bubblesort and SelectionSort
  383.  
  384.  
  385.  
  386. //Sort list using BubbleSort - O(n^2)
  387. int * bubSort(int arr[]) {
  388.     int max = SIZE-1;
  389.     for(int i = 0; i < max; i++) {
  390.                                                                     COUNT
  391.         for(int j = 0; j < max-i; j++) {
  392.                                                                     COUNTS(2)
  393.             if(arr[j] > arr[j+1]) {
  394.                 swap(arr,j,j+1);
  395.             }
  396.         }
  397.     }
  398.     return arr;
  399. }
  400.  
  401. //Sort list using Selection Sort - O(n^2)
  402. int * selectionSort(int arr[]) {
  403.     int b = SIZE-1; //last index
  404.     int minI;       //index of smallest value in unsorted portion of list
  405.     for(int a = 0; a < b; a++) {
  406.                                                                     COUNT
  407.         minI = a;
  408.         for(int i = a+1; i < b; i++) {
  409.                                                                     COUNTS(2)
  410.             if(arr[i] < arr[minI]) {
  411.                 minI = i;
  412.             }
  413.         }
  414.         swap(arr,a,minI);
  415.         //print values as they're put into sorted part of list
  416.         //because with that runtime I'd like some feedback
  417.         //printf("%d ",arr[a]);
  418.     }
  419.     return arr;
  420. }
  421.  
  422.  
  423.  
  424.  
  425.  
  426.  
  427. //---------------------------------------------------------------------------
  428. //HeapSort
  429.  
  430.  
  431.  
  432. //Helper definitions for heap
  433. #define Parent(i) floor((i-1)/2)
  434. #define LChild(i) (2*i+1)
  435. #define RChild(i) (2*i+2)
  436.  
  437.  
  438.  
  439.  
  440.  
  441. int * heapSort(int[]);
  442. void makeHeap(int[]);
  443. void siftDown(int[],int,int);
  444. void siftUp(int[],int,int);
  445. void printHeap(int[]);
  446. void followDown(int[]);
  447.  
  448.  
  449. //Sort list using HeapSort - O(nlogn)
  450. int * heapSort(int arr[]) {
  451.     int a = 0;      //first index
  452.     int b = SIZE-1; //last considered index
  453.     makeHeap(arr);
  454.     while(b > a) {
  455.                                                                     COUNTS(2)
  456.         if(arr[b] > arr[a]) {
  457.             swap(arr,b,a);
  458.         }
  459.         siftUp(arr, a, b);  //repair heap after swap
  460.         --b;                //reduce size of list considered
  461.     }
  462.     return arr;
  463. }
  464.  
  465.  
  466. //Convert array to max heap - O(n)
  467. //Largest element at root
  468. //Each child is less than or equal to its parent
  469. void makeHeap(int arr[]) {
  470.     int i = Parent(SIZE); //last nonleaf node
  471.     while(i >= 0) {
  472.                                                                     COUNT
  473.         siftDown(arr,i,SIZE-1); //(arr,i,SIZE-1);
  474.         i--;
  475.     }
  476.     return;
  477. }
  478.  
  479.  
  480.  
  481. //siftUp and siftDown are two implementations
  482. //that are supposed to do basically the same thing.
  483. //However, I've ended up using one in makeHeap and the other in heapSort
  484. //and am too tired of fiddling with it to try to figure out why.
  485.  
  486. //Repair heap after doing a swap
  487. void siftUp(int arr[], int start, int end) {
  488.     int child = end; int parent;
  489.     while(child > start) {
  490.         parent = Parent(child);
  491.                                                                     COUNTS(2)
  492.         if(arr[parent] < arr[child]) { //out of max-heap order
  493.             swap(arr,parent,child);
  494.             child = parent; //continue sifting up parent
  495.         } else {
  496.             return;
  497.         }
  498.     }
  499. }
  500.  
  501.  
  502. //Move first element to its proper position - O(logn), called O(n) times - total O(nlogn)
  503. void siftDown(int arr[], int start, int end) {
  504.     int root = start;
  505.     int child; int toswap;
  506.     while(LChild(root) <= end) {
  507.                                                                     COUNTS(5)
  508.         child = LChild(root);
  509.         toswap = root;
  510.         if(arr[toswap] < arr[child]) {
  511.             toswap = child;
  512.         }
  513.         //If there is a right child and it is greater
  514.         if(child+1 <= end && arr[toswap] < arr[child+1]) {
  515.             toswap = child+1;
  516.         }
  517.         if(toswap == root) {
  518.             return;
  519.         } else {
  520.             swap(arr,start,toswap);
  521.         }
  522.     }
  523. }
  524.  
  525.  
  526.  
  527.  
  528.  
  529. //Print heap - for debugging
  530. //I probably spent as much time trying to get this to print nicely
  531. //as I did getting the algorithm to actually work
  532. //Looks best with 31 elements
  533. void printHeap(int arr[]) {
  534.     int height = floor(log(SIZE+1));
  535.     int col_width = pow(2,height+1) * (height-1);
  536.     printf("\n%d-Level Heap:\n",height+2);
  537.     int n = 2; //end of each level
  538.     for(int i=0; i<SIZE; i++) {
  539.         if(i == n-1) {
  540.             n*=2;
  541.             col_width /= 2;
  542.             printf("\n");
  543.         }
  544.         printf("%*s",col_width/2," ");
  545.         printf("%0*d", 2,arr[i] );
  546.         if(col_width/2-1>0){ printf("%*s",col_width/2," "); }
  547.     }
  548.     printf("\n");
  549. }
  550.  
  551. //Follow a random path down child branches - for debugging
  552. //Helps checking that each child is less than its parent for large N
  553. void followDown(int arr[]) {
  554.     int node = 0;
  555.     int next;
  556.     const char* dirStrings[] = {"LEFT","RIGHT"};
  557.     printf("Following a path from the root to a random leaf:\n");
  558.     while(node < SIZE) {
  559.         printf("arr[%*d]=%*d",2,node,2,arr[node]);
  560.         next = rand() % 2; //0 or 1
  561.         printf("\tNext: %s\n", dirStrings[next]);
  562.         node = 2*node + 1 + next;
  563.     }
  564.     printf("No child found; done\n");
  565.     return;
  566. }
  567.  
  568.  
  569.  
  570.  
  571. //----------------------------------------------------------------------
  572. //Bogosort, just because
  573.  
  574.  
  575. int * bogoSort(int[]);
  576. void shuffle(int[]);
  577. int test(int[]);
  578. void printarr(int[]);
  579. void arewethereyet(int[],int,int);
  580.  
  581. int * bogoSort(int arr[]) {
  582.     int shuffles = 0; int unsorted = 1;
  583.     while(unsorted) {
  584.         shuffle(arr);
  585.         unsorted = test(arr);
  586.         //arewethereyet(arr,++shuffles,unsorted);
  587.     }
  588.     return arr;
  589. }
  590.  
  591. //Sort the elements of the list in a random order
  592. void shuffle(int arr[]) {
  593.     for(int i = 0; i < SIZE; i = i + 1) {
  594.         swap(arr, i, i+( rand()%(SIZE-i) ) );
  595.     }
  596. }
  597.  
  598. //Check if the array is unsorted
  599. int test(int arr[]) {
  600.     int wrong = 0;  //number of pairs that are out of order
  601.     for(int i = 0; i < SIZE-1; i++) {
  602.                                                                     COUNT
  603.         if(arr[i] > arr[i+1]) {
  604.             wrong += 1;
  605.         }
  606.     }
  607.     return wrong;
  608. }
  609.  
  610. //print array
  611. void printarr(int arr[]) {
  612.     printf("[ ");
  613.     for(int i = 0; i < SIZE; i++) {
  614.         printf("%d ",arr[i]);
  615.     }
  616.     printf("]");
  617. }
  618.  
  619.  
  620. //Let's be honest, the array's not gonna end up sorted for N much larger than 10 or so.
  621. //So the real point of this algorithm... is the journey.
  622. void arewethereyet(int arr[],int shuffles,int unsorted) {
  623.     printf("Is THIS sorted?\t\t\t\t\t\t(%d)  ",unsorted);
  624.     printarr(arr); printf("\n");
  625.     if(shuffles < 5) {
  626.         printf("\t\tN");
  627.         for(int i = 0; i <= shuffles-1; i = i + 1) {
  628.             printf("o");
  629.         }
  630.         printf("%c", (char[]){"..!"}[rand()%3] );
  631.     }
  632.     else if(shuffles%(rand()%10+1) == 0) {
  633.         printf("\t\tFor the %d%c%c time, no!", shuffles,
  634.             (char[]){"tsnttttttt"}[shuffles%10], (char[]){"htdhhhhhhh"}[shuffles%10]  );
  635.     }
  636.     else {
  637.         int caps = rand()%3;
  638.         printf("\t\tN%c",(char[]){"OOo"}[caps]);
  639.         for(int i = 0; i < rand()%5; i = i + 1) {
  640.             printf("%c",(char[]){"OOo"}[caps]);
  641.         }
  642.         int punct = rand()%3;
  643.         for(int i = 0; i <= rand()%8; i = i + 1) {
  644.             printf("%c",(char[]){".!!"}[punct]);
  645.         }
  646.     }
  647.     printf("\n");
  648.     if(!unsorted) {
  649.         printf("\t\tWait, yes! Haha, it's finally over!\n");
  650.         printf("Yaaaaay!\n");
  651.     }
  652.     return;
  653. }
  654. //-----------------------------------------------------------------------
  655.  
  656.  
  657.  
  658.  
  659.  
  660.  
  661.  
  662. int main() {
  663.  
  664.     int * arr = makeList(SIZE);
  665.     srand(time(NULL));
  666.    
  667.    
  668.     //Code used to generate averages
  669.     if(TESTS > 0) {
  670.         int total = 0;
  671.         for(int i = 0; i < TESTS; i++) {
  672.             ops = 0;
  673.             SORT(arr);
  674.             printf("%d, ",ops);
  675.             total += ops;
  676.             arr = makeList(SIZE);
  677.             //shuffle(arr);
  678.         }
  679.         printf("Average %d over %d runs\n",total/TESTS, TESTS);
  680.         return 0;
  681.     }
  682.  
  683.  
  684.  
  685.    
  686.     printf("Converting list of size %d to max heap",SIZE);
  687.    
  688.     int start = clock();
  689.     heapSort(arr);
  690.     int end = clock();
  691.    
  692.     printf("%-*s%*d ms\n", 10,"\n\nTime:", 10,end-start);
  693.     printf("%-*s%*d\n", 10,"Ops:", 10,ops);
  694.     printf("%-*s%*d\n", 10,"N: ", 10,SIZE);
  695.     printf("%-*s%*d\n\n", 10,"O(NlogN): ", 10,(int)(SIZE*log(SIZE)));
  696.    
  697.     if(SIZE < 64) {
  698.         printHeap(arr);
  699.     } else {
  700.         followDown(arr);
  701.     }
  702.    
  703.     shuffle(arr);
  704.    
  705.  
  706.     printf("\nSorting list of size %d with Selection Sort...\n\n",SIZE);
  707.     ops = 0;
  708.     start = clock();
  709.     selectionSort(arr);
  710.     end = clock();
  711.    
  712.     printf("%-*s%*d ms\n", 10,"Time:", 10,end-start);
  713.     printf("%-*s%*d\n", 10,"Ops:", 10,ops);
  714.     printf("%-*s%*d\n", 10,"N: ", 10,SIZE);
  715.     printf("%-*s%*d\n\n", 10,"O(N^2): ", 10,SIZE*SIZE);
  716.    
  717.     if(SIZE > 10) {
  718.         return 0;
  719.     }
  720.    
  721.     printf("\nAnd finally, attempting to sort the list with Bogosort in \n3\n");
  722.     sleep(1);
  723.     printf("2\n");
  724.     sleep(1);
  725.     printf("1\n");
  726.     sleep(1);
  727.    
  728.     ops = 0;
  729.     start = clock();
  730.     bogoSort(arr);
  731.     end = clock();
  732.    
  733.     printf("%-*s%*d ms\n", 10,"\n\nTime:", 10,end-start);
  734.     printf("%-*s%*d\n", 10,"Ops:", 10,ops);
  735.     printf("%-*s%*d\n", 10,"N: ", 10,SIZE);
  736.     printf("%-*s", 10,"O((N+1)!):");
  737.     int fact = 1; for(int i=1; i<SIZE; i++) { fact *= i; }
  738.     printf("%*d\n",10,fact);
  739.    
  740.  
  741.     return 0;
  742. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!