Sortieralgorithmen

"Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen. Algorithmen bestehen aus endlich vielen, wohldefinierten Einzelschritten. Somit können sie zur Ausführung in einem Computerprogramm implementiert, aber auch in menschlicher Sprache formuliert werden. Bei der Problemlösung wird eine bestimmte Eingabe in eine bestimmte Ausgabe überführt."
Quelle: https://de.wikipedia.org/wiki/Algorithmus

Vorweg: Es ist weniger effizient die Laufzeit eines Algorithmus direkt, zum Beispiel in einer Zeiteinheit, zu messen. Es gibt zu viele Faktoren, welche die Laufzeit beeinflussen. Das könnte Hardware, Betriebssystem, Auslastung des PCs, Compiler usw. sein. Es lässt sich also keine genaue Aussage über die benötigte Zeit machen.

Um die Laufzeit von Algorithmen zu bestimmen, zählt man die benötigten Elementaroperationen eines Algorithmus in Abhängigkeit der Eingabelänge n, da diese zeitkonstante Anweisungen sind. Elementaroperationen können zum Beispiel Arrayzugriffe, arithmetische Funktionen, einfache Zuweisungen oder Vergleiche sein.

Ziel ist es nun mit Hilfe der O-Notation die beste obere Schranke der Laufzeit zu finden. Also den schlimmsten Fall (worst-case), mit den ungünstigsten Eingabedaten. In einigen Fällen wird auch der best-case bzw. average-case betrachtet.

Des weiteren wird der Speicherverbrauch untersucht. Manche Algorithmen benötigen zusätzlichen Speicherbedarf, um zum Beispiel Daten in einem Hilfsarray abzulegen.

Werbung

it-versand.com - Generalüberholt
it-versand.com - 75% Rabatt

Stabilität

Außerdem können Sortieralgorithmen stabil oder nicht stabil sein. Die Einhaltung gleicher Sortierschlüssel ist somit gewährleistet bzw. nicht. Das bedeutet, dass bei stabilen Sortieralgorithmen, Elemente mit gleichem Sortierschlüssel, vor der Sortierung die gleiche Reihenfolge aufweisen, wie danach. Instabile Sortieralgorithmen beachten die Reihenfolge gleicher Sortierschlüssel vor der Sortierung nicht. Sie können also danach vertauscht sein.
Diese Eigenschaften müssen berücksichtigt werden, um den optimalen (Sortier-)Algorithmus zu wählen.

Bubblesort

Bubblesort (Sortieren nach Aufsteigen) ist ein einfach zu verstehender Sortieralgorithmus, der häufig als Einführungsbeispiel eingesetzt wird. In der Praxis wird dieser Algorithmus eher selten benutzt, da andere Sortierverfahren ein besseres Laufzeitverhalten haben. Sortiert wird indem die Liste von links nach rechts durchlaufen wird.

Pro Schritt wird das aktuelle Element mit seinem rechten Nachbar verglichen. Wird das Sortierkriterium verletzt werden die beiden Elemente vertauscht.
Nach einem Durchlauf steht das größte bzw. kleinste Element am Schluss und muss beim nächsten Schritt nicht mehr beachtet werden. Nach jedem Durchlauf fällt also ein Element weg.

  • Bubblesort ist ein stabiler Sortieralgorithmus *
  • arbeitet in-place **
  • Laufzeit beträgt im worst-case und average-case O(n²) ***
  • Laufzeit beträgt im best-case O(n)

* Die Einhaltung der Reihenfolge von gleichen Sortierschlüsseln ist gewährleistet.

** "Ein Algorithmus arbeitet in-place bzw. in situ, wenn er außer dem für die Speicherung der zu bearbeitenden Daten benötigten Speicher nur eine konstante, also von der zu bearbeitenden Datenmenge unabhängige Menge von Speicher benötigt. Der Algorithmus überschreibt die Eingabedaten mit den Ausgabedaten."
Quelle: https://de.wikipedia.org/wiki/In-place

*** Durch das "schlechte" Laufzeitverhalten von im Worst- und Average-Case, dient der Algorithmus meist nur zu Demonstrationszwecken

Pseudocode

Bubblesort(A,n)
begin
	i := 1;
    active := true;
    while ((i < n) and (active = true))
    do begin active = false;
    		 for (j:=1 to (n-1))
             do if (A[j] > A[j+1])
             	then swap(A[j], A[j+1]);
                	 active = true;
             i = i+1;
    end;
 end;

Javacode

