Question: import java.util.*; /** * This class represents chains of linked nodes that * can be sorted by a Shell sort. * */ public class ChainSort
import java.util.*; /** * This class represents chains of linked nodes that * can be sorted by a Shell sort. * */ public class ChainSort
> { private Node firstNode; // reference to first node public ChainSort() { this.firstNode = null; } public void display() { Node currentNode = this.firstNode; while (currentNode != null) { System.out.print(currentNode.data + " "); currentNode = currentNode.next; } System.out.println(); } // end display public boolean isEmpty() { return this.firstNode == null; } // end isEmpty public void addToBeginning(T newEntry) { Node newNode = new Node(newEntry); newNode.next = this.firstNode; this.firstNode = newNode; } // end addToBeginning public void shellSort(int chainSize) { //TODO Project3 // for each space // create sub-chains: // set previousNode to the first node in the chain // set currentNode to the first node in the chain // with a for loop traverse nodes space times using currentNode // to find the second node of the first sub-chain // // with a while loop set up backward links for all sub-chains: // set currentNode's previous pointer to the previousNode // set previousNode to its next node and do the same with the currentNode // // call incrementalInsertionSort } // end shellSort /** * Task: Sorts equally spaced elements of a linked chain into * ascending order. Sub-chains created with a use of previous. * * @param space the space between the nodes of the * elements to sort */ private void incrementalInsertionSort( int space) { //TODO Project3 // when sorting do not change pointers - simply swap the data if needed } // end incrementalInsertionSort private class Node { private S data; private Nodenext; private Nodeprevious; // ADDED for linking backwards for shell sort private Node(S dataPortion) { this.data = dataPortion; this.next = null; this.previous = null; } } // end Node // ************ TEST DRIVER ***************** public static void main(String args[]) { System.out.println("What size chain should be used?"); int chainSize = getInt(" It should be an integer value greater than or equal to 1."); System.out.println("What seed value should be used?"); int seed = getInt(" It should be an integer value greater than or equal to 1."); Random generator = new Random(seed); ChainSortmyChain = new ChainSort(); for (int i = 0; i -------------------------------------------------------------------------------------------------------------------------------------------
SAMPLE RUN
What size chain should be used?
It should be an integer value greater than or equal to 1.
7
What seed value should be used?
It should be an integer value greater than or equal to 1.
11
Original Chain Content: 40 7 33 55 11 68 38
----->Before partial sort with space 3 :
40 7 33 55 11 68 38
-> Comparing 55 with 40
-> Comparing 11 with 7
-> Comparing 68 with 33
-> Comparing 38 with 55
---> 38 is smaller than 55:
-> Comparing 38 with 40
---> 38 is smaller than 40:
38 7 33 40 11 68 55
----->After partial sort done with space 3 :
38 7 33 40 11 68 55
----->Before partial sort with space 1 :
38 7 33 40 11 68 55
-> Comparing 7 with 38
---> 7 is smaller than 38:
7 38 33 40 11 68 55
-> Comparing 33 with 38
---> 33 is smaller than 38:
-> Comparing 33 with 7
7 33 38 40 11 68 55
-> Comparing 40 with 38
-> Comparing 11 with 40
---> 11 is smaller than 40:
-> Comparing 11 with 38
---> 11 is smaller than 38:
-> Comparing 11 with 33
---> 11 is smaller than 33:
-> Comparing 11 with 7
7 11 33 38 40 68 55
-> Comparing 68 with 40
-> Comparing 55 with 68
---> 55 is smaller than 68:
-> Comparing 55 with 40
7 11 33 38 40 55 68
----->After partial sort done with space 1 :
7 11 33 38 40 55 68
III. Working with ChainSort.java apply incrementalInsertionSort algorithm to work with a linked chain instead of an array and implement a Shell sort for a linked chain. The skeleton of the application is provided Before calling incrementalInsertionSort method, set the previous pointers to create the appropriate sub-chains as shown in the picture below: 1. 38 modlessoit space 3 46 see sowu 2. 3. During the sorting process, replace appropriate data without changing the next pointers. Sample run with 7 elements and seed 11: What size chain should be used? It should be an integer value greater than or equal to 1. What seed value should be used? It should be an integer value greater than or equal to III. Working with ChainSort.java apply incrementalInsertionSort algorithm to work with a linked chain instead of an array and implement a Shell sort for a linked chain. The skeleton of the application is provided Before calling incrementalInsertionSort method, set the previous pointers to create the appropriate sub-chains as shown in the picture below: 1. 38 modlessoit space 3 46 see sowu 2. 3. During the sorting process, replace appropriate data without changing the next pointers. Sample run with 7 elements and seed 11: What size chain should be used? It should be an integer value greater than or equal to 1. What seed value should be used? It should be an integer value greater than or equal to
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help