~Java4Beginners~
~Java4Beginners~

Sortierung

Was beim Umgang mit Arrays gerne verwendet wird, sind sämtliche Arten von Sortieralgorithmen, um den Inhalt eines Arrays sortiert auszugeben.

Es gibt eine Vielzahl von Sortieralgorithmen, welche in Java verwirklicht werden können. Es gibt auch bereits Klassen in Java, welche die Sortierung beinhalten. Für das bessere Verständnis ist es allerdings unabdingbar, dass zumindeste in paar Sortieralgorithmen in der Funktionsweise bekannt sind. Die Umsetzung in Java-Code ist nach Verständnis der Funktionsweise dann nur noch "Fleissarbeit"

Klasse Arrays

Java stellt uns eine Klasse Arrays zur Verfügung, mit welcher wir Arrays sortieren können. Der Aufruf ist hierbei sehr einfach.

    Arrays.sort(zuSortierendesArray);

Beispiel


import java.util.Arrays;

/**
 * Einfaches int-Array mit Klasse Arrays sortieren
 * @author Markus Badzura
 */
public class asort 
{
    public static void main(String[] args) {
        int[] zahl = new int[] {2,4,3,1,8,6,5};
        Arrays.sort(zahl);
        for (int i = 0;i < zahl.length; i++)
        {
            System.out.println(zahl[i]);
        }
    }
}
    

Verschiedene Sortieralgorithmen

  • Bubblesort
  • Gnomesort
  • Insertionsort
  • Quicksort
  • Binary Tree Sort
  • Selectionsort
  • Bogosort
  • Bucketsort
  • Radixsort
  • .....

Bubblesort

Bei diesem sehr einfachen Algoritmus werden Zahlenpaare miteinander verglichen und bei Bedarf ausgetauscht.

In der Bubble-Phase wird die Eingabe-Liste von links nach rechts durchlaufen. Dabei wird in jedem Schritt das aktuelle Element mit dem rechten Nachbarn verglichen. Falls die beiden Elemente das Sortierkriterium verletzen, werden sie getauscht. Am Ende der Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe am Ende der Liste.

Die Bubble-Phase wird solange wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da die restliche zu sortierende Eingabe keine größeren bzw. kleineren Elemente mehr enthält.


    /**
     * Sortieralgorithmus Bubblesort
     * @param zahlen Array mit Int-Werten
     * @return durchsortierte Array-Liste
     */
    public static int[] sortBubble(int[] zahlen)
    {
        int temp;
	for(int i=1; izahlen[j+1]) 
                {
                    temp=zahlen[j];
                    zahlen[j]=zahlen[j+1];
                    zahlen[j+1]=temp;
		}				
            }
        }
        return zahlen;
    }

Insertionsort

Das Vorgehen ist mit der Sortierung eines Spielkartenblatts vergleichbar. Am Anfang liegen die Karten des Blatts verdeckt auf dem Tisch. Die Karten werden nacheinander aufgedeckt und an der korrekten Position in das Blatt, das in der Hand gehalten wird, eingefügt. Um die Einfügestelle für eine neue Karte zu finden, wird diese sukzessive (von links nach rechts) mit den bereits einsortierten Karten des Blattes verglichen. Zu jedem Zeitpunkt sind die Karten in der Hand sortiert und bestehen aus den zuerst vom Tisch entnommenen Karten.

    /** 
     * Sortieralgorithmus Insertion-Sort
     * @param zahlen mit Int-Werten
     * @return durchsortiertes Array mit Int-Werten
     */
    public static int[] sortInsertion(int[] zahlen) 
    {
	int temp;
        for (int i = 1; i < zahlen.length; i++) 
        {
            temp = zahlen[i];
            int j = i;
            while (j > 0 && zahlen[j - 1] > temp) 
            {
                zahlen[j] = zahlen[j - 1];
		j--;
            }        
            zahlen[j] = temp;
	}
	return zahlen;
    } 

Selectionsort

Die Funktionsweise von Selectionsort stellt sich so dar: Man hat ein Array in dem sich die zu sortierenden Daten befinden. Nun teilt man das Array im Geiste in zwei Teile. Der erste Teil soll den sortierten Teil darstellen, der zweite Teil den unsortierten. Da am Anfang noch nichts sortiert ist, stellt dementsprechend das gesamte Array den unsortierten Teil dar.

Nun sucht man das kleinste Element im Array und vertauscht es mit dem ersten Element. Nun befindet sich also das erste Element im sortierten Bereich und die restlichen Elemente im unsortierten. Nun wird wieder im unsortierten Teil nach dem kleinsten Element gesucht und dieses nun hinter dem ersten Element im sortierten Bereich eingefügt. Dies geht so lange, bis alle Elemente im sortierten Bereich und keins mehr im unsortierten Bereich sich befindet. Wer nach der Größe sortieren will, angefangen mit dem größten Element, sucht statt dem kleinsten, immer nach dem größten Element.

    /**
     * Sortieralgorithmus Selection Sort
     * @param zahlen Array mit Int-Werten
     * @return durchsortiertes Array mit IntWerten
     */
    public static int[] sortSelection(int[] zahlen) 
    {
	for (int i = 0; i < zahlen.length - 1; i++) 
        {
            for (int j = i + 1; j < zahlen.length; j++) 
            {
		if (zahlen[i] > zahlen[j]) 
                {
                    int temp = zahlen[i];
                    zahlen[i] = zahlen[j];
                    zahlen[j] = temp;
		}
            }
	}
	return zahlen;
    }   
nach oben Java4Beginners -- Seitenversion 1.0 -- Stand: 2017-05-17