public static void main(String[] args) {
	bubblesort();
}
// Aufruf des Bubblesort Algorithmus
private void bubblesort() {
	Sort sorter = new Sort();
	Scanner scan = new Scanner( System.in );
	int i = 0;
	System.out.println("Wie viele Zahlen möchten Sie sortieren? ");
	int anzahl = scan.nextInt();
	int array[] = new int[anzahl];
	while(i < anzahl) {
		System.out.println("Bitte geben Sie die nächste Zahl ein: ");
		int wert = scan.nextInt();
		array[i] = wert;
		i++;
	}
	
	System.out.println("\nZu sortierendes Array: \n" + Arrays.toString(array));
	System.out.println("Schrittweise Sortierung: \n");
	sorter.bubble(array);
	System.out.println("Sortiertes Array: " + Arrays.toString(array));  
}
public void bubble(int[] inputArr) {
   boolean unsortiert=true;
   int temp;

   while (unsortiert){
	  unsortiert = false;
	  for (int i=0; i < inputArr.length-1; i++) 
		 if (inputArr[i] > inputArr[i+1]) {                      
			temp          = inputArr[i];
			inputArr[i]   = inputArr[i+1];
			inputArr[i+1] = temp;
			unsortiert = true;
		 } 
	  System.out.println(Arrays.toString(inputArr));
	  System.out.println("");
   } 
} 

Quicksort

Quicksort ist ein sehr schneller Sortieralgorithmus, daher auch sein Name. Der Algorithmus arbeitet rekursiv nach dem divide and conquer (teile und herrsche) Prinzip. Zunächst wird aus der zu sortierenden Liste ein sogenanntes Pivot Element bestimmt. Dieses Element kann beliebig gewählt werden.
Das Pivot Element trennt die Liste in 2 Teillisten. Somit entsteht eine "linke" und eine "rechte" Liste.

Alle Elemente die kleiner als das Pivot Element sind, wandern in die linke Liste, die größeren in die rechte. Hat ein Element die gleiche Größe wie das Pivot Element, wird es zufällig in eines der beiden Listen verteilt. Aus diesem Grund ist Quicksort kein stabiler Sortieralgorithmus.

Aus jeder Teilliste wird ein neues Pivot Element bestimmt, und der Vorgang wird erneut durchgeführt.

  • Quicksort ist kein stabiler Sortieralgorithmus *
  • arbeitet in-place **
  • Laufzeit beträgt im worst-case O(n²) ***
  • Laufzeit beträgt im average-case O(n*log(n))
  • Partition hat die Laufzeit O(n)

* Die Einhaltung der Reihenfolge von gleichen Sortierschlüsseln ist nicht gewährleistet.

** "Ein Algorithmus arbeitet in-place bzw. in situ, wenn er außer dem für die Speicherung der zu bearbeitenden Daten benötigten Speicher nur eine konstante, also von der zu bearbeitenden Datenmenge unabhängige Menge von Speicher benötigt. Der Algorithmus überschreibt die Eingabedaten mit den Ausgabedaten."
Quelle: https://de.wikipedia.org/wiki/In-place

*** Unter der Berücksichtigung, dass der Worst-Case sehr selten eintritt, erweist sich Quicksort in der Praxis als das schnellste Sortierverfahren.

Pseudocode

QUICKSORT(A,l,r)
begin
	if(l < r)
    then begin
    	     q := PARTITION(a,l,r)
             QUICKSORT(A,l,q)
             QUICKSORT(A,q+1,r)
       	 end
end
PARTITION(A,l,r)
begin	x := A[l];
        i := l;
        j := r;
        if(l < r)
        then active := true;
       	else active := false;
        while (active)
        do begin
                while(A[j] > x) do j := j-1;
                while(A[i] < x) do i := i+1;
                if (i < j)
                then begin
                    SWAP(A[i],A[j]);
                    j := j-1;
                    i := i+1;
                end;
             else	active := false;
         end;
         RETURN j;
end;

Javacode

public static void main(String[] args) {
	quicksort();
}
// Aufruf des Quicksort Algorithmus
private void quicksort() {
	Sort sorter = new Sort();
	Scanner scan = new Scanner( System.in );
	int i = 0;
	System.out.println("Wie viele Zahlen möchten Sie sortieren? ");
	int anzahl = scan.nextInt();
	int array[] = new int[anzahl];
	while(i < anzahl) {
		System.out.println("Bitte geben Sie die nächste Zahl ein: ");
		int wert = scan.nextInt();
		array[i] = wert;
		i++;
	}
	
	System.out.println("\nZu sortierendes Array: \n" + Arrays.toString(array));
	System.out.println("Schrittweise Sortierung: \n");
	sorter.quick(array);
	System.out.println("Sortiertes Array: " + Arrays.toString(array));  
}
public void quick(int[] inputArr) {
	if (inputArr == null || inputArr.length == 0) {
		return;
	}
	this.array = inputArr;
	length = inputArr.length;
	quickSort(0, length - 1);
}
private void quickSort(int IndexLow, int IndexHigh) {
	int i = IndexLow;
	int j = IndexHigh;
	int pivot = array[IndexLow+(IndexHigh-IndexLow)/2];
	while (i <= j) {
		while (array[i] < pivot) {
			i++;
		}
		while (array[j] > pivot) {
			j--;
		}
		if (i <= j) {
			exchangeNumbers(i, j);
			i++;
			j--;
		}
	}
	// call quickSort() method recursively
	if (IndexLow < j)
		quickSort(IndexLow, j);
	if (i < IndexHigh)
		quickSort(i, IndexHigh);
}
private void exchangeNumbers(int i, int j) {
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
	System.out.println(Arrays.toString(array));
	System.out.println("");
}

