Java Reference
In-Depth Information
{
if (a[i] == c) count++;
}
return count;
}
Exercise R14.10. Your task is to remove all duplicates from an array. For
example, if the array has the values
4 7 11 4 9 5 11 7 3 5
then the array should be changed to
4 7 11 9 5 3
Here is a simple algorithm. Look at
a[i]
. Count how many times it
occurs in
a
. If the count is larger than 1, remove it. What is the growth rate
of the time required for this algorithm?
Exercise R14.11. Consider the following algorithm to remove all
duplicates from an array. Sort the array. For each element in the array, look
at its next neighbor to decide whether it is present more than once. If so,
remove it. Is this a faster algorithm than the one in Exercise R14.10?
Exercise R14.12. Develop an O(n log (n)) algorithm for removing
duplicates from an array if the resulting array must have the same
ordering as the original array.
Exercise R14.13. Why does insertion sort perform significantly better
than selection sort if an array is already sorted?
Exercise R14.14. Consider the following speedup of the insertion sort
algorithm of Advanced Topic 14.1. For each element, use the enhanced
binary search algorithm that yields the insertion position for missing
elements. Does this speedup have a significant impact on the efficiency
of the algorithm?
Additional review exercises are available in WileyPLUS.
