Sortierverfahren

Ich habe das ganze in eine grafische Oberfläche gesteckt und die Fenster, in denen sortiert wird, durch eine Klasse SortierSortierFrame realisiert. Darin werden auch die Zufallszahlen erstellt und an die einzelnen Sortierverfahren weitergegeben.

Die Klassen für die Sortierverfahren werden als Nachkommen der Klasse MethodenFuerAlle erstellt und müssen das interface Sortierverfahren impementieren. Vermutlich ist das ein bisschen mit Kanonen auf Spatzen geschossen, aber das sah mir nach einer guten Gelegenheit aus, sowohl Vererbung als auch die interfaces zu üben und in ein Projekt einzubauen. Hier die Klasse und das Interface:

package Sortieralgorithmen;
public class MethodenFuerAlle {
    public void tausche (int a [], int m, int n ) {
        int c = a[m];
        a[m] = a[n];
        a[n] = c;
    }
}

package Sortieralgorithmen;
public interface Sortierverfahren { 
    public int [] sortiere (int [] zahlen);
    public String getName();
    public String getSource();
}

Man beachte hier, dass Java lediglich call by value versteht. Das bedeutet, dass die Methode nicht folgendermaßen erstellen kann:

public void tausche (int a, int b) { ... }

In diesem Falle würde ein Aufruf tausche (zahlen[i], zahlen[j]) nichts nutzen, da die Inhalte zwar in der Methode getauscht werden, die Vertauschung aber nicht mit zurückgegeben werden kann. Der Kopf

public void tausche (int a[], int m, int n) { ... }

sorgt aber dafür, dass als value die Referenz auf die Reihung und die beiden Positionen in der Reihung übergeben werden. So kann in tausche direkt auf die echte Reihung zugegriffen werden.

Hier nun in Java…

package Sortieralgorithmen;
 
/**
 *
 * @author claudius
 */
public class Auswahl1 extends MethodenFuerAlle implements Sortierverfahren {
 
    public String getName() {
        return ("Sortieren durch Auswahl - I");
    }
 
    public String getSource() {
        [...]
    }
 
    /** Creates a new instance of Auswahl1 */
    public Auswahl1() {
    }
 
    public int posmin (int [] zahlen) {
        // liefert die Position des kleinsten Elements
        int pos = 0;
 
        for (int i=1; i<zahlen.length; i++) {
            if (zahlen[i]<zahlen[pos]) {
                pos = i;
            }
        }
 
        return (pos);      
    }
 
    public int max (int [] zahlen) {
        // liefert das größte Element
        int max = zahlen[0];
 
        for (int i=1; i<zahlen.length; i++) {
            if (zahlen[i]>max) {
                max = zahlen[i];
            }
        }
        return (max);      
    }
 
    public int [] sortiere (int [] zahlen) {
        int [] zahlen2 = new int [zahlen.length];
        int max = max(zahlen)+1;
 
        for (int i=0; i<zahlen.length; i++) {
            zahlen2[i] = zahlen [posmin(zahlen)];
            zahlen [posmin(zahlen)] = max;
        }
 
        return (zahlen2);
    }
 
}

package Sortieralgorithmen;
 
/**
 *
 * @author claudius
 */
public class Auswahl2 extends MethodenFuerAlle implements Sortierverfahren {
 
    public String getName() {
        return ("Sortieren durch Auswahl - II");
    }
 
    public String getSource() {
        [...]
    }
 
    /** Creates a new instance of Auswahl2 */
    public Auswahl2() {
    }
 
    public int posmin (int [] zahlen, int a, int b) {
        // liefert die Position des kleinsten Elements im Bereich a bis b
        int pos = a;
 
        for (int i=a; i<=b; i++) {
            if (zahlen[i]<zahlen[pos]) {
                pos = i;
            }
        }
        return (pos);      
    }
 
    public int [] sortiere (int [] zahlen) {
        for (int i=0; i<zahlen.length-1; i++) {
            int kleinste = posmin(zahlen,i+1,zahlen.length-1);
            if (zahlen[i]>zahlen[kleinste]) {
                tausche (zahlen,i,kleinste);
            }
        }
        return (zahlen);
    }
 
}

package Sortieralgorithmen;
 
/**
 *
 * @author claudius
 */
public class Einfuegen extends MethodenFuerAlle implements Sortierverfahren {
 
    public String getName() {
        return ("Sortieren durch Einfügen");
    }
 
    public String getSource() {
        [...]
    }
 
    /** Creates a new instance of Einfuegen */
    public Einfuegen() {
    }
 
    public int posmin (int [] zahlen, int a, int b) {
        // liefert die Position des kleinsten Elements im Bereich a bis b
        int pos = a;
 
        for (int i=a; i<=b; i++) {
            if (zahlen[i]<zahlen[pos]) {
                pos = i;
            }
        }
        return (pos);      
    }
 
    public void fuegeEin (int [] zahlen, int von, int nach) {
        /* von ist immer größer als nach!
         *der Bereich von 'nach' bis 'von-1' wird um 1 nach rechts geschoben. */
        int merke = zahlen[von];
        for (int i=von; i>nach; i--) {
            zahlen[i] = zahlen[i-1];
        }
        zahlen[nach] = merke;
    }
 
    public int [] sortiere (int [] zahlen) {
        int hinten = zahlen.length-1;
        for (int i=0; i<hinten; i++) {
            fuegeEin (zahlen, posmin(zahlen,i,hinten), i);
        }
        return (zahlen);
    }
 
}

package Sortieralgorithmen;
 
/**
 *
 * @author claudius
 */
public class Bubblesort extends MethodenFuerAlle implements Sortierverfahren {
 
    public String getName() {
        return ("Bubblesort");
    }
 
    public String getSource() {
        [...]
    }
 
    /** Creates a new instance of Bubblesort */
    public Bubblesort() {
    }
 
    public int [] sortiere (int [] zahlen) {
        for (int i=zahlen.length-2; i>=0; i--) {
            for (int j=0; j<=i; j++) {
                if (zahlen[j]>zahlen[j+1]) {
                    tausche (zahlen,j,j+1);
                }
            }
        }
        return (zahlen);
    }
 
}

package Sortieralgorithmen;
 
/**
 *
 * @author claudius
 */
public class Quicksort extends MethodenFuerAlle implements Sortierverfahren {
 
    private int [] zahlen;
 
    public String getName() {
        return ("Quicksort");
    }
 
    public String getSource() {
        [...]
    }
 
    /** Creates a new instance of Quicksort */
    public Quicksort() {
    }
 
    public int posPivot (int l, int r) {        
        int pivot = zahlen[ (l+r)/2 ];
        while (true) {
            while (zahlen[l]<pivot) l++;
            while (zahlen[r]>pivot) r--;
            if (l<r) {
                tausche (zahlen, l, r);
                //l++;
                if (zahlen[l]==zahlen[r]) r--;
            }
            else
                return (l);
        }
    }
 
    public void sortiereQuick (int l, int r) {
        if (l<r) {
            int p = posPivot (l, r);
            sortiereQuick (l, p);
            sortiereQuick (p+1, r);
        }
    }
 
    public int [] sortiere (int [] zahlen) {
        this.zahlen = zahlen;
        sortiereQuick (0, this.zahlen.length-1);
        return (this.zahlen);
    }
 
}