This is an open book, open notes, and open computer test. You may not use any books other than your textbook, and you may not use Internet resources from off campus. If you get stuck, talk to Jeff Ondich, but please don't talk to anyone else about the exam.
short i = 1; while( i > 0 ) { i++; } cout << i << endl;
int Sum( int N );
int max = 0; for( int i=0; i < N; i++ ) { for( int j=0; j < N; j++ ) { if( a[i] - a[j] > max ) max = a[i] - a[j]; } }
struct CharNode { char mData; CharNode *mNext; }; typedef CharNode * CharNodePtr; int MysteryFunction( CharNodePtr& head ) { int n = 0; CharNodePtr current = head; while( current != 0 ) { n++; current = current->mNext; } return( n ); }
Selection, Insertion, and Merge Sorts are all members of a class of sorting algorithms whose performance is usually measured by counting the number of array element comparisons need to be done to complete the sorting of the array. That is, we count the number of times something like "if( a[i] < a[j] )" gets executed during the run of the algorithm. It would take several pages to provide a reasonably rigorous argument that the comparison count is a good measure of performance for these algorithms. With a lot less rigor, we can say something like this: by counting comparisons, we are counting the number of iterations of the inner loop, and by counting inner loop iterations, we are counting the most time-consuming portion of the algorithm.
So, in what follows, you're going to count comparisons
and measure running times for the three algorithms and several
values of N. Let's get started.
N | Comp. count for Sel. Sort | Running time for Sel. Sort | Comp. count for Ins. Sort | Running time for Ins. Sort | Comp. count for Merge Sort | Running time for Merge Sort |
---|---|---|---|---|---|---|
10 | ? | ? | ? | ? | ? | ? |
100 | ? | ? | ? | ? | ? | ? |
1000 | ? | ? | ? | ? | ? | ? |
10000 | ? | ? | ? | ? | ? | ? |
20000 | ? | ? | ? | ? | ? | ? |
30000 | ? | ? | ? | ? | ? | ? |