喵咪社区

This is the Merge Sort algorithm that we will disucss in class. Please print it out and spend some time working through it - you should understand what this does and how it does it! Please take a print out of this code with you to class for lecture 25 (Recursion).

 

---

 

 

public class MS {

 

public static void main(String[] args) {

 

� 牋牋牋牋� int[] test1 = { 13, 26, 12, 14, 23, 25, 10, 24, 11, 19, 17, 18, 16, 20, 22, 21, 15 } ;

� 牋牋牋牋� MS.mergeSort(test1,0,test1.length-1);

� 牋牋牋牋� MS.print("sorted", test1);

}

 

public static void print(String s, int[] a) {

� 牋牋牋牋� System.out.print(s);

� 牋牋牋牋� for (int i =0; i < a.length; i++)

牋牋牋 牋牋牋牋牋牋牋牋 System.out.print(" "+a[i]);

� 牋牋牋牋� System.out.println() ;

}

 

 

public static void mergeSort(int[] anArray, int first, int last) {

� 牋牋牋牋� int size = (last - first) + 1 ;

� 牋牋牋牋� if ( size > 1) {

牋牋 牋牋牋牋牋牋牋牋牋 int frontsize = size/2 ;

牋牋 牋牋牋牋牋牋牋牋牋 int backsize = size - frontsize ;

牋牋 牋牋牋牋牋牋牋牋牋 int[] front = new int[frontsize] ;

牋牋 牋牋牋牋牋牋牋牋牋 int[] back� = new int[backsize] ;

牋牋 牋牋牋牋牋牋牋牋牋 int i;

牋牋 牋牋牋牋牋牋牋牋牋 for (i=0; i < frontsize; i++)

牋牋牋牋牋 牋牋牋牋牋牋牋牋牋牋牋牋 front[i] = anArray[first + i] ;

牋牋 牋牋牋牋牋牋牋牋牋 for (i=0; i < backsize;� i++)

牋牋牋牋牋 牋牋牋牋牋牋牋牋牋牋牋牋 back[i]� = anArray[first + frontsize + i] ;

牋牋 牋牋牋牋牋牋牋牋牋 MS.mergeSort(front,0,frontsize-1);

牋牋 牋牋牋牋牋牋牋牋牋 MS.mergeSort(back, 0,backsize -1);

牋牋 牋牋牋牋牋牋牋牋牋 MS.merge(front,back,anArray,first,last) ;

� 牋牋牋牋� }

}

 

public static void merge(int[] front, int[] back, int[] anArray, int first, int last) {

牋� 牋牋牋� int fIndex = 0 ; // front index

牋� 牋牋牋� int bIndex =0 ;� // back� index

牋� 牋牋牋� int i = first ;牋� // index in anArray in which to place next element

牋�

牋� 牋牋牋� while (( fIndex < front.length) && (bIndex < back.length)) {

牋牋牋 牋牋牋牋牋牋牋牋 if (front[fIndex] < back[bIndex]) {

牋牋牋牋 牋牋牋牋牋牋牋牋牋牋牋牋牋 anArray[i] = front[fIndex] ;

牋牋牋牋 牋牋牋牋牋牋牋牋牋牋牋牋牋 i++ ;

牋牋牋牋 牋牋牋牋牋牋牋牋牋牋牋牋牋 fIndex++ ;

牋牋牋 牋牋牋牋牋牋牋牋 }

牋牋牋 牋牋牋牋牋牋牋牋 else {

牋牋牋牋 牋牋牋牋牋牋牋牋牋牋牋牋牋 anArray[i] = back[bIndex] ;

牋牋牋牋 牋牋牋牋牋牋牋牋牋牋牋牋牋 i++ ;

� 牋牋牋�牋牋牋牋牋牋牋牋牋牋牋牋牋 bIndex++ ;

牋牋牋 牋牋牋牋牋牋牋牋 }

牋� 牋牋牋� }

牋牋

牋� 牋牋牋� while ( fIndex < front.length) {

牋牋牋牋 牋牋牋牋牋牋牋 anArray[i] = front[fIndex] ;

牋牋牋牋 牋牋牋牋牋牋牋 i++ ;

牋牋牋牋 牋牋牋牋牋牋牋 fIndex++ ;

牋� 牋牋牋� }

牋牋

牋� 牋牋牋� while ( bIndex < back.length) {

牋牋牋牋 牋牋牋牋牋牋牋 anArray[i] = back[bIndex] ;

牋牋 牋牋牋牋牋牋牋牋牋 i++ ;

牋牋牋牋 牋牋牋牋牋牋牋 bIndex++ ;

牋� 牋牋牋� }

}

 

}