AuK/Teile und Herrsche 1 SS10/JavaMerge

Wiki-Quelltext dieser Seite.

<language>Java</language>
== Javabeispiel für Mergesort ==

<code id="4bbdfcc36a146">
public class MergeSort {

	  
	    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
	       int i = lo, j = mid;
	       for (int k = lo; k < hi; k++) {
	          if      (i == mid)                 aux[k] = a[j++];
	          else if (j == hi)                  aux[k] = a[i++];
	          else if (a[j].compareTo(a[i]) < 0) aux[k] = a[j++];
	          else                               aux[k] = a[i++];
	       }

	       
	       for (int k = lo; k < hi; k++)
	          a[k] = aux[k];
	    }


	   
	    public static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {

	       // Grundfall
	    	
	       if (hi - lo <= 1) return;

	       // rekursives Sortieren jeder Hälfte
	       
	       int mid = lo + (hi - lo) / 2;
	       sort(a, aux, lo, mid);
	       sort(a, aux, mid, hi);

	       // Zusammenführen der Werte
	       
	       merge(a, aux, lo, mid, hi);
	    }


	   // Sortierung der Liste
	    
	    public void sort(Comparable[] a) {
	        int N = a.length;
	        Comparable[] aux = new Comparable[N];
	        sort(a, aux, 0, N);
	    }


	   // Untersuchung ob die Liste Sortiert ist
	    
	    public boolean isSorted(Comparable[] a) {
	        for (int i = 1; i < a.length; i++)
	            if (a[i].compareTo(a[i-1]) < 0) return false;
	        return true;
	    }

	   // Zeigen des Ergebnisses
	    
	    public void show(Comparable[] a) {
	        for (int i = 0; i < a.length; i++)
	            System.out.println(a[i]);
	    }
}
</code>