Mergesort

Mergesort arbeitet nach dem divide and conquer (teile und herrsche) Prinzip.
Im ersten Teil des Algorithmus wird die zu sortierende Liste solange rekursiv in kleinere Listen zerlegt, bis jedes Element einzeln dargestellt wird.
Im 2. Teil werden sie im Reißverschlussverfahren zusammengefügt (engl. (to) merge) und dabei sortiert. Zum Schluss hat man dann wider eine sortierte Gesamtliste

  • Mergesort ist ein stabiler Sortieralgorithmus *
  • arbeitet in der Regel nicht in-place **
  • beträgt im Worst-, Best- und Average-Case O(n*log(n)) ***

* Die Einhaltung der Reihenfolge von gleichen Sortierschlüsseln ist gewährleistet.

** "Ein Algorithmus arbeitet in-place bzw. in situ, wenn er außer dem für die Speicherung der zu bearbeitenden Daten benötigten Speicher nur eine konstante, also von der zu bearbeitenden Datenmenge unabhängige Menge von Speicher benötigt. Der Algorithmus überschreibt die Eingabedaten mit den Ausgabedaten."
Quelle: https://de.wikipedia.org/wiki/In-place

*** Mergesort benötigt jedoch für das Hilfsarray zusätzlichen Speicherplatz der Größe O(n)

Javacode

// Aufruf des Mergesort Algorithmus
private void mergesort() {
	Sort sorter = new Sort();
	Scanner scan = new Scanner( System.in );
	int i = 0;
	System.out.println("Wie viele Zahlen möchten Sie sortieren? ");
	int anzahl = scan.nextInt();
	int array[] = new int[anzahl];
	while(i < anzahl) {
		System.out.println("Bitte geben Sie die nächste Zahl ein: ");
		int wert = scan.nextInt();
		array[i] = wert;
		i++;
	}
	
	System.out.println("\nZu sortierendes Array: \n" + Arrays.toString(array));
	System.out.println("Schrittweise Sortierung: \n");
	sorter.merge(array);
	System.out.println("Sortiertes Array: " + Arrays.toString(array));  
}
public void merge(int[] inputArr) {
	this.array = inputArr;
	this.length = inputArr.length;
	this.tempMergArr = new int[length];
	mergeSort(0, length - 1);
}
private void mergeSort(int IndexLow, int IndexHigh) {
	if (IndexLow < IndexHigh) {
		int middle = IndexLow + (IndexHigh - IndexLow) / 2;
		mergeSort(IndexLow, middle);
		mergeSort(middle + 1, IndexHigh);
		mergeParts(IndexLow, middle, IndexHigh);
	}
}
private void mergeParts(int IndexLow, int middle, int IndexHigh) {
	for (int i = IndexLow; i <= IndexHigh; i++) {
		tempMergArr[i] = array[i];
	}
	int i = IndexLow;
	int j = middle + 1;
	int k = IndexLow;
	while (i <= middle && j <= IndexHigh) {
		if (tempMergArr[i] <= tempMergArr[j]) {
			array[k] = tempMergArr[i];
			i++;
		} else {
			array[k] = tempMergArr[j];
			j++;
		}
		k++;
	}
	while (i <= middle) {
		array[k] = tempMergArr[i];
		k++;
		i++;
	}
	System.out.println(Arrays.toString(array));
	System.out.println("");
}

Werbung

Maconline
Maconline
keyboard_arrow_left

Vorheriger Artikel

Datenstrukturen

Queue, Stack, einfach und doppelt verkettete Liste

Nächster Artikel

Threads

Gleichzeitige Ausführung von Programmen mittels Threads

keyboard_arrow_right

Werbung

Mit Programmier-Skills perfekt für die Zukunft aufgestellt! Die Kurse gehen schon bei 11,99 € los!
Top-Online-Kurse in „IT & Software“