Java Reference
In-Depth Information
Suppose that L is a list of 10,000 elements. Find the average number of
comparisons made by selection sort and insertion sort to sort L .
11.
Suppose that L is a sorted list of 4096 elements. What is the maximum number
of comparisons made by a binary search to determine if an item is in L ?
12.
Suppose that the elements of a list are in descending order and they need to be
put in ascending order. Write a Java method that takes as input an array of items
in descending order and the number of elements in the array. The method
rearranges the element of the array in ascending order. Your method must not
incorporate any sorting algorithms, that is, no item comparisons should occur.
13.
PROGRAMMING EXERCISES
1. Write a program to test the method binarySearch . Use either the method
insertionSort or selectionSort to sort the list before the search.
2. Write a method, remove , that takes three parameters: an array of integers,
the length of the array, and an integer, say, removeItem . The method
should find and delete the first occurrence of removeItem in the array. If
the value does not exist or the array is empty, output an appropriate message.
(Note that after deleting the element, the array size is reduced by 1 .) You
may assume that the array is unsorted.
3. Write a method, removeAt , that takes three parameters: an array of integers,
the length of the array, and an integer, say, index . The method deletes the
array element indicated by index .If index is out of range or the array is
empty, output an appropriate message. (Note that after deleting the element,
the array size is reduced by 1 .) You may assume that the array is unsorted.
4. Write a method, removeAll , that takes three parameters: an array of
integers, the length of the array, and an integer, say, removeItem . The
method should find and delete all occurrences of removeItem from the
array. If the value does not exist or the array is empty, output an appropriate
message. (Note that after deleting the element, the array size will be
reduced.) You may assume that the array is unsorted.
5. Redo Programming Exercises 2, 3, and 4 for a sorted array.
6. Write a method, insertAt , that takes four parameters: an array of integers;
the length of the array; an integer, say, insertItem ; and an integer, say,
index . The method inserts insertItem in the array at the position specified
by index .If index is out of range, output an appropriate message. (Note
that index must be between 0 and arraySize , that is, 0 index <
arraySize .) You may assume that the array is unsorted.
7. Write a version of a sequential search that can be used to search a string
Vector object. Also, write a program to test your algorithm.
8. Write a version of a selection sort that can be used to sort a string Vector
object. Also, write a program to test your algorithm.
 
Search WWH ::




Custom Search