algorithms
Differences
This shows you the differences between two versions of the page.
algorithms [2009/03/06 21:01] – created moritz | algorithms [2009/03/10 18:30] (current) – Add mergesort moritz | ||
---|---|---|---|
Line 54: | Line 54: | ||
return; | return; | ||
} | } | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | |||
+ | ==== Mergesort ==== | ||
+ | This implementation is rather ugly, however, it seems to work. | ||
+ | <code java> | ||
+ | package ch.ethz.da.serie3; | ||
+ | |||
+ | /** | ||
+ | * Sample implementation of 2 way natural merge sort.. | ||
+ | | ||
+ | * @author Moritz Hoffmann | ||
+ | | ||
+ | */ | ||
+ | public class Mergesort { | ||
+ | |||
+ | private int sLength = 0; | ||
+ | |||
+ | private int[] source; | ||
+ | |||
+ | private int sStart = -1; | ||
+ | |||
+ | private int[] target; | ||
+ | |||
+ | /** | ||
+ | * Construct new sorter instance. | ||
+ | | ||
+ | * @param v | ||
+ | | ||
+ | | ||
+ | */ | ||
+ | public Mergesort(int[] v) { | ||
+ | source = v; | ||
+ | target = new int[source.length]; | ||
+ | } | ||
+ | |||
+ | public int[] getValues() { | ||
+ | return source; | ||
+ | } | ||
+ | |||
+ | /** | ||
+ | * Sort the array the object was created with. | ||
+ | */ | ||
+ | public void sort() { | ||
+ | resetRun(); | ||
+ | boolean swap = true; | ||
+ | while (sStart + sLength + 1 < source.length) { | ||
+ | nextRun(); | ||
+ | if (sStart > source.length || sLength == source.length - 1) { | ||
+ | swap = false; | ||
+ | break; | ||
+ | } | ||
+ | int s = sStart; | ||
+ | int l = sLength; | ||
+ | nextRun(); | ||
+ | if (sStart < source.length) { | ||
+ | System.out.println(" | ||
+ | + ":" | ||
+ | merge(s, l); | ||
+ | // System.out.println(Arrays.toString(target)); | ||
+ | } else { | ||
+ | System.arraycopy(source, | ||
+ | resetRun(); | ||
+ | int[] t = target; | ||
+ | target = source; | ||
+ | source = t; | ||
+ | } | ||
+ | } | ||
+ | if (swap) { | ||
+ | int[] t = target; | ||
+ | target = source; | ||
+ | source = t; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | /** | ||
+ | * Merge the sequence sStart + sLength with the sequence described by the | ||
+ | * arguments/ | ||
+ | | ||
+ | * @param s | ||
+ | | ||
+ | * @param l | ||
+ | | ||
+ | */ | ||
+ | private void merge(int s, int l) { | ||
+ | |||
+ | // pointer to current target | ||
+ | int pv = s; | ||
+ | // pointer to the position in the first run | ||
+ | int pa = s; | ||
+ | // pointer to the position in the second run. | ||
+ | int pb = sStart; | ||
+ | |||
+ | // end of new run. | ||
+ | int ev = s + l + sLength + 2; | ||
+ | // end of first run. | ||
+ | int ea = s + l + 1; | ||
+ | // end of second run | ||
+ | int eb = sStart + sLength + 1; | ||
+ | |||
+ | // merge part | ||
+ | while (pa < ea && pb < eb) { | ||
+ | int da = source[pa]; | ||
+ | int db = source[pb]; | ||
+ | if (da <= db) { | ||
+ | target[pv] = da; | ||
+ | pa = pa + 1; | ||
+ | |||
+ | } else { | ||
+ | target[pv] = db; | ||
+ | pb = pb + 1; | ||
+ | } | ||
+ | pv = pv + 1; | ||
+ | } | ||
+ | |||
+ | // copy part | ||
+ | if (pv < ev) { | ||
+ | if (pa < ea) { | ||
+ | // first part is longer. | ||
+ | System.arraycopy(source, | ||
+ | } else { | ||
+ | // second part must be longer. | ||
+ | System.arraycopy(source, | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | /** | ||
+ | * Get the length of the next sorted sequence. Result is stored in sStart | ||
+ | * and sLength. | ||
+ | */ | ||
+ | private void nextRun() { | ||
+ | int i = sStart + sLength + 1; | ||
+ | sStart = i; | ||
+ | final int length = source.length - 1; | ||
+ | while (i < length && source[i] <= source[i + 1]) { | ||
+ | i++; | ||
+ | } | ||
+ | sLength = i - sStart; | ||
+ | } | ||
+ | |||
+ | /** | ||
+ | * Reset sStart and sLength to their initial values after reaching the end | ||
+ | * of the array. | ||
+ | */ | ||
+ | private void resetRun() { | ||
+ | sLength = 0; | ||
+ | sStart = -1; | ||
} | } | ||
} | } | ||
</ | </ | ||
algorithms.1236369719.txt.gz · Last modified: 2009/03/06 21:01 by moritz