PLEASE READ ALL INSTRUCTIONS CAREFULLY. YOUR CODE MUST COMPILE AND PASS THE TWO
ID: 3539668 • Letter: P
Question
PLEASE READ ALL INSTRUCTIONS CAREFULLY.
YOUR CODE MUST COMPILE AND PASS THE TWO DRIVERS BELOW!!!
EXPLAIN YOUR CODE WITH // COMMENTS!!!
THANK YOU IN ADVANCE!
The second two methods of this assignment must be implemented recursively. Your methods must be in a file named Sort.java.
}
The second method, called countOccurances records the number of times each value occurs. The header is as follows:
public static void countOccurances(LinkedList list, int[] counters)
You will use counter[i] to count the number of i's which occur in list. It will be a recursive method. The base case is when the linked list is empty. In that case, nothing needs to be done to your counters, because no values are in the list. In the recursive case, increment the counter corresponding to the first value in the list, and call countOccurances on the rest of the list.
The third method constructs a sorted list based off an array of counters. It has the header:
The method must be recursive. The base case is when startPosition is not a legal position (it is either too high or too low). In the base case, you will return null, since no sensible list can be constructed. Otherwise, you are in the recursive case. In the recursive case, first (1) recursively call the buildList with an appropriate change to startPosition. (2) Then build a linked list containing counters[startPosition] values, where each value is equal to startPosition. You will contruct the linked list of (2) using a loop. (3) Make sure you connect the list built in (2) with the list returned from the recursive call in (1). (4) Return the linked list from step (3).
Here is included code to help with the assignment:
public class LinkedList
{
public int value;
public LinkedList next;
public LinkedList(int value, LinkedList next)
{
this.value = value;
this.next = next;
}
public LinkedList()
{
}
}
Explanation / Answer
/*please rate both my answers 5 star(of course only if you are satisfied) otherwise I might not get the points for this answer as this answer of mine is being answered after the deadline, so won't get points for this answer. Will get points for the earlier answer as it was answered within deadline. Please consider this. And do ask in case of any doubt. Thanks*/
/*By the way the code is working with both Drivers perfectly*/
public class Sort {
static int MIN = 0,MAX=19;
public static LinkedList sort(LinkedList list) {
int[] occurances = new int[20];
countOccurances(list, occurances);
return buildList(occurances, 0);
}
private static LinkedList buildList(int[] occurances, int startPosition) {
//Base Case. If the start position is invalid return null
if(startPosition < MIN || startPosition > MAX) {
return null;
}
int count;
LinkedList oldList = null,newList = new LinkedList(),head = null;
count = occurances[startPosition];//get the count of the number startPosition
//If the number is 0 or less(number doesn't exist in list),return build list with next position
if(count <= 0) return buildList(occurances,startPosition + 1);
//Loop to create linked list with the value startPosition
while(count > 0){
newList = new LinkedList();//create a new linked list(node)
newList.value = startPosition;//initialize its value with startPosition
if(oldList == null){ //If it is the first node in the list, then
head = newList; //make it head of the list
oldList = newList; //update the tail(oldList) of the list
}
else{ //If it is not the first node in the list
oldList.next = newList; //then attach the node to the tail of the list and
oldList = newList; //update the tail of the list
}
count--;//decrease the count
}
LinkedList recursiveList = buildList(occurances,startPosition+1); //recursive call
newList.next = recursiveList; //Attach the list obtained by the recursive call to tail of this list
return head; //Return the head of this list
}
public static void countOccurances(LinkedList list, int[] occurances) {
if(list == null) return;//base case. Do nothing
//Recursive case.
occurances[list.value] = occurances[list.value] + 1;//Increment the count of first element by 1
countOccurances(list.next, occurances);//recursively call countOccurances with the rest of the list
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.