wiki.antiguru.de

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Algorithms ======

A small section about some algorithms I collected and wrote.

===== Sorting =====

==== Heap Sort ====
<code java>
package ch.ethz.da.vorlesung;

/**
 * Heap sort according to lecture.
 * 
 * @author Moritz Hoffmann
 * 
 */
public class Heapsort {

    private final int[] data;

    public Heapsort(int[] data) {
        this.data = data;
    }

    public void sort() {
        final int length = data.length;
        for (int i = length / 2; i >= 0; i--) {
            reorder(i, length);
        }
        for (int i = data.length - 1; i > 0;) {
            int z = data[0];
            data[0] = data[i];
            data[i] = z;
            reorder(0, --i);
        }
    }

    private void reorder(int i, int length) {
        int j = i << 1;
        while (true) {
            j = i << 1;
            if (j >= length) {
                return;
            }
            if (data[j + 1] > data[j]) {
                j++;
            }
            if (data[i] < data[j]) {
                int z = data[i];
                data[i] = data[j];
                data[j] = z;
                i = j;
            } else
                return;
        }
    }
}
</code>


==== 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
     *            The values to sort. Call {@link Mergesort#sort()} to start
     *            sorting.
     */
    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("Merging " + s + ":" + l + " with " + sStart
                        + ":" + sLength);
                merge(s, l);
                // System.out.println(Arrays.toString(target));
            } else {
                System.arraycopy(source, s, target, s, l + 1);
                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
     *            The sequence's start.
     * @param l
     *            The sequence's length.
     */
    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, pa, target, pv, ea - pa);
            } else {
                // second part must be longer.
                System.arraycopy(source, pb, target, pv, eb - pb);
            }
        }
    }

    /**
     * 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;
    }
}
</code>