Results 1 to 6 of 6

Thread: Merge Sort Help

  1. #1
    Hollywood is offline Member
    Join Date
    Jan 2008
    Posts
    8
    Rep Power
    0

    Default Merge Sort Help

    Hello everyone, I am new to the Forum.
    I have a homework problem implementing the merge sort using generic list not w/ an array. I didn't see anything online about using it w/ list. I was wondering if you could give me a hand w/ my code. I understand everything untill the actual merging of the list, and just can't seem to get the algorithm. Keep in mind I am sorting the list as is and not copying it into sub-lists as to keep efficiency. Thanks for any of your help.
    Java Code:
    package sort;
    
    import utilities.containers.*;
    
    /**
     * This class subdivides a list of elements into a subsequences of elements,
     * then merges the single elements in order to form a single ordered list.
     */
    
    public class MergeSort <E>{
      
      /**
       * MergeSort Starting algorithm.
       *      Require: a non-empty list of elements to sort.
       *      Ensure: returns the input list in increasing order.
       * 
       */
      
      public void mergesort(List <E> toSort){
        
        if (toSort.size()<=1){
          /*Do Nothing*/
        }
        else{
          
          int low = 0;
          int high = toSort.size()-1;
          
          sort(toSort,low,high);
          
          }
        
      }
     
      /**
       * Private sort method used to break down input list into single list elements.
       * 
       */
      
      private void sort(List <E> toSort,int low,int high){
        
        if(low==high){
          /*Do Nothing*/
        }
        else{
          int middle = (high+low)/2;
          
          sort(toSort,low,middle);
          sort(toSort,middle,high);
          merge(toSort,low, middle, high);
          
        }
      }
      
      /**
       * Private merge method used to merge and order two generic lists.
       */
      
      private void merge(List<E> toSort,int low, int middle, int high){
        
      /**
       *This is the area I don't get.
       */
        
      }
      
      /**
       * Swaps two generic elements of a list.
       */
      
      private void swap(List<E> toSort,int left, int right){
      
        E temp = toSort.get(left);
        toSort.set(left,toSort.get(right));
        toSort.set(right,temp);
        
      }
      
    }//end of class MergeSort

  2. #2
    Hollywood is offline Member
    Join Date
    Jan 2008
    Posts
    8
    Rep Power
    0

    Default

    Bump. anyone?

  3. #3
    gibsonrocker800's Avatar
    gibsonrocker800 is offline Senior Member
    Join Date
    Nov 2007
    Location
    New York
    Posts
    143
    Rep Power
    0

    Default

    I'm not too good at generic programming, but i believe that E will have to be a Comparable because how else will the MergeSort know how to sort these elements. So, you have to write something like this for the class declaration:

    Java Code:
    public class MergeSort<E extends Comparable>
    Saying E extends Comparable means E extends or implements the following class or interface, so in this case, we're saying E implements Comparable.
    You may need to incorporate this information somewhere in your class, because i don't understand how else you can sort Objects if they can't be compared.

    There are many other things you can do with these limitations. They are called wildcards.
    Java Code:
       ? extends E
    The specified type must be a subclass of E


    Java Code:
       ? super E
    The specified type must be a superclass of E

    Java Code:
       ?
    All types


    Hope that information helps you, and anyone interested in generic programming.
    Last edited by gibsonrocker800; 01-29-2008 at 06:59 AM.

  4. #4
    hardwired's Avatar
    hardwired is offline Senior Member
    Join Date
    Jul 2007
    Posts
    1,576
    Rep Power
    9

    Default

    Java Code:
    import java.util.*;
    
    public class MergeSortRx {
        public <T extends Comparable<? super T>> void mergesort(List<T> toSort) {
            if (toSort.size()<=1){
                /*Do Nothing*/
            }
            else{
                int low = 0;
                int high = toSort.size()-1;
                print(toSort, "original collection");
                sort(toSort, low, high);
            }
        }
    
        private <T extends Comparable<? super T>> void sort(List<T> toSort,
                                                            int low, int high) {
            if(low == high){
                /*Do Nothing*/
                return;
            }
            else{
                int middle = (high+low)/2;
                sort(toSort, low, middle);
                sort(toSort, middle+1, high);
                merge(toSort, low, middle, high);
            }
        }
    
        private <T extends Comparable<? super T>> void merge(List<T> toSort,
                                   int low, int middle, int high) {
            int loCount = low;
            int midCount = middle;
            int hiCount = middle+1;
    
            while(loCount <= midCount && hiCount <= high) {
                T lo = toSort.get(loCount);
                T hi = toSort.get(hiCount);
                int compare = lo.compareTo(hi);
                if(compare < 0) {    // lo < hi
                    loCount++;
                } else {             // lo >= hi
                    T temp = hi;
                    for(int j = hiCount-1; j >= loCount; j--)
                        toSort.set(j+1, toSort.get(j));
                    toSort.set(loCount, temp);
                    loCount++;
                    midCount++;
                    hiCount++;
                }
            }
        }
    
        private <T> void print(List<T> list, String title) {
            System.out.println(title);
            for(int j = 0; j < list.size(); j++) {
                System.out.print(list.get(j));
                if(j < list.size()-1)
                    System.out.print(", ");
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
            MergeSortRx ms = new MergeSortRx();
            int[] ints = { 5, 7, 9, 3, 16, 12, 4 };
            List<Integer> list = new ArrayList<Integer>();
            for(int j = 0; j < ints.length; j++)
                list.add(Integer.valueOf(ints[j]));
            ms.mergesort(list);
            ms.print(list, "after sorting");
            System.out.println("--------------");
            String[] s = "bdoaplvjertmxn".split("(?<=[\\w])");
            List<String> sList = Arrays.asList(s);
            ms.mergesort(sList);
            ms.print(sList, "after sorting");
        }
    }

  5. #5
    Hollywood is offline Member
    Join Date
    Jan 2008
    Posts
    8
    Rep Power
    0

    Default

    Hardwired, I just need to find a way to use your merge in my merge.

    Ok I am sorry I forgot to implement an order I am not using Comparable.
    Here is my new code. I have some of the merge algorithm but am a little stuck.
    I have tested the split method and it is splitting fine it is when I merge, and I have more than two elements of each half when some aren't fully comparing w/ the others.

    I am inputing this list of Integers "8,4,1,6,4,3,2,6"
    my output so far looks like this "1,2,3,6,6,4,4,8"
    4 is not after 6
    Java Code:
    package sort;
    
    import utilities.containers.*;
    
    /**
     * This class subdivides a list of elements into a subsequences of elements,
     * then merges the single elements in order to form a single ordered list.
     */
    
    public class ListUtilities {
      
      /**
       * MergeSort Starting algorithm.
       *      Require: a non-empty list of elements to sort.
       *      Ensure: returns the input list in increasing order.
       */
      
      public static <E> List <E> mergesort(Order<E> order,List <E> toSort){
        
        List<E> result = toSort.copy();
        
        if (toSort.size()<=1){
          /*Do Nothing*/
        }
        else{
                
          int low = 0;
          int high = result.size()-1;
    
          split(order,result,low,high);
    
        }
    
        return result;
        
      }
     
      /**
       * Private split method used to break down input list into single list elements.
       * 
       */
      
      private static <E> void split(Order<E> order,List <E> toSort,int low,int high){
        
        if(low==high){
          /*Do Nothing*/
          //return split;
        }
    
        else{
          
          int middle = (high+low)/2;
          
          split(order,toSort,low,middle);
          split(order,toSort,middle+1,high);
          merge(order,toSort,low, middle, high);
          
        }
      }
      
      /**
       * Private merge method used to merge and order two generic lists.
       * As elements are merged they are sorted according to order.
       */
      
      private static <E> void merge(Order<E> order,List<E> toSort,int low, int middle, int high){
    
        int i = middle;
        int j = middle+1;
        
        while((low<=i)&&(j<=high)){
          if(order.inOrder(toSort.get(low),toSort.get(j))){
            low++;
          }
          else{
            swap(toSort,low,j);
            j++;
          }
        }
      }
      
      /**
       * Swaps two generic elements of a list.
       */
      
      private static <E> void swap(List<E> toSort,int left, int right){
      
        E temp = toSort.get(left);
        toSort.set(left,toSort.get(right));
        toSort.set(right,temp);
        
      }
      
    }//end of class MergeSort
    Last edited by Hollywood; 01-30-2008 at 06:23 AM.

  6. #6
    Hollywood is offline Member
    Join Date
    Jan 2008
    Posts
    8
    Rep Power
    0

    Default

    Double Post
    Last edited by Hollywood; 01-30-2008 at 06:23 AM.

Similar Threads

  1. Merge Two Xml files ????
    By alwz_nikhil in forum XML
    Replies: 5
    Last Post: 01-18-2011, 09:18 AM
  2. How to sort a list using Bubble sort algorithm
    By Java Tip in forum Algorithms
    Replies: 3
    Last Post: 04-29-2008, 08:04 PM
  3. Merge Sort in Java
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-15-2008, 07:43 PM
  4. Replies: 1
    Last Post: 03-27-2008, 05:06 PM
  5. Merge 2 button become one
    By banie in forum AWT / Swing
    Replies: 1
    Last Post: 02-17-2008, 05:26 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •