Homework Help is Here – Start Your Trial Now!
Engineering
Computer Engineering
Question 1: In this practice, you will implement the Merge Sort algorithm to sort an array of integers in ascending order. Additionally, assuming that an array can contain duplicates, for a given key, you will write a method that can display the starting and ending position of the key in the sorted array.

Question 1: In this practice, you will implement the Merge Sort algorithm to sort an array of integers in ascending order. Additionally, assuming that an array can contain duplicates, for a given key, you will write a method that can display the starting and ending position of the key in the sorted array.

Computer Networking: A Top-Down Approach (7th Edition)
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
See similar textbooks
icon
Related questions
Question
Step 3 Now that the array is sorted, create an iterative method called search. This method doesn't return anything and takes two parameters, a reference to an int array named numArray and an int named key. This method prints the left and right indices where the key value can be found in the array. This method should contain the following variables and operations: Four int variables named first, last, leftIndex, rightIndex. Variables first and last hold the index values for the start and end of the array. leftIndex and rightIndex should store the leftmost and rightmost indices that point to the key value. • Two binary searches, one to look for and store the leftIndex where the key first appears and another that does the same but for the rightIndex. A print statement that prints the two indices where the key value can be found. If the key value doesn't appear in the array, print -1 for the left and right indices. Step 4- Create a test driver to verify your implementation and use the jGRASP plugin to visualize how the mergeSort and search methods work. Sample Input 1: 10 12 6 464 1 206 Sample Output 1: Sorted: (1, 4, 4, 6, 6, 6, 10, 12, 20] The duplicates of 6 are between index 3 and index 5 Sample Input 2: 33, 5, 10, 1, 33, 4, 33, 0, 4, 33 Sample Output 2: Sorted: [0, 1, 4, 4, 5, 10, 33, 33, 33, 33] The duplicates of 7 are between index -1 and index -1
Transcribed Image Text:Step 3 Now that the array is sorted, create an iterative method called search. This method doesn't return anything and takes two parameters, a reference to an int array named numArray and an int named key. This method prints the left and right indices where the key value can be found in the array. This method should contain the following variables and operations: Four int variables named first, last, leftIndex, rightIndex. Variables first and last hold the index values for the start and end of the array. leftIndex and rightIndex should store the leftmost and rightmost indices that point to the key value. • Two binary searches, one to look for and store the leftIndex where the key first appears and another that does the same but for the rightIndex. A print statement that prints the two indices where the key value can be found. If the key value doesn't appear in the array, print -1 for the left and right indices. Step 4- Create a test driver to verify your implementation and use the jGRASP plugin to visualize how the mergeSort and search methods work. Sample Input 1: 10 12 6 464 1 206 Sample Output 1: Sorted: (1, 4, 4, 6, 6, 6, 10, 12, 20] The duplicates of 6 are between index 3 and index 5 Sample Input 2: 33, 5, 10, 1, 33, 4, 33, 0, 4, 33 Sample Output 2: Sorted: [0, 1, 4, 4, 5, 10, 33, 33, 33, 33] The duplicates of 7 are between index -1 and index -1
Question 1: In this practice, you will implement the Merge Sort algorithm to sort an array of integers in ascending order. Additionally, assuming that an array can contain duplicates, for a given key, you will write a method that can display the starting and ending position of the key in the sorted array. 4 7. 8. numArray 10 12 4. 6. 4. 20 Step 1- You are given a method called mergeSort, which calls the method mergeSortRec. You are asked to create the method mergeSortRec, which returns nothing and takes the following parameters: an int array reference named numArray, an int first, and an int last. • The parameters first and last are used to keep track of the indices. The method mergeSortRec should recursively call itself to cut the array into two halves. Invoke the mergeSortRec on the left half and then invoke the mergeSortRec on the right half. It should stop once the array is completely divided. This means that the array can no longer be divided into two halves (hint: first is no longer less than last). • Then, sort and merge the two halves of the array by invoking the method merge. Step 2-Create the method merge, which sorts and merges the left half and right half of the array. The method returns nothing and takes these parameters: an int array reference named numArray, an int first, and an int last. This method should contain the following variables and operations: A temporary array of length n (hint: if the first index of the array is 4 and the last index is 7, then the length of the array is 4). Variables to keep track of the indices. Iterate through the array and compare the element in the left half and the element in the right half, and then add the smaller element to the temporary array. If there are elements leftover from one side of the array, then add the remaining elements to the temporary array in an iterative fashion. Copy the elements from the tèmporary array to the numArray.
Transcribed Image Text:Question 1: In this practice, you will implement the Merge Sort algorithm to sort an array of integers in ascending order. Additionally, assuming that an array can contain duplicates, for a given key, you will write a method that can display the starting and ending position of the key in the sorted array. 4 7. 8. numArray 10 12 4. 6. 4. 20 Step 1- You are given a method called mergeSort, which calls the method mergeSortRec. You are asked to create the method mergeSortRec, which returns nothing and takes the following parameters: an int array reference named numArray, an int first, and an int last. • The parameters first and last are used to keep track of the indices. The method mergeSortRec should recursively call itself to cut the array into two halves. Invoke the mergeSortRec on the left half and then invoke the mergeSortRec on the right half. It should stop once the array is completely divided. This means that the array can no longer be divided into two halves (hint: first is no longer less than last). • Then, sort and merge the two halves of the array by invoking the method merge. Step 2-Create the method merge, which sorts and merges the left half and right half of the array. The method returns nothing and takes these parameters: an int array reference named numArray, an int first, and an int last. This method should contain the following variables and operations: A temporary array of length n (hint: if the first index of the array is 4 and the last index is 7, then the length of the array is 4). Variables to keep track of the indices. Iterate through the array and compare the element in the left half and the element in the right half, and then add the smaller element to the temporary array. If there are elements leftover from one side of the array, then add the remaining elements to the temporary array in an iterative fashion. Copy the elements from the tèmporary array to the numArray.
Expert Solution
steps

Step by step

Solved in 3 steps with 8 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY
SEE MORE TEXTBOOKS