Help with Recursive Merge Sort in Java Using Linked Lists

Discussion in 'Computer Programming, Emulation, and Game Modding' started by vayanui8, Jan 10, 2016.

  1. vayanui8
    OP

    vayanui8 GBAtemp Maniac

    Member
    1,086
    936
    Nov 11, 2013
    United States
    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;
      }
    }
     
  2. Author

    Author ****NEWS**FLASH**** 1 /̵͇̿̿/'̿-̅-̅-̅''

    Member
    458
    419
    Aug 30, 2014
    GBAtemp
    you accidentally tagged me

    LMAO
     
    Lucifer666 likes this.
  3. vayanui8
    OP

    vayanui8 GBAtemp Maniac

    Member
    1,086
    936
    Nov 11, 2013
    United States
    LOL I didn't realize that. It never even occurred to me that the code might tag someone
     
  4. Lucifer666

    Lucifer666 all the world needs is me

    Member
    1,499
    737
    Apr 22, 2011
    The Fourth Dimension
    God that is funny :rofl:

    Anyway do you mind sticking your code in a
    Code:
    
    
    box? You can do it by typing [ code] [ /code] (without spaces)
    With tabs/formatting and all