This is an open book, open notes, and open computer test. If you get stuck, talk to Jeff Ondich, but please don't talk to anyone else (not even Justin Thomson or the lab assistants) about the exam.
bool HaveCommonElement( string a[], string b[], int N ) { bool result = false; for( int i=0; i < N; i++ ) { for( int j=0; j < N; j++ ) { if( b[i] == a[j] ) result = true; } } return( result ); }
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 |
---|---|---|---|---|---|---|
1000 | ? | ? | ? | ? | ? | ? |
10000 | ? | ? | ? | ? | ? | ? |
20000 | ? | ? | ? | ? | ? | ? |
30000 | ? | ? | ? | ? | ? | ? |
void Concatenate( Node *firstList, Node *secondList ) { // Run to the end of the first list. Node *current = firstList; while( current != NULL ) current = current->next; // Link the last node of the first list // to the first node of the second list. current->next = secondList; }
Unfortunately, this version of Concatenate doesn't work.
Why not? How can you fix it?