Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: Mergesort with linkedlist using recursion

  1. #1
    Junior Member
    Join Date
    Nov 2013
    Posts
    9
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Mergesort with linkedlist using recursion

    Hi, I'm trying to do a mergesort with linklist using recursion. The problem I'm running into is, the code will not enter if(ordered[1].size() > 2) if block to process the second part of the linkedlist. I can't seem to figure out why that it. Please look at my code below and let me know if you want me to post the LinkedList class I created, thanks.

    mergesort code:
    public class Merge{
     
      public static LinkedListABS merge (LinkedListABS first, LinkedListABS second){
        // purpose : to merge together two lists of strings (each that are sorted alphabetically)
        // input : two lists 
        // output : a "new" list that is sorted alphabteically and contains all the elements in the two input lists
        //          the new list should have all new nodes in it
     
        // Note: you must use recursion for this problem
        if(first.look(0).compareTo(second.look(0)) > 0){
          first.insert(second.look(0));
          second.remove();
        } else if(first.look(1).compareTo(second.look(0)) > 0){
          first.insert(second.look(0),1);
        }
     
        return first;
      }
     
     
      public static LinkedListABS[] split(LinkedListABS list){
        // purpose : to split the input list into two (almost) equally sized lists
        // input : a list of strings 
        // output : an array of two "new" lists a list. The first list corresponds to first half of the 
        //          input list and the second list corresponds to the second half of the input list 
        //          The output lists should have all new nodes in it
        // example: list = {s0,s1,s2,s3,s4,s5}
        //          split(list) -> [{s0,s1,s2}, {s3,s4,s5}]
        //          list = {s0,s1,s2,s3,s4,s5,s6}
        //          split(list) -> [{s0,s1,s2,s3}, {s4,s5,6}]
        // when list has even length the list is split exactly in half size()/2 strings in each
        // when list has odd length, then the first list has size()/2+1 strings and the second has size()/2 
        //                                                   (using integer division)
        if(list.size() > 1){
          System.out.println("Entered size>1 and list is: " + list.toString());
          int s = list.size();
          int middle;
          if(s%2 == 0){
            middle = s/2;
          }else{
            middle = (s/2) + 1;
          }
          System.out.println("s = " + s + " middle = " + middle);
          LinkedListABS s1 = CopyLinkedList.copy(list, 0, middle);
          System.out.println("s1 is: " + s1.toString());
          LinkedListABS s2 = CopyLinkedList.copy(list, middle, list.size());
          System.out.println("s2 is: " + s2.toString());
          LinkedListABS[] ordered = {s1,s2};
          System.out.println("ordered[0] is " + ordered[0] + " ordered[1] is " + ordered[1]);
          return ordered;
        }else{
          System.out.println("Entered size <=1");
          LinkedListABS[] ordered = {list};
          System.out.println("ordered is " + ordered[0]);
          return ordered;
        }
     
      }
     
     
      public static LinkedListABS sort(LinkedListABS list){
        // puspose : sorts the link of Strings (alphabteically) using mergesort
        // input : a list of Strings
        // output : a "new" list of the same Strings but sorted alphabetically
        //          (the input list must be left unchanged. the new list must have all new nodes in it)
        System.out.println("entered sort");
        LinkedListABS n = new LinkedList();
     
        LinkedListABS copied = CopyLinkedList.copy(list, 0, list.size());
        System.out.println("copy created: " + copied.toString());
        LinkedListABS[] ordered = split(copied);
        System.out.println("ordered[0] = " + ordered[0].toString() + " ordered[1] = " + ordered[1].toString());
        //if((ordered[0].size() > 2) || (ordered[1].size() > 2)){
        if(ordered[0].size() > 2){
          System.out.println("Entered ordered[0].size() > 2");
          LinkedListABS s = sort(ordered[0]);
          return s;
        } else if(ordered[0].size() == 2){
          System.out.println("Entered ordered[0].size = 2");
          if(ordered[0].look(0).compareTo(ordered[0].look(1)) > 0){
            ordered[0].insert(ordered[0].look(1));
            ordered[0].remove(2);
            System.out.println("ordered[0] = " + ordered[0].toString());
          }
          System.out.println("ordered[0] = " + ordered[0].toString());
        }
     
        if(ordered[1].size() > 2){
          System.out.println("Entered ordered[1].size() > 2");
          LinkedListABS s = sort(ordered[1]);
          return s;
        } else if(ordered[1].size() == 2){
          System.out.println("Entered ordered[1].size = 2");
          if(ordered[0].look(0).compareTo(ordered[0].look(1)) > 0){
            ordered[1].insert(ordered[1].look(1));
            ordered[0].remove(2);
            System.out.println("ordered[1] = " + ordered[1].toString());
          }
          System.out.println("ordered[0] = " + ordered[0].toString());
        }
     
         LinkedListABS m = merge(ordered[0], ordered[1]);
         n = m;
        //}
     
        return n;    
      }
     
    }

    test code:
    public class MergeTest{
     
      public static void main(String[] args){
     
        LinkedListABS list = new LinkedList();
        System.out.println("Size is: " + list.size());
        System.out.println("isEmpty: " + list.isEmpty());
        System.out.println("inserted at: " + list.insert("cat"));
        System.out.println("inserted dog at: " + list.insert("dog"));
        list.insert("eel");
        list.insert("mouse");
        list.insert("goat");
        list.insert("sheep");
        System.out.println("list: " + list.toString());
        LinkedListABS order = Merge.sort(list);
        System.out.println("order is " + order.toString());
        System.out.println("list: " + list.toString());
     
      }
    }


    --- Update ---

    LinkedList class
    /
    public class LinkedList extends LinkedListABS {
     
      private int position = 1; //variable to hold the position of the node
      private Node runner;
     
      // zero parameter constructor 
      public LinkedList(){
        head = null;
      }
     
      /* checks if list is empty or not 
       * return true if the list is empty and false otherwise*/
      public boolean isEmpty(){
        if(head == null){
          return true;
        }else{
          return false;
        }
      }
     
      /* returns the number of Strings in the list */
      public int size(){
        int s = 0;
        runner = head;
        if(runner == null){
          return 0;
        } else if(runner != null){
          return 1 + tailSize(head.getNode());
        } else{
          return 0;
        }
      }
     
      //to get the size of the tail, helper method for size
      private int tailSize(Node tail){
        if(tail == null){
          return 0;
        }else{
          return 1 + tailSize(tail.getNode());
        }
      }
     
      /* inserts a String s into position pos of the current list 
       * if pos < 0 it inserts to the front of the list
       * if pos > size() it inserts to the end of the list
       * returns the actual position that s is added to */
      public int insert(String s, int pos){
        if(pos <= 0){
          this.insert(s);
          return 0;
        }else if(pos >= this.size()){
          Node n = getPos(head,(this.size()-1));
          n.setNext(new Node(s));
          return (this.size() - 1);
        } else {
          Node n1 = getPos(head, pos);
          Node n2 = getPos(head, (pos-1));
          Node n = new Node(s,n1);
          n2.setNext(n);
          return pos;
        }
      }
     
      /* inserts a String s to the front of the current list 
       * returns the position that the String was inserted to  */
      public int insert(String s){
        if(head == null){
          //System.out.println("entered head == null");
          runner = head;
          Node n = new Node(s);
          head = n;
          return 0;
        } else {
          //System.out.println("entered head != null");
          runner = head;
          Node next = new Node(s, runner);
          head = next;
          return 0;
        }
      }
     
     
      /* removes and returns the String in position pos 
       * or if pos is not in the range 0..size()-1, returns null and does not modify the list */
      public String remove(int pos){
        if(pos == 0){
          return this.remove();
        }else if(pos >= this.size()){
          return null;
        } else {
          Node n1 = getPos(head, pos);
          Node n2 = getPos(head, (pos-1));
          n2.setNext(n1.getNode());
          return n1.getData();
        }
      }
     
      /* removes and returns the String in the front of the list 
       * or returns null if the list is empty */
      public String remove(){
        runner = head;
        head = head.getNode();
        return runner.getData();
      }
     
     
      /* returns the String at position pos in the list 
       * or returns null if pos is not in the range 0..size()-1 
       * The list is never modified */  
      public String look(int pos){
        return getPos(head,pos).getData();
      }
     
      //to get Node at the position in the list
      private Node getPos(Node n, int i){
        if(i == 0){
          //System.out.println("In n==0");
          return head;
        }else if( i >= this.size()){
          //System.out.println("In i>size");
          return null;
        }else{
          //System.out.println("In else");
          position = position + 1;
          if(i == (position - 1)){
            position = 1;
            return n.getNode();
          }else{
            n = n.getNode();
            return getPos(n,i);
          }
        }
      }
     
      /* returns a String representation of the list.  
       * The returned String consists of all the Strings in the list, in order,
       * with a "|" (pipe) between each String. 
       * For example, if list = "cat" -> "dog" -> "eel" then the String representation
       * would be "cat|dog|eel"
       * No extra spaces are added */
       @Override
      public String toString(){
         if(head == null){
           return "";
         } else{
           return head.getData() + helper(head.getNode());
         }
      }
     
       //helper method for toString
       private String helper(Node n){
         if(n == null){
           return "";
         } else{
           return "|" + n.getData() + helper(n.getNode());
         }
       }
     
    }

    LinkedList Abstract:
    /* Abstract class for an ordered list of Strings 
     * 
     * Strings in the list have a position, starting at 0 and
     * ending with size()-1.  (Similar to the index of an array)
     */
    public abstract class LinkedListABS{
     
      /* head is the first node in the linked list */
      protected Node head;
     
     
      /* checks if list is empty or not 
       * return true if the list is empty and false otherwise*/
      public abstract boolean isEmpty();
     
      /* returns the number os Strings in the list */
      public abstract int size();
     
      /* inserts a String s into position pos of the current list 
       * if pos < 0 it inserts to the front of the list
       * if pos > size() it inserts to the end of the list
       * returns the actual position that s is added to */
      public abstract int insert(String s, int pos);
     
      /* inserts a String s to the front of the current list 
       * returns the position that the String was interred to  */
      public abstract int insert(String s);
     
     
      /* removes and returns the String in position pos 
       * or if pos is not in the range 0..size()-1, returns null and does not modify the list */
      public abstract String remove(int pos);
     
      /* removes and returns the String in the front of the list 
       * or returns null if the list is empty */
      public abstract String remove();
     
     
      /* returns the String at position pos in the list 
       * or returns null if pos is not in the range 0..size()-1 
       * The list is never modified */  
      public abstract String look(int pos);
     
     
      /* returns a String representation of the list.  
       * The returned String consists of all the Strings in the list, in order,
       * with a "|" (pipe) between each String. 
       * For example, if list = "cat" -> "dog" -> "eel" then the String representation
       * would be "cat|dog|eel"
       * No extra spaces are added */
      @Override
      public String toString(){
        return "";
      }
     
     
    }

    copy class:
    public class CopyLinkedList{
     
      public static LinkedListABS copy(LinkedListABS list, int start, int end){
        // purpose : makes a copy of a consecutrive section of a linked list
        // input : a list of strings, two integer with start < end
        //         assume that     0 <= start < size()
        //                     start <  end   < size() + 1 
        // output : a "new" list consisting of the same strings that are found
        //          in the input list from positions start to end - 1.
        //          or, retyurn null if start/end are not valid (violating the assumed ranges above)
        // example: list = {s0,s1,s2,s3,s4,s5,s6,s7}
        //          copy(list, 2, 5) -> {s2,s3,s4}
        LinkedListABS copied = new LinkedList();
        for(; start<end; end--){
          copied.insert(list.look(end-1));
        }
        return copied;
      }
     
    }


  2. #2
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,543
    Thanks
    24
    Thanked 298 Times in 281 Posts

    Default Re: Mergesort with linkedlist using recursion

    You seem to have a lot of print statements. Are you able to also provide the printed output?
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

  3. #3
    Junior Member
    Join Date
    Nov 2013
    Posts
    9
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Re: Mergesort with linkedlist using recursion

    I've updated my code and realized that I would create a LinkedListABS s inside the 2 main if statements in the sort method and had a return statement under it, which I think caused the problem. I have commented them out:
    if(ordered[0].size() > 2){
          System.out.println("Entered ordered[0].size() > 2");
          /*LinkedListABS s =*/ sort(ordered[0]);
          //return s;

    but still I'm only getting:
    order is eel|sheep|goat|mouse

Similar Threads

  1. Replies: 4
    Last Post: September 3rd, 2013, 11:03 AM
  2. Need help with a part in a recursion LinkedList question
    By ZenithX in forum Algorithms & Recursion
    Replies: 3
    Last Post: November 2nd, 2011, 05:17 AM
  3. MergeSort not working Helppp please :(
    By colombianita2089 in forum What's Wrong With My Code?
    Replies: 4
    Last Post: May 17th, 2010, 08:56 PM
  4. Quick Question about Mergesort
    By Shadow703793 in forum Algorithms & Recursion
    Replies: 4
    Last Post: March 4th, 2010, 04:48 PM
  5. MergeSort
    By mgutierrez19 in forum Algorithms & Recursion
    Replies: 3
    Last Post: March 3rd, 2010, 07:46 PM