Assignment 7 - Searching, Sorting, and Efficiency Analysis
[65 points]
For this assignment, you will complete searching/sorting tasks and efficiency analysis. No
code is to be written for this assignment.
Problem 1 -
...
Assignment 7 - Searching, Sorting, and Efficiency Analysis
[65 points]
For this assignment, you will complete searching/sorting tasks and efficiency analysis. No
code is to be written for this assignment.
Problem 1 - Binary Search (8 points)
Search for the character Z using the binary search algorithm on the following array of
characters: A D H J L N P R Z
For each iteration of binary search use a table similar to the table below to list: (a) the
left index and (b) the right index of the array that denote the region of the array that is still
being searched, (c) the middle point of the array, and (d) the character-to-character number
of comparisons made during the search (line 09 and line 11 of the Binary Search algorithm
at the end of the assignment).
Grading (8 points): 0.5 point for each correct left, right, and middle index,
and for each compare.
Iteration Left Right Middle Number of Comparisons
1 0 8 4 2
2 5 8 6 2
3 7 8 7 2
4 8 8 8 1
Problem 2 - Selection Sort (7 points)
List the resulting array after each iteration of the outer loop of the selection sort algorithm.
Indicate the number of character-to-character comparisons made for each iteration (line 07
of the Selection Sort algorithm at the end of the assignment). Sort the following array of
characters (sort into alphabetical order): C Q R B P D X
Grading (7 points): 0.5 point for each correct iteration;
0.5 points for the number of comparisons
B Q R C P D X - 6 comparisons
B C R Q P D X - 5 comparisons
B C D Q P R X - 4 comparisons
B C D P Q R X - 3 comparisons
B C D P Q R X - 2 comparisons
B C D P Q R X - 1 comparisons
B C D P Q R X - 0 comparisons
1Rutgers University CS111 - Introduction to Computer Science Fall 2020
Problem 3 - Insertion Sort (12 points)
List the resulting array after each iteration of the outer loop of the insertion sort algorithm.
Indicate the number of character-to-character comparisons made for each iteration (line 06
of the Insertion Sort algorithm at the end of the assignment). Sort the following array of
characters (sort into alphabetical order): C Q R B P D X
Grading (12 points): 0.5 point for each correct iteration;
0.5 points for each number of comparisons
C Q R B P D X - 1 comparisons
C Q R B P D X - 1 comparisons
B C Q R P D X - 3 comparisons
B C P Q R D X - 3 comparisons
B C D P Q R X - 4 comparisons
B C D P Q R X - 1 comparisons
Problem 4 - Mergesort (12 points)
List the resulting array after each call of the merge method. Indicate the number of characterto-character comparisons made for each call to merge (line 20 of the merge method at the
end of the assignment). Sort the following array of characters (sort into alphabetical order):
C Q S A X B T
Grading (12 points): 0.5 point for
[Show More]
