Algorithmensammlung: Sortierverfahren: Quicksort

Aus Wikibooks
Wechseln zu: Navigation, Suche

Algorithmensammlung: Sortierverfahren

Quicksort[Bearbeiten]

Quicksort wird gemeinhin als das beste Sortierverfahren in der Praxis betrachtet. Während seine Laufzeit im schlechtesten Fall \mathcal{O}(n^2) beträgt, erreicht es eine mittlere Laufzeit von \mathcal{O}(n\cdot \log(n)) und ist damit nahezu optimal. Der Algorithmus arbeitet nach dem "Teile und Herrsche"-Prinzip.

Für weitere Informationen siehe  Quicksort.

Perl[Bearbeiten]

sub quicksort {
    if(!@_) {
    	return ();
    }
    else {
    	return (quicksort(grep { $_ < $_[0] } @_[1..$#_]),
    		$_[0],
    		quicksort(grep { $_ >= $_[0] } @_[1..$#_]));
    }
}

Python[Bearbeiten]

def quicksort(liste):
    if len(liste) <= 1:
        return liste
    else:
        return quicksort(filter(lambda x: x < liste[0], liste[1:])) + \
               [ liste[0] ] + \
               quicksort(filter(lambda x: x >= liste[0], liste[1:]))

Visual Basic for Applications[Bearbeiten]

→ Siehe Algorithmus im Buch VBA in Excel

Visual Basic .NET[Bearbeiten]

' Die Implementierung wurde der Pseudocode-Version des Hauptartikels nachempfunden.
Public Class Quicksort
 
    Public Shared Sub sort(ByRef array As Integer())
        quicksort(0, array.Length - 1, array)
    End Sub
    Private Shared Sub quicksort(ByVal links As Integer, ByVal rechts As Integer, ByRef daten As Integer())
        If links < rechts Then
            Dim teiler As Integer = teile(links, rechts, daten)
            quicksort(links, teiler - 1, daten)
            quicksort(teiler + 1, rechts, daten)
        End If
    End Sub
    Private Shared Function teile(ByVal links As Integer, ByVal rechts As Integer, ByRef daten As Integer()) As Integer
        Dim i As Integer = links
        'Starte mit j links vom Pivotelement
        Dim j As Integer = rechts - 1
        Dim pivot As Integer = daten(rechts)
 
        Do
            'Suche von links ein Element, welches größer als das Pivotelement ist
            While daten(i) <= pivot AndAlso i < rechts
                i += 1
            End While
 
            'Suche von rechts ein Element, welches kleiner als das Pivotelement ist
            While daten(j) >= pivot AndAlso j > links
                j -= 1
            End While
 
            If i < j Then
                Dim z As Integer = daten(i)
                daten(i) = daten(j) ' tausche daten[i] mit daten[j]
                daten(j) = z
            End If
 
        Loop While i < j 'solange i an j nicht vorbeigelaufen ist 
 
        ' Tausche Pivotelement (daten[rechts]) mit neuer endgültiger Position (daten[i])
 
        If daten(i) > pivot Then
            Dim z As Integer = daten(i)
            daten(i) = daten(rechts) ' tausche daten[i] mit daten[rechts]
            daten(rechts) = z
        End If
 
        Return i ' gib die Position des Pivotelements zurück
 
    End Function
 
End Class

C#[Bearbeiten]

// Die Implementierung wurde der Pseudocode-Version des Hauptartikels nachempfunden.
public class Quicksort
{
	public static void sort(ref int[] array)
	{
		quicksort(0, array.Length - 1, ref array);
	}
	private static void quicksort(int links, int rechts, ref int[] daten)
	{
		if (links < rechts) {
			int teiler = teile(links, rechts, ref daten);
			quicksort(links, teiler - 1, ref daten);
			quicksort(teiler + 1, rechts, ref daten);
		}
	}
	private static int teile(int links, int rechts, ref int[] daten)
	{
		int i = links;
		//Starte mit j links vom Pivotelement
		int j = rechts - 1;
		int pivot = daten[rechts];
 
		do {
			//Suche von links ein Element, welches größer als das Pivotelement ist
			while (daten[i] <= pivot && i < rechts) 
				i += 1;
 
			//Suche von rechts ein Element, welches kleiner als das Pivotelement ist
			while (daten[j] >= pivot && j > links) 
				j -= 1;
 
			if (i < j) {
				int z = daten[i];
				daten[i] = daten[j];
				// tausche daten[i] mit daten[j]
				daten[j] = z;
			}
 
		} while (i < j);
		//solange i an j nicht vorbeigelaufen ist 
 
		// Tausche Pivotelement (daten[rechts]) mit neuer endgültiger Position (daten[i])
 
		if (daten[i] > pivot) {
			int z = daten[i];
			daten[i] = daten[rechts];
			// tausche daten[i] mit daten[rechts]
			daten[rechts] = z;
		}
		return i; // gib die Position des Pivotelements zurück
	}
}

F#[Bearbeiten]

let rec quicksort (list:int list) = 
    match list with
    | [] -> []
    | head::tail -> 
        let smaller,larger = List.partition (fun y -> y <= head) tail
        quicksort smaller @ [head] @ quicksort larger