Questions Chapter 7 Flashcards
The Shellsort works by:
a. partitioning the array
b. swapping adjacent elements
c. dealing with widely separated elements
d. starting with the normal insertion sort.
c. dealing with widely separated elements
If an array has 100 elements, then Knuth’s algorithm would start with an interval of _____.
40
To transform the insertion sort into the Shellsort, which of the following do you NOT do?
a. substitute h for 1
b. insert an algorithm for creating gaps of decreasing width
c. enclose the normal insertion sort in a loop
d. change the direction of the indices in the inner loop
d. change the direction of the indices in the inner loop
True or False: a good interval sequence for the Shellsort is created by repeatedly dividing the array size in half.
False
Fill in the big O values: The speed of the Shellsort is more than _______ but less than _______.
Shellsort speed more than O(N^2), but less than O(N*logN)
Partitioning is:
a. putting all the elements larger than a certain value on one end of the array
c. dividing an array in half
d. sorting each half of an array separately
a. putting all the elements larger than a certain value on one end of the array
When partitioning, each array element is compared to the _________.
pivot
In partitioning, if an array element is equal to the pivot:
a. it is passed over
b. it is passed over or not, depending on the other array element
c. it is placed in the pivot position
d. it is swapped
d. it is swapped
True or False: In quicksort, the pivot can be an arbitrary element of the array
True
Assuming larger keys on the right, the partition is:
a. the element between the left and right subarrays
b. the key value of the element between the left and right subarrays
c. the left element in the right subarray
d. the key value of the left element in the right subarray
c. the left element in the right subarray
QuickSort involves partitioning the original array and then ______________________.
recursively calling recQuickSort
After a partition in a simple version of quickSort, the pivot may be:
a. used to find the median of the array
b. exchanged with an element of the right subarray
c. used as the starting point of the next partition
d. discarded
d. discarded
Median-of-three partitioning is a way of choosing the _________.
pivot
In quicksort, for an array of N elements, the partitionIt( ) method will examine each element approximately ________ times
n+2
True or False: you can speed up quicksort if you stop partitioning when the partition size is 5 and finish by using a different sort
True
The expression _____________ means sorting every nth element.
n-sorting
A sequence of numbers, called the _______ ________ or ______ ________, is used to determine the sorting intervals in the Shellsort
interval sequence or gap sequence
A widely used interval sequence is generated by the recursive expression __________, where the initial value of __ is 1.
interval sequence recursive expression: h=3*h+1
initial value of h is 1
The _______ is the value that determines into which group an item will go during partitioning. Items _______ than the _____ go in the ______ group; _______ items go in the ______ group.
the pivot value.
items smaller than the pivot go in the left group.
items larger go in the right group.
In the partitioning algorithm, two array indices, each in its own ________ _______, start at opposite ends of the array and step toward each other, looking for items that need to be _______.
each in its own while loop.
items that need to be swapped.
Partitioning operates in ______ time, making N plus 1 or 2 comparisons and fewer than N/2 swaps
O(N) time
Quicksort partitions an array and then calls itself recursively _______ number of times to sort the remaining subarrays.
calls itself recursively 2 times
During the partition, the _____ is placed out of the way on the _______ side, and is not involved in the partitioning process
pivot is placed out of the way on the right side
In the simple version of quicksort, performance is only ______ for already sorted (or inversely sorted) data.
O(N^2) time
In the more advanced version of quicksort, the pivot can be the ______ of the first, last, and centre items in the subarray. This is called the ____________________ partitioning
median. median-of-three partitioning.
Median-of-three partitioning effectively eliminates the problem of _______ performance for already sorted data.
O(N^2) performance for already sorted data
Subarrays smaller than the cutoff can be sorted by ___________ sort.
insertion sort
The _______ sort is about as fast as quicksort, but uses twice as much memory
radix sort
