Results 1 to 4 of 4
  1. #1
    Ujemny is offline Member
    Join Date
    Nov 2013
    Location
    Poland
    Posts
    8
    Rep Power
    0

    Default MergeSort with Comparable and Lists

    Hello guys!

    I have big problem with mergesort in Java. I can't figure out why it do not works.

    I need write it on lists using Comparable. Here is piece of code:

    Java Code:
    class MergeSort{
      Comparator _comparator;
      List lista = new ArrayList<>();
      List list_temp = new ArrayList<>();
    
    
    
    MergeSort(Comparator comparator){
        _comparator = comparator;
    }
    void sort(List lista){
        this.lista = lista;
    
        mergesort(0, lista.size()-1);
    
    }
    
    void mergesort(int start, int end){
       if(start < end){
           int mid = start + (end-start)/2;
    
           mergesort(start, mid);
           mergesort(mid+1, end);
    
           merge (start, mid, end);
       }
    
    
    }
    
    void merge(int start, int mid, int end){
    
        int i = start;
        int j = mid + 1;
        int k = start;
    
        for(int h = start; h <= end; h++)
            list_temp.add(lista.get(h));
    
       while (i <= mid && j <= end) {
            if (_comparator.compare(list_temp.get(i),list_temp.get(j)) <= 0) {
                lista.set(k, list_temp.get(i)); 
                i++;
            } 
            else{
                lista.set(k, list_temp.get(j));  
                j++;
            }
           k++;
    
        while (i <= mid) {
            lista.set(k, list_temp.get(i));  
            k++;
            i++;
        }
        }
    
    
    
      }
    
     final class NaturalComparator implements Comparator{
              public static final NaturalComparator INSTANCE = new NaturalComparator();
    
              NaturalComparator(){}
    
             @Override
              public int compare(Object left, Object right) throws ClassCastException{
                      return ((Comparable) left).compareTo(right);
              }
    }

    I have tried everything, still no results. It's return list with random placed numbers.

    Thnak you for any advice!

  2. #2
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,902
    Rep Power
    25

    Default Re: MergeSort with Comparable and Lists

    How can the code be compiled and executed for testing?
    If you don't understand my response, don't ignore it, ask a question.

  3. #3
    kneitzel is offline Senior Member
    Join Date
    Feb 2014
    Posts
    447
    Rep Power
    1

    Default Re: MergeSort with Comparable and Lists

    Hi,
    Just check your merge code:
    You have to parts ... the i...mid and j...end
    As long as both have values you compare them and take the smaller value.
    Then one of moth areas is empty and you have to copy the remaining elements. You do this for the i area but not for the j part.
    So you need a while(j<=end) loop as you have this i<=mid loop.

    Konrad

    BTW: maybe you want to make your code more readable. I,j,k are really bad names. At least some comments could help understanding your code.

  4. #4
    Robel Lakwe is offline Member
    Join Date
    Jun 2014
    Posts
    2
    Rep Power
    0

    Default Re: MergeSort with Comparable and Lists

    Robel Lakwe - thanks !

Similar Threads

  1. Adding Counts to a mergesort
    By wfsteadman in forum New To Java
    Replies: 0
    Last Post: 03-26-2013, 07:31 PM
  2. Mergesort
    By pauser in forum New To Java
    Replies: 1
    Last Post: 05-09-2011, 08:33 PM
  3. mergesort recursion
    By Yakg in forum New To Java
    Replies: 13
    Last Post: 02-20-2011, 07:58 PM
  4. help with mergesort
    By desconocido in forum New To Java
    Replies: 5
    Last Post: 09-15-2010, 04:56 AM
  5. mergeSort
    By Blue_beaver in forum New To Java
    Replies: 2
    Last Post: 10-11-2009, 11:55 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
  •