Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Andi ******
- I implemented HeapSort and SelectionSort, and reused my earlier implementation of BubbleSort. I also, for some reason, implemented Bogosort.
- Here's each algorithm's expected time complexity:
- HeapSort O(NlogN)
- SelectionSort O(N^2)
- BubbleSort O(N^2)
- BogoSort A((N+1)!) (worst-case is unbounded)
- And each algorithm's auxiliary space complexity:
- HeapSort O(1)
- SelectionSort O(1)
- BubbleSort O(1)
- BogoSort O(1)
- So all four algorithms are in-place.
- That's one area Bogosort isn't nearly bad enough, at least.
- 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.
- Rather than list the times from a bunch of single runs, I accumulated the times from a bunch of runs and took the average.
- Heapsort:
- N=10: Average 86 over 10000 runs NlogN = 23
- N=100: Average 947 over 10000 runs NlogN = 460
- N=1000: Average 9584 over 10000 runs NlogN = 6907
- N=10000: Average 95989 over 1000 runs NlogN = 92103
- N=100000: Average 960028 over 1000 runs NlogN = 1151292
- N=1000000: Average 9600172 over 100 runs NlogN = 13815510
- N=10000000: Average 96006971 over 10 runs NlogN = 161180956
- SelectionSort:
- N=10: Average 81 over 1000 runs N^2 = 100
- N=100: Average 9801 over 1000 runs N^2 = 10000
- N=1000: Average 998001 over 1000 runs N^2 = 1000000
- N=10000: Average 99980001 over 1000 runs N^2 = 100000000
- N=100000: Average 9999800001 over 10 runs N^2 = 10000000000
- Bubblesort:
- N=10: Average 99 over 100000 runs N^2 = 100
- N=100: Average 9999 over 10000 runs N^2 = 10000
- N=1000: Average 999999 over 1000 runs N^2 = 1000000
- N=10000: Average 99999999 over 100 runs N^2 = 100000000
- N=100000: Average 9999999999 over 10 runs N^2 = 10000000000
- Bogosort:
- N=2 Average 1 over 10000 runs (N+1)! = 6
- N=3 Average 12 over 1000 runs (N+1)! = 24
- N=4 Average 68 over 1000 runs (N+1)! = 120
- N=5 Average 438 over 1000 runs (N+1)! = 720
- N=6 Average 3400 over 1000 runs (N+1)! = 5040
- N=7 Average 27415 over 1000 runs (N+1)! = 40320
- N=8 Average 240061 over 1000 runs (N+1)! = 362880
- N=9 Average 3247018 over 100 runs (N+1)! = 3628800
- N=10 Average 24817337 over 100 runs (N+1)! = 39916800
- N=11 Average 227220673 over 10 runs (N+1)! = 479001600
- N=12 Average 629836304 over 2 runs (N+1)! = 6227020800
- 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.
- 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.
- 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.
- Sample runs follow:
- andi@ubuntu:~/Desktop/BinarySearch$ ./heapsort
- Converting list of size 31 to max heap
- Time: 7 ms
- Ops: 158
- N: 31
- NlogN: 106
- 5-Level Heap:
- 99
- 91 90
- 82 91 48 79
- 18 79 63 24 43 30 59 36
- 02 01 00 73 23 32 05 02 21 36 19 21 55 29 13 01
- andi@ubuntu:~/Desktop/BinarySearch$ ./heapsort
- Converting list of size 1000000 to max heap
- Time: 173912 ms
- Ops: 5887396
- N: 1000000
- NlogN: 13815510
- Following a path from the root to a random leaf:
- arr[ 0]=99 Next: LEFT
- arr[ 1]=99 Next: LEFT
- arr[ 3]=99 Next: LEFT
- arr[ 7]=99 Next: RIGHT
- arr[16]=99 Next: RIGHT
- arr[34]=99 Next: RIGHT
- arr[70]=99 Next: LEFT
- arr[141]=99 Next: LEFT
- arr[283]=99 Next: RIGHT
- arr[568]=99 Next: RIGHT
- arr[1138]=99 Next: RIGHT
- arr[2278]=99 Next: RIGHT
- arr[4558]=99 Next: LEFT
- arr[9117]=97 Next: RIGHT
- arr[18236]=95 Next: RIGHT
- arr[36474]=94 Next: RIGHT
- arr[72950]=78 Next: RIGHT
- arr[145902]=66 Next: RIGHT
- arr[291806]=19 Next: RIGHT
- arr[583614]=25 Next: RIGHT
- No child found; done
- andi@ubuntu:~/Desktop/BinarySearch$ ./heapsort
- Converting list of size 10000000 to max heap
- Time: 1689601 ms
- Ops: 58867754
- NlogN: 161180956
- Following a path from the root to a random leaf:
- arr[ 0]=99 Next: LEFT
- arr[ 1]=99 Next: LEFT
- arr[ 3]=99 Next: LEFT
- arr[ 7]=99 Next: LEFT
- arr[15]=99 Next: LEFT
- arr[31]=99 Next: RIGHT
- arr[64]=99 Next: LEFT
- arr[129]=99 Next: RIGHT
- arr[260]=99 Next: RIGHT
- arr[522]=99 Next: RIGHT
- arr[1046]=99 Next: RIGHT
- arr[2094]=99 Next: LEFT
- arr[4189]=99 Next: RIGHT
- arr[8380]=99 Next: RIGHT
- arr[16762]=99 Next: RIGHT
- arr[33526]=99 Next: RIGHT
- arr[67054]=99 Next: LEFT
- arr[134109]=98 Next: LEFT
- arr[268219]=97 Next: RIGHT
- arr[536440]=94 Next: LEFT
- arr[1072881]=93 Next: RIGHT
- arr[2145764]=84 Next: RIGHT
- arr[4291530]=58 Next: LEFT
- arr[8583061]=57 Next: LEFT
- No child found; done
- andi@ubuntu:~/Desktop/BinarySearch$ ./heapsort
- Converting list of size 10 to max heap
- Time: 5 ms
- Ops: 56
- N: 10
- O(NlogN): 23
- 4-Level Heap:
- 93
- 73 78
- 73 68 13 42
- 42 34 53
- Sorting list of size 10 with Selection Sort...
- Time: 1 ms
- Ops: 36
- N: 10
- O(N^2): 100
- And finally, attempting to sort the list with Bogosort in
- 3
- 2
- 1
- Is THIS sorted? (3) [ 13 53 73 78 42 42 34 73 93 68 ]
- No.
- Is THIS sorted? (5) [ 53 42 34 78 13 68 93 73 42 73 ]
- Noo!
- Is THIS sorted? (5) [ 42 42 78 68 13 93 73 53 73 34 ]
- Nooo.
- Is THIS sorted? (5) [ 34 68 93 73 13 53 42 78 73 42 ]
- Noooo.
- Is THIS sorted? (5) [ 42 68 13 93 78 53 42 73 73 34 ]
- NOO.....
- Is THIS sorted? (3) [ 42 34 93 42 53 68 73 73 78 13 ]
- For the 6th time, no!
- Is THIS sorted? (4) [ 42 34 73 73 78 93 53 13 68 42 ]
- NOOOOO!!!!!!
- Is THIS sorted? (5) [ 53 73 34 42 78 68 93 73 42 13 ]
- NOOO!!
- Is THIS sorted? (4) [ 53 34 13 42 78 93 73 73 42 68 ]
- For the 9th time, no!
- Is THIS sorted? (4) [ 73 42 93 53 73 13 68 78 34 42 ]
- NOO.
- Is THIS sorted? (4) [ 34 73 73 78 42 93 42 68 53 13 ]
- NOOO!!!!
- Is THIS sorted? (4) [ 42 53 93 42 34 13 73 68 73 78 ]
- For the 12nd time, no!
- Is THIS sorted? (4) [ 53 73 42 73 42 68 78 34 13 93 ]
- NO.
- Is THIS sorted? (5) [ 93 42 68 13 78 73 34 42 73 53 ]
- NOO.
- Is THIS sorted? (5) [ 93 13 73 42 68 53 34 73 42 78 ]
- NOOOO!!!!!
- Is THIS sorted? (4) [ 42 68 73 53 93 42 13 78 34 73 ]
- For the 16th time, no!
- Is THIS sorted? (4) [ 42 93 42 73 34 68 53 78 13 73 ]
- NOO....
- Is THIS sorted? (6) [ 34 73 42 13 78 73 53 93 68 42 ]
- For the 18th time, no!
- Is THIS sorted? (4) [ 42 13 78 34 73 73 53 68 93 42 ]
- No..
- Is THIS sorted? (5) [ 53 78 73 42 42 34 93 68 73 13 ]
- NOO!!!!!!
- Is THIS sorted? (5) [ 34 73 42 42 93 78 73 68 13 53 ]
- For the 21st time, no!
- Is THIS sorted? (4) [ 42 42 73 93 68 73 53 78 34 13 ]
- For the 22nd time, no!
- Is THIS sorted? (6) [ 68 53 13 73 42 34 78 93 73 42 ]
- Noo!!
- Is THIS sorted? (4) [ 73 42 13 34 78 68 73 93 42 53 ]
- No!!!
- Is THIS sorted? (5) [ 34 73 42 73 68 93 53 78 42 13 ]
- Noo......
- Is THIS sorted? (5) [ 73 53 42 42 93 78 13 34 73 68 ]
- NOO!
- Is THIS sorted? (3) [ 42 42 73 73 34 13 78 53 68 93 ]
- For the 27th time, no!
- *
- Is THIS sorted? (6) [ 68 34 93 73 73 42 13 78 53 42 ]
- NOOOOO!!!!
- Is THIS sorted? (3) [ 73 13 42 68 73 78 93 34 53 42 ]
- Nooo!!!!
- Is THIS sorted? (5) [ 73 42 42 34 73 68 13 93 53 78 ]
- NOOO!
- Is THIS sorted? (4) [ 34 42 13 78 53 73 93 68 42 73 ]
- NOO!!
- Is THIS sorted? (5) [ 73 78 13 53 73 68 42 93 42 34 ]
- Nooo...
- Is THIS sorted? (5) [ 93 68 73 42 53 13 73 42 34 78 ]
- NO..
- Is THIS sorted? (3) [ 42 34 93 42 78 13 53 68 73 73 ]
- Nooo!
- Is THIS sorted? (4) [ 73 13 53 34 42 93 68 73 78 42 ]
- For the 175097th time, no!
- Is THIS sorted? (6) [ 53 42 13 78 73 42 93 68 73 34 ]
- No!
- Is THIS sorted? (4) [ 42 68 53 73 73 34 78 42 13 93 ]
- No!!!!!
- Is THIS sorted? (4) [ 53 93 34 73 78 73 42 13 42 68 ]
- NO!!
- Is THIS sorted? (4) [ 68 53 34 73 73 93 42 42 78 13 ]
- Noo!!!!
- Is THIS sorted? (2) [ 13 53 68 42 73 73 34 42 78 93 ]
- For the 175102nd time, no!
- Is THIS sorted? (4) [ 68 34 73 78 93 42 73 42 53 13 ]
- NOOO!!!!!
- Is THIS sorted? (4) [ 42 73 93 68 34 13 53 73 42 78 ]
- For the 175104th time, no!
- Is THIS sorted? (3) [ 34 42 68 42 53 73 73 93 78 13 ]
- For the 175105th time, no!
- Is THIS sorted? (4) [ 42 73 13 42 93 34 78 73 53 68 ]
- NO.....
- Is THIS sorted? (5) [ 93 78 34 53 68 13 73 42 73 42 ]
- NO!!!
- Is THIS sorted? (4) [ 73 42 42 68 93 78 53 73 13 34 ]
- For the 175108th time, no!
- Is THIS sorted? (3) [ 42 68 78 34 13 73 93 42 53 73 ]
- Noo....
- Is THIS sorted? (4) [ 73 13 34 68 78 73 42 42 93 53 ]
- NOOOO....
- Is THIS sorted? (4) [ 42 68 13 53 73 42 93 73 78 34 ]
- Nooo!!!
- Is THIS sorted? (4) [ 34 93 42 73 42 13 78 53 68 73 ]
- For the 175112nd time, no!
- Is THIS sorted? (2) [ 34 42 68 93 13 53 73 73 42 78 ]
- For the 175113th time, no!
- Is THIS sorted? (5) [ 73 68 53 42 13 34 42 78 93 73 ]
- Noo!!!!
- Is THIS sorted? (5) [ 78 42 13 42 93 73 73 68 34 53 ]
- Nooo!!!
- Is THIS sorted? (5) [ 73 34 78 73 53 13 42 93 42 68 ]
- For the 175116th time, no!
- Is THIS sorted? (5) [ 93 78 73 34 53 13 73 42 42 68 ]
- NO!!!!
- Is THIS sorted? (4) [ 73 78 73 53 68 13 34 42 93 42 ]
- NOO!!!
- Is THIS sorted? (5) [ 42 34 68 13 73 73 93 78 53 42 ]
- For the 175119th time, no!
- Is THIS sorted? (5) [ 73 78 42 73 42 68 53 13 93 34 ]
- NO!
- Is THIS sorted? (6) [ 42 73 34 68 53 93 78 73 42 13 ]
- NOO!!!
- Is THIS sorted? (4) [ 42 34 73 73 13 68 53 78 42 93 ]
- For the 175122nd time, no!
- Is THIS sorted? (0) [ 13 34 42 42 53 68 73 73 78 93 ]
- NOOO!!!
- Wait, yes! Haha, it's finally over!
- Yaaaaay!
- Time: 2257139 ms
- Ops: 1576107
- N: 10
- O((N+1)!): 362880
- */
- //-----------------------------------------------------------------------------------------
- //Code follows
- //-----------------------------------------------------------------------------------------
- #include <time.h>
- #include <stdlib.h>
- #include <stdio.h>
- #include <math.h> //compile with -lm
- #include <unistd.h>
- //Change N here and recompile, because I was too lazy to make it take input
- #define SIZE 1000
- //Which algorithm to use
- #define SORT heapSort
- //Number of trials
- #define TESTS 0
- //Max value (+1) for random numbers
- #define RSIZE 100
- //Swap two elements in the list
- static inline void swap(int arr[],int a,int b) {
- int temp = arr[a];
- arr[a] = arr[b];
- arr[b] = temp;
- return;
- }
- //Generate random unsorted list
- //Call srand(time(NULL)) first, exactly once
- int * makeList(int size) {
- static int list [SIZE];
- for(int i=0; i<size; i++) {
- list[i] = rand()%RSIZE;
- }
- return list;
- }
- int ops = 0; //count basic operation (comparisons)
- #define COUNT ++ops;
- #define COUNTS(n) ops+=n;
- //---------------------------------------------------------------------------
- //Bubblesort and SelectionSort
- //Sort list using BubbleSort - O(n^2)
- int * bubSort(int arr[]) {
- int max = SIZE-1;
- for(int i = 0; i < max; i++) {
- COUNT
- for(int j = 0; j < max-i; j++) {
- COUNTS(2)
- if(arr[j] > arr[j+1]) {
- swap(arr,j,j+1);
- }
- }
- }
- return arr;
- }
- //Sort list using Selection Sort - O(n^2)
- int * selectionSort(int arr[]) {
- int b = SIZE-1; //last index
- int minI; //index of smallest value in unsorted portion of list
- for(int a = 0; a < b; a++) {
- COUNT
- minI = a;
- for(int i = a+1; i < b; i++) {
- COUNTS(2)
- if(arr[i] < arr[minI]) {
- minI = i;
- }
- }
- swap(arr,a,minI);
- //print values as they're put into sorted part of list
- //because with that runtime I'd like some feedback
- //printf("%d ",arr[a]);
- }
- return arr;
- }
- //---------------------------------------------------------------------------
- //HeapSort
- //Helper definitions for heap
- #define Parent(i) floor((i-1)/2)
- #define LChild(i) (2*i+1)
- #define RChild(i) (2*i+2)
- int * heapSort(int[]);
- void makeHeap(int[]);
- void siftDown(int[],int,int);
- void siftUp(int[],int,int);
- void printHeap(int[]);
- void followDown(int[]);
- //Sort list using HeapSort - O(nlogn)
- int * heapSort(int arr[]) {
- int a = 0; //first index
- int b = SIZE-1; //last considered index
- makeHeap(arr);
- while(b > a) {
- COUNTS(2)
- if(arr[b] > arr[a]) {
- swap(arr,b,a);
- }
- siftUp(arr, a, b); //repair heap after swap
- --b; //reduce size of list considered
- }
- return arr;
- }
- //Convert array to max heap - O(n)
- //Largest element at root
- //Each child is less than or equal to its parent
- void makeHeap(int arr[]) {
- int i = Parent(SIZE); //last nonleaf node
- while(i >= 0) {
- COUNT
- siftDown(arr,i,SIZE-1); //(arr,i,SIZE-1);
- i--;
- }
- return;
- }
- //siftUp and siftDown are two implementations
- //that are supposed to do basically the same thing.
- //However, I've ended up using one in makeHeap and the other in heapSort
- //and am too tired of fiddling with it to try to figure out why.
- //Repair heap after doing a swap
- void siftUp(int arr[], int start, int end) {
- int child = end; int parent;
- while(child > start) {
- parent = Parent(child);
- COUNTS(2)
- if(arr[parent] < arr[child]) { //out of max-heap order
- swap(arr,parent,child);
- child = parent; //continue sifting up parent
- } else {
- return;
- }
- }
- }
- //Move first element to its proper position - O(logn), called O(n) times - total O(nlogn)
- void siftDown(int arr[], int start, int end) {
- int root = start;
- int child; int toswap;
- while(LChild(root) <= end) {
- COUNTS(5)
- child = LChild(root);
- toswap = root;
- if(arr[toswap] < arr[child]) {
- toswap = child;
- }
- //If there is a right child and it is greater
- if(child+1 <= end && arr[toswap] < arr[child+1]) {
- toswap = child+1;
- }
- if(toswap == root) {
- return;
- } else {
- swap(arr,start,toswap);
- }
- }
- }
- //Print heap - for debugging
- //I probably spent as much time trying to get this to print nicely
- //as I did getting the algorithm to actually work
- //Looks best with 31 elements
- void printHeap(int arr[]) {
- int height = floor(log(SIZE+1));
- int col_width = pow(2,height+1) * (height-1);
- printf("\n%d-Level Heap:\n",height+2);
- int n = 2; //end of each level
- for(int i=0; i<SIZE; i++) {
- if(i == n-1) {
- n*=2;
- col_width /= 2;
- printf("\n");
- }
- printf("%*s",col_width/2," ");
- printf("%0*d", 2,arr[i] );
- if(col_width/2-1>0){ printf("%*s",col_width/2," "); }
- }
- printf("\n");
- }
- //Follow a random path down child branches - for debugging
- //Helps checking that each child is less than its parent for large N
- void followDown(int arr[]) {
- int node = 0;
- int next;
- const char* dirStrings[] = {"LEFT","RIGHT"};
- printf("Following a path from the root to a random leaf:\n");
- while(node < SIZE) {
- printf("arr[%*d]=%*d",2,node,2,arr[node]);
- next = rand() % 2; //0 or 1
- printf("\tNext: %s\n", dirStrings[next]);
- node = 2*node + 1 + next;
- }
- printf("No child found; done\n");
- return;
- }
- //----------------------------------------------------------------------
- //Bogosort, just because
- int * bogoSort(int[]);
- void shuffle(int[]);
- int test(int[]);
- void printarr(int[]);
- void arewethereyet(int[],int,int);
- int * bogoSort(int arr[]) {
- int shuffles = 0; int unsorted = 1;
- while(unsorted) {
- shuffle(arr);
- unsorted = test(arr);
- //arewethereyet(arr,++shuffles,unsorted);
- }
- return arr;
- }
- //Sort the elements of the list in a random order
- void shuffle(int arr[]) {
- for(int i = 0; i < SIZE; i = i + 1) {
- swap(arr, i, i+( rand()%(SIZE-i) ) );
- }
- }
- //Check if the array is unsorted
- int test(int arr[]) {
- int wrong = 0; //number of pairs that are out of order
- for(int i = 0; i < SIZE-1; i++) {
- COUNT
- if(arr[i] > arr[i+1]) {
- wrong += 1;
- }
- }
- return wrong;
- }
- //print array
- void printarr(int arr[]) {
- printf("[ ");
- for(int i = 0; i < SIZE; i++) {
- printf("%d ",arr[i]);
- }
- printf("]");
- }
- //Let's be honest, the array's not gonna end up sorted for N much larger than 10 or so.
- //So the real point of this algorithm... is the journey.
- void arewethereyet(int arr[],int shuffles,int unsorted) {
- printf("Is THIS sorted?\t\t\t\t\t\t(%d) ",unsorted);
- printarr(arr); printf("\n");
- if(shuffles < 5) {
- printf("\t\tN");
- for(int i = 0; i <= shuffles-1; i = i + 1) {
- printf("o");
- }
- printf("%c", (char[]){"..!"}[rand()%3] );
- }
- else if(shuffles%(rand()%10+1) == 0) {
- printf("\t\tFor the %d%c%c time, no!", shuffles,
- (char[]){"tsnttttttt"}[shuffles%10], (char[]){"htdhhhhhhh"}[shuffles%10] );
- }
- else {
- int caps = rand()%3;
- printf("\t\tN%c",(char[]){"OOo"}[caps]);
- for(int i = 0; i < rand()%5; i = i + 1) {
- printf("%c",(char[]){"OOo"}[caps]);
- }
- int punct = rand()%3;
- for(int i = 0; i <= rand()%8; i = i + 1) {
- printf("%c",(char[]){".!!"}[punct]);
- }
- }
- printf("\n");
- if(!unsorted) {
- printf("\t\tWait, yes! Haha, it's finally over!\n");
- printf("Yaaaaay!\n");
- }
- return;
- }
- //-----------------------------------------------------------------------
- int main() {
- int * arr = makeList(SIZE);
- srand(time(NULL));
- //Code used to generate averages
- if(TESTS > 0) {
- int total = 0;
- for(int i = 0; i < TESTS; i++) {
- ops = 0;
- SORT(arr);
- printf("%d, ",ops);
- total += ops;
- arr = makeList(SIZE);
- //shuffle(arr);
- }
- printf("Average %d over %d runs\n",total/TESTS, TESTS);
- return 0;
- }
- printf("Converting list of size %d to max heap",SIZE);
- int start = clock();
- heapSort(arr);
- int end = clock();
- printf("%-*s%*d ms\n", 10,"\n\nTime:", 10,end-start);
- printf("%-*s%*d\n", 10,"Ops:", 10,ops);
- printf("%-*s%*d\n", 10,"N: ", 10,SIZE);
- printf("%-*s%*d\n\n", 10,"O(NlogN): ", 10,(int)(SIZE*log(SIZE)));
- if(SIZE < 64) {
- printHeap(arr);
- } else {
- followDown(arr);
- }
- shuffle(arr);
- printf("\nSorting list of size %d with Selection Sort...\n\n",SIZE);
- ops = 0;
- start = clock();
- selectionSort(arr);
- end = clock();
- printf("%-*s%*d ms\n", 10,"Time:", 10,end-start);
- printf("%-*s%*d\n", 10,"Ops:", 10,ops);
- printf("%-*s%*d\n", 10,"N: ", 10,SIZE);
- printf("%-*s%*d\n\n", 10,"O(N^2): ", 10,SIZE*SIZE);
- if(SIZE > 10) {
- return 0;
- }
- printf("\nAnd finally, attempting to sort the list with Bogosort in \n3\n");
- sleep(1);
- printf("2\n");
- sleep(1);
- printf("1\n");
- sleep(1);
- ops = 0;
- start = clock();
- bogoSort(arr);
- end = clock();
- printf("%-*s%*d ms\n", 10,"\n\nTime:", 10,end-start);
- printf("%-*s%*d\n", 10,"Ops:", 10,ops);
- printf("%-*s%*d\n", 10,"N: ", 10,SIZE);
- printf("%-*s", 10,"O((N+1)!):");
- int fact = 1; for(int i=1; i<SIZE; i++) { fact *= i; }
- printf("%*d\n",10,fact);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement