Algorithmensammlung: Sortierverfahren: Quicksort

Quicksort

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.

C#

// 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#

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

Perl

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

Python

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

→ Siehe Algorithmus im Buch VBA in Excel

Visual Basic .NET

' 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