Short Answers Section 13.1 Quadratic Sorting Algorithms |
5 3 8 9 1 7 0 2 6 4Draw this array after the FIRST iteration of the large loop in a selection sort (sorting from smallest to largest).
5 3 8 9 1 7 0 2 6 4Draw this array after the FIRST iteration of the large loop in an insertion sort (sorting from smallest to largest). This iteration has shifted at least one item in the array!
void selectionsort(int data[ ], size_t n);Your program also has an integer array called x, with 10 elements. Write two function calls: The first call uses selectionsort to sort all of x; the second call uses selectionsort to sort x[3]..x[9].
Short Answers
Section 13.2
Recursive Sorting
Algorithms
3, 0, 2, 4, 5, 8, 7, 6, 9Which of these elements could be the pivot? (There may be more than one possibility!)
5 3 8 9 1 7 0 2 6 4Suppose we partition this array using quicksort's partition function and using 5 for the pivot. Draw the resulting array after the partition finishes.
5 3 8 9 1 7 0 2 6 4Draw this array after the TWO recursive calls of merge sort are completed, and before the final merge step has occured.
void merge(int data[ ], size_t n1, size_t n2); // Precondition: The first n1 elements of data are sorted, and the // next n2 elements of data are sorted (from smallest to largest). // Postcondition: The n1+n2 elements of data are now completely // sorted.
Short Answers
Section 13.3
An O(n log n) Algorithm
Using a Heap
Worst Case | Average Case | |
Binary search of a sorted array | . | . |
Insertion sort | . | . |
Merge sort | . | . |
Quick sort without "median of three" pivot selection | . | . |
Quick sort with "median of three" pivot selection | . | . |
Selection sort | . | . |
Heap sort | . | . |
Short Answers
Beyond the Book
int compare_ints(const void* p1, const void* p2); // Precondition: p1 and p2 are really pointers to integers. // Postcondition: The return value is: // (a) negative if *p1 < *p2 // (b) zero if *p1 == *p2 // (c) positive if *p1 > *p2 void qsort( void* base, size_t n, size_t bytes, int compar(const void*, const void*) ); // Same specification as the standard library qsort function.Your program also has an integer array called x, with 10 elements. Write two function calls: The first call uses qsort to sort all of x; the second call uses qsort to sort x[3]..x[9].
Multiple Choice Section 13.1 Quadratic Sorting Algorithms |
1 2 3 4 5 0 6 7 8 9Which statement is correct? (Note: Our selectionsort picks largest items first.)
2 4 5 7 8 1 3 6Which statement is correct? (Note: Our selectionsort picks largest items first.)
Multiple Choice
Section 13.2
Recursive Sorting
Algorithms
2 5 1 7 9 12 11 10Which statement is correct?
Multiple Choice
Section 13.3
An O(n log n) Algorithm
Using a Heap
6 4 5 1 2 7 8How many reheapifications downward have been performed so far?
Data Structures and Other Objects Using C++
Thank you for visiting
http://www.cs.colorado.edu/~main/questions/chap13q.html
Copyright © 2000
Addison-Wesley Computer and Engineering Publishing Group