Programming Assignment 1

Data structure Java

Implement Shellsort for a linked list, based on a variant of bubble sort. The rather severe constraints imposed by the singly-linked list organization presents special problems for implementing Shellsort. Your task is to overcome these constraints and develop a simple, elegant implementation that does not sacrifice efficiency or waste space.

Step 1. First, implement a routine to build a list: read integers from standard input, and build a list node for each item consisting of an integer key and a link to the node for the next item. Also, write a routine to print out the contents of the linked list.

Have a Class File for Linked List Implementation, and define a set of methods:

LinkedNode() a constructor that initializes an Empty LinkedNode LinkedNode(T element) - a constructor that initializes an Empty LinkedNode with the given element.

LinkedNode getNext() return the next node void setNext(LinkedNode node) set next to point to the node T getElement() return the element void setElement(T element) store the element in current node

In your main Java file, have the following methods:

readValues(): read values from a file and build a linked list of integers. displayList(): Write a routine to display the contents of the linked list.

Step 2. Next, implement bubble sort: it should take as input a link to the beginning of a list, and should rearrange the nodes of the list so that they are in sorted order. This is not the same as rearranging keys within nodes: that is to be avoided because, in real applications, other information might be associated with the keys, or other data structures might have pointers to

the nodes. You may use dummy nodes or circular lists as you see fit, but do not use doubly-linked lists. That is, you should use only one link per node, with a constant extra number of links for bookkeeping.

Create a Class File to implement Sorting Algorithms:

bubbleSort(LinkedNode first): Implement the bubble sort on the linked list.

Step 3: There is a variation of the bubble sort algorithm called a shell sort that, rather than comparing neighboring elements each time through the list, compares elements that are some number (i) positions apart, where i is an integer less than n. For example, the first element would be compared to the (i+1) element, the second element would be compared to the (i+2) element, the nth element would be compared to the (n-i) element, etc. A single iteration is completed when all of the elements that can be compared, have been compared. On the next iteration, i is reduced by some number greater than 1 and the process continues until i is less than 1. Implement a shell sort using Knuths increment sequence: 1, 4, 13,....(3k 1)/2: it should take as input a link to the beginning of a list, and should rearrange the nodes of the list so that they are in sorted order.

shellSort(LinkedNode first): Implement the gap sort on the linked list.

Make a call to the Sorting algorithms from your Main Java Files.

resultBubbleSort() resultShellSort() 

Analysis. Use explicit counters to determine how many key comparisons and exchanges are used. Report these counts and the amount of time your program takes to sort random input files of size 100, 1,000, and 10,000. Include in your output.txt a two-dimensional table with a row corresponding to each file size and columns giving the total number of comparisons and exchanges used. Also, include a column that indicates how many seconds your program takes on each input.

Input and output. The input consists of integers separated by whitespace. You may use the sample input files given in the document folder. Your program should output the intermediate stages of the sort for debugging and to provide evidence that your program works. For example, on the input file random10.txt, your program should output:

a.out < random10.txt

k pass cmp exch ----------------------------------

18794675999198531023

10234653187998759991 10234653187998759991 10182346537579989199 10182346537579919899 10182346537579919899

If N is larger than 20, for brevity only print out the number of comparisons and exchanges for

each value of h. a.out < random100000.txt

k pass cmp exch ----------------------------------

4 1 4 2 1 1 1 2 1 3

125

277 ---------------------------------- Total 5 39 12

88573 2 29524 4 9841 10 3280 16 1093 21 364 29 121 36 40 49 13 46 4 28 1 16

 22854 281904 901590 

1547520 2077047 2889444 3595644 4898040 4599402 2799888 1599984 

 5722 49788 94555 

148293 203626 274828 391385 584519 634147 388543 175669 

---------------------------------- Total 257 25213317 2951075

Submission:

Submit your files on Canvas using the Programming Assignment 1 submission Link. You will submit a zip file containing:

Main.java the controller and tester for your program.

LinkedList.java - the Linked List class file.

Sorting.java- Class file for Sorting Algorithms

Output.txt With the output details as explained earlier.

Grading Rubric:

Grading will be done across the following points:

Correct implementation of Linked List interface.

Correct working of all three algorithms

Correct working for all input files

Compiles correctly on the first try

Exception Handling

Output File generated properly

All required files submitted