Java Forums

Main Menu
Home
Today's Posts
FAQ
Search
Contact Us

Java Network
Java Tips
Java Tips Blog

Sponsored Links





Welcome to the Java Forums.

You are currently viewing our boards as a guest which gives you limited access to view most discussions and access our other features. By joining our free community, you will:

  • have access to post topics
  • communicate privately with other members (PM)
  • not see advertisements between posts
  • have the possibility to earn one of our surprises if you are an active member
  • access many other special features that will be introduced later.

Registration is fast, simple and absolutely free so please, join our community today!

If you have any problems with the registration process or your account login, please contact us.

Reply
 
LinkBack Thread Tools Display Modes
  #1 (permalink)  
Old 01-25-2008, 05:14 PM
Member
 
Join Date: Jan 2008
Posts: 5
Hollywood is on a distinguished road
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.
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
Bookmark Post in Technorati
Reply With Quote
Sponsored Links
  #2 (permalink)  
Old 01-26-2008, 04:59 PM
Member
 
Join Date: Jan 2008
Posts: 5
Hollywood is on a distinguished road
Bump. anyone?
Bookmark Post in Technorati
Reply With Quote
  #3 (permalink)  
Old 01-29-2008, 07:56 AM
gibsonrocker800's Avatar
Senior Member
 
Join Date: Nov 2007
Location: New York
Posts: 143
gibsonrocker800 is on a distinguished road
Send a message via AIM to gibsonrocker800
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:

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.
Code:
? extends E
The specified type must be a subclass of E


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

Code:
?
All types


Hope that information helps you, and anyone interested in generic programming.
__________________
//Haha javac, can't see me now, can ya?

Last edited by gibsonrocker800 : 01-29-2008 at 07:59 AM.
Bookmark Post in Technorati
Reply With Quote
  #4 (permalink)  
Old 01-29-2008, 09:19 AM
Senior Member
 
Join Date: Jul 2007
Posts: 1,022
hardwired is on a distinguished road
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"); } }
Bookmark Post in Technorati
Reply With Quote
  #5 (permalink)  
Old 01-30-2008, 04:17 AM
Member
 
Join Date: Jan 2008
Posts: 5
Hollywood is on a distinguished road
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
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 07:23 AM.
Bookmark Post in Technorati
Reply With Quote
  #6 (permalink)  
Old 01-30-2008, 04:26 AM
Member
 
Join Date: Jan 2008
Posts: 5
Hollywood is on a distinguished road
Double Post

Last edited by Hollywood : 01-30-2008 at 07:23 AM.
Bookmark Post in Technorati
Reply With Quote
Sponsored Links
Reply


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to sort a list using Bubble sort algorithm Java Tip Algorithms 3 04-29-2008 09:04 PM
Merge Sort in Java Java Tip Algorithms 0 04-15-2008 08:43 PM
Merge Two Xml files ???? alwz_nikhil XML 3 03-28-2008 12:40 PM
How do merge two xml files into one xml? veera XML 1 03-27-2008 06:06 PM
Merge 2 button become one banie AWT / Swing 1 02-17-2008 06:26 PM


All times are GMT +3. The time now is 10:36 AM.


VBulletin, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO ©2007, Crawlability, Inc.
Copyright ©2006 - 2007, www.java-forums.org