I'm currently working on programming a recursive mergesort method for my comp sci class. We are required to use Linked Lists for this method, and as I'm pretty terrible at both recursion and sorting algorithms this assignment has been giving me alot of trouble. We were given some starter code to get an idea, but I don't think my methods work properly, and Im getting a stack overflow error. Could somebody please help me?
Code:
import java.util.*;
import java.io.*;
/**
* Implements a recursive mergesort on a LinkedList data type
*
* [USER=353451]@Author[/USER] G. Peck
* @created July 18, 2002
*
* Modified by Jason Quesenberry and Nancy Quesenberry
* February 9, 2006
*/
public class MergeList{
private Scanner inFile;
private String myFile;
/**
* Open a file containing id/inventory pairs of data
*
* @param fileName File to be opened
*/
public MergseList(String fileName)
{
try{
inFile = new Scanner(new File(fileName));
}
catch(IOException i){
System.out.println("Error: " + i.getMessage());
}
myFile = fileName;
}
/**
* Reads a file containing id/inv data pairs. The first line of the
* file contains the number of id/inventory integer pairs listed on
* subsequent lines.
*
* @param list Reference to LinkedList to which data will be added
*/
public void readData(LinkedList<Item> list){
int id = 0;
int inv = 0;
LinkedList<Item> tempList = new LinkedList<Item>();
int count = 0;
while (inFile.hasNext())
{
count++;
if(count%2 == 0)
{
inv = Integer.parseInt(inFile.next()
);
tempList.addFirst(new Item(id, inv));
}
else
{
id = Integer.parseInt(inFile.next());
}
}
list = tempList;
}
/**
* Prints contents of list
*
* @param list linked list to be printed
*/
public void printList(LinkedList list)
{
System.out.printf("%5s%16s","Id","Inventory\n");
ListIterator<Item> listIterator = list.listIterator();
while(listIterator.hasNext())
{
Item harman = listIterator.next();
System.out.printf("%5s%16s", harman.getId() , harman.getInv());
System.out.println();
}
System.out.println();
System.out.println();
}
/**
* Splits listA into two parts. listA retains the first
* half of the list, listB contains the last half of
* the original list.
*
* @param listA Original list. reduced by half after split.
* @param listB Contains last half of the original list
*/
public void split(LinkedList<Item> listA, LinkedList<Item> listB)
{
int temp = listA.size()/2;
while (temp<listA.size())
{
listA.removeLast();
listB.removeFirst();
temp++;
}
}
/**
* Two linked lists listA and listB are merged into a single
* linked list mergedList. They are placed in mergedList starting
* with the smallest item on either list and continue working up to
* to largest item.
*
* @param listA LinkedList in nondecreasing order
* @param listB LinkedList in nondecreasing order
* @return List containing all the values from lists listA
* and listB, in nondecreasing order
*/
public LinkedList<Item> merge(LinkedList<Item> listA, LinkedList<Item> listB){
// make sure the target list is empty
LinkedList <Item> mergedList = new LinkedList <Item>();
ListIterator<Item> listIterator1 = listA.listIterator();
ListIterator<Item> listIterator2 = listB.listIterator();
while(listIterator1.hasNext() && listIterator2.hasNext())
{
Item jim = listIterator1.next();
Item jam = listIterator2.next();
if(jim.compareTo(jam) <= 0)
{
mergedList.addLast(jam);
}
else
{
mergedList.addLast(jim);
}
}
while(listIterator1.hasNext())
{
mergedList.addLast(listIterator1.next());
}
while(listIterator2.hasNext())
{
mergedList.addLast(listIterator2.next());
}
// start at mergedList left and right item
// continue until either left or right list has no more value to add
// use <= instead of < so if duplicate take from left so sort is stable
// One of the next two while loops will execute. It will be the one with some values
// left on the list.
return mergedList;
}
/*** The linked list is returned in sorted order.
* Sorted order has the smallest item first and the largest item
* last. The ordering is determined by the order defined in the
* Comparable class. The method uses the merge sort technique and
* must be recursive.
*
* @param listA LinkedList to be sorted
* @return LinkedList in sorted (nondecreasing) order
*/
public LinkedList<Item> mergeSort(LinkedList <Item> listA){
LinkedList <Item> listB = (LinkedList) listA.clone();
// Split the list in half. If uneven then make left one larger.
split(listA, listB);
return merge(mergeSort(listA), mergeSort(listB));
}
/**
* Reverses the order of a list
*
* @param list LinkedList to be reversed
* @return List in reverse order
*/
public LinkedList<Item> reverseList(LinkedList <Item>list)
{
LinkedList <Item> listB = new LinkedList<Item>();
ListIterator<Item> listIterator = list.listIterator();
while(listIterator.hasNext())
{
listB.addLast(list.getFirst());
}
return listB;
}
}
