123 lines
3.2 KiB
Java
123 lines
3.2 KiB
Java
/**
|
|
* <PRE>
|
|
* MergeSort.java
|
|
*
|
|
* Revisions: 1.0 Nov. 04, 2002
|
|
* Created the MergeSort class
|
|
* 1.1 Nov. 05, 2002
|
|
* Compiled, Finished, Commented
|
|
*
|
|
* </PRE>
|
|
*
|
|
* Collaboration Statement:
|
|
* I worked on the homework assignment alone, using only
|
|
* course materials.
|
|
*
|
|
* Created with JCreatorLE, some indents are off when viewed through notepad
|
|
* or EMACS
|
|
*
|
|
* @author <A HREF="mailto:gtg184g@mail.gatech.edu">Jose Manuel Caban</A>
|
|
* @version Version 1.1, Nov. 04, 2002
|
|
*/
|
|
|
|
public class MergeSort extends AbstractSort{
|
|
|
|
////////////////
|
|
//Constructors//
|
|
////////////////
|
|
|
|
/**
|
|
*Constructor for MergeSort
|
|
*@param arrayWrap, the array to be sorted
|
|
*/
|
|
public MergeSort(ArrayWrapper arrayWrap){
|
|
super(arrayWrap);
|
|
|
|
}
|
|
|
|
///////////
|
|
//Methods//
|
|
///////////
|
|
|
|
/**
|
|
*Sort the Array
|
|
*/
|
|
public void doSort(){
|
|
Comparable[] tmpArray = new Comparable[arrayWrap.length()];
|
|
for(int i=0; i<arrayWrap.length(); i++){
|
|
tmpArray[i] = arrayWrap.get(i);
|
|
}
|
|
mergeSort(tmpArray,0,tmpArray.length-1);
|
|
}//end doSort()
|
|
|
|
/**
|
|
*Recursive Function to sort 2 arrays
|
|
*/
|
|
private void mergeSort(Comparable[] toSort, int iLeft, int iRight){
|
|
if(iLeft < iRight){
|
|
int center = (iLeft+iRight)/2;
|
|
mergeSort(toSort,iLeft,center);
|
|
mergeSort(toSort,center+1,iRight);
|
|
merge(toSort,iLeft,center+1,iRight);
|
|
}
|
|
}//end mergeSort()
|
|
|
|
/**
|
|
*Merge arrays
|
|
*/
|
|
private void merge(Comparable[] toSort, int iLeft, int iCenter, int iRight){
|
|
int iLeftCounter = iLeft;
|
|
int iRightCounter = iCenter;
|
|
int iTempCounter = iLeft;
|
|
int iLength = (iRight - iLeft) + 1;
|
|
|
|
|
|
while(iLeftCounter<=(iCenter-1) && iRightCounter<= iRight){
|
|
if(arrayWrap.get(iLeftCounter).compareTo(
|
|
arrayWrap.get(iRightCounter))<0){
|
|
toSort[iTempCounter++] = arrayWrap.get(iLeftCounter++);
|
|
}
|
|
else{//you're off your rocker if you think im gonna write the if()
|
|
toSort[iTempCounter++] = arrayWrap.get(iRightCounter++);
|
|
}
|
|
}
|
|
|
|
while(iLeftCounter <= (iCenter-1)){
|
|
toSort[iTempCounter++] = arrayWrap.get(iLeftCounter++);
|
|
}
|
|
|
|
while(iRightCounter <= iRight){
|
|
toSort[iTempCounter++] = arrayWrap.get(iRightCounter++);
|
|
}
|
|
|
|
for(int i=0; i<iLength; i++,iRight--){
|
|
arrayWrap.set(iRight,toSort[iRight]);
|
|
}
|
|
}//end merge()
|
|
|
|
|
|
/**
|
|
* Debugging main for class MergeSort.
|
|
* This method will rigorously test my code.
|
|
*
|
|
* <br><br>
|
|
* @param args a String array of command line arguments.
|
|
*/
|
|
public static void main(String[] args) {
|
|
ArrayWrapper aw = new ArrayWrapper(ArrayWrapper.getRandomIntegerArray(40));
|
|
MergeSort M$ = new MergeSort(aw); //ok, actually i HATE ppl who say M$
|
|
//except T.A.'s who say it..
|
|
|
|
for(int i=0;i<aw.length();i++){
|
|
System.out.println(aw.get(i));
|
|
}
|
|
M$.doSort();
|
|
System.out.println("\n/****Testing Now****/\n");
|
|
for(int i=0;i<aw.length();i++){
|
|
System.out.println(aw.get(i));
|
|
}
|
|
|
|
}// end of main(String[] args)
|
|
|
|
}// end of class MergeSort
|