Algorithmensammlung: Sortierverfahren: Quicksort

Aus Wikibooks

Algorithmensammlung: Sortierverfahren

Quicksort[Bearbeiten]

Quicksort wird gemeinhin als das beste Sortierverfahren in der Praxis betrachtet. Während seine Laufzeit im schlechtesten Fall beträgt, erreicht es eine mittlere Laufzeit von und ist damit nahezu optimal. Der Algorithmus arbeitet nach dem "Teile und Herrsche"-Prinzip.

Für weitere Informationen siehe  Quicksort.

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

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