Quicksort in PHP

Die Funktion sortiert ein Array. Aber sie ist überflüssig, denn es gibt eine Schnellere Funktion, die auch funktioniert, wenn String-Keys dabei sind.
siehe arsort(array $ar);
[OT] Ach schade, der Doku vorlese-Service fehlt immernoch -.- [/OT]

brauchst du eine funktionserklärung, wie quicksort funktioniert?
oder wie?

hab dieses jahr in "industrielle informationstechnik" mehrere algorithmen gelernt. könnte dir da sicher was erklären.

oder versteht ich dich falsch?

<?php


$array = array(6,4,2,1,0,7,3,5,8 ) ;


function quick_sort($array)
{
if (count($array) <= 1) return $array; //nur 1 element? -> Array bereits sortiert!


$key = $array[0]; // Pivot-Element -> Welche sind kleiner, welche größer?
$left_arr = array(); // Hier kommen alle kleineren rein
$right_arr = array(); //Hier kommen alle größeren rein
for ($i=1; $i<count($array); $i++){ // Das gesamte Array durchgehen
if ($array[$i] <= $key) // Ist das Element kleiner als das Pivotelement?
$left_arr[] = $array[$i]; // ---------- In das linke, kleinere Array schreiben
else // Sonst
$right_arr[] = $array[$i]; // --------- In das rechte, größere Array schreiben
}
$left_arr = quick_sort($left_arr); // Alle kleineren Elemente auf dieselbe Art sortieren
$right_arr = quick_sort($right_arr); // Alle größeren Elemente auf dieselbe Art sortieren


return array_merge($left_arr, array($key), $right_arr); // Array zusammenfügen. kleinere Elemente + Pivotelement + größere Elemente
}


$sortiert = quick_sort($array);


foreach($sortiert as $val)
{
echo $val . '<br> <br/>';
}


?>

Es gibt zwar bessere Wege, ein Array nach Quicksort zu sortieren, aber um Algorithmik zu lernen ist das akzeptabel.

Wenn dich das interessiert: Sieh dir Heapsort an

Immer wieder gerne
Kannst dich gerne wieder melden (vor allem bei Algorithmik <3) ;D

Das ist ein bisschen doof, den mit O(n) Extra-Speicher zu implementieren, lieber auf left-array und right-array verzichten und nur Bereiche eines einzigen Arrays betrachten, damit geht das locker mit logarithmischen Speicher.

Zitat von The User

Das ist ein bisschen doof, den mit O(n) Extra-Speicher zu implementieren, lieber auf left-array und right-array verzichten und nur Bereiche eines einzigen Arrays betrachten, damit geht das locker mit logarithmischen Speicher.

Ich denke, hier geht es darum, Algorithmik zu lernen und nicht darum perfekte Algorithmen zu implementieren.
Wir haben die Speicherverwaltung auch in der Schule angerissen.
Aber das einzige, wo es mit Speicher knapp werden könnte, wäre Microprozessor-Programmierung. Und das ist mit PHP nur schwer möglich

Quicksort lohnt sich nur bei vielen Elementen, und wenn du ein paar tausend Elemente sortierst, dann ist es ein Unterschied, ob du die alle doppelt im Speicher hast oder nicht.
Andererseits: Die ganzen Array-Funktionen von PHP sind genauso schrottig, da sollte man nicht erwarten, dass es jemand besser macht, der es gerade erst lernt. Irgendwie sind diese Funktionen so ausgelegt, dass man möglichst ineffizient programmiert. Andererseits möchte man vllt. unabhängig von der Programmiersprache auch mal wissen, wie man einen bestimmten Algorithmus in-place hinbekommt.

<?php
function quicksortimpl(array &$arr, $beg, $end)
{
    if($end - $beg <= 1)
        return;
    $pivot = $arr[$beg];
    $pivotpos = $beg;
    for($i = $end-1; $i != $pivotpos; )
    {
        if($arr[$i] < $pivot)
        {
            $arr[$pivotpos] = $arr[$i];
            $arr[$i] = $arr[++$pivotpos];
            $arr[$pivotpos] = $pivot;
        }
        else
            --$i;
    }
    quicksortimpl(&$arr, $beg, $pivotpos);
    quicksortimpl(&$arr, $pivotpos + 1, $end);
}
function &quicksort(array $arr)
{
    quicksortimpl(&$arr, 0, count($arr));
    return $arr;
}
?>

Dann kann man entweder quicksort($array) oder quicksort(&$array) verwenden, je nachdem, ob man die unsortierte Version behalten möchte.

Hast schon Recht, dass das in der PHP-Praxis egal ist, aber man will ja Algorithmik lernen.

un jetzt vergleich die komplexität deines codes mal mit der des anderen ;D (aus der sicht eines anfängers, nicht aus deiner)

Komplexität...
Average Case:
Meiner: O(n log n) Laufzeit, O(log n) Speicher
Vorheriger: O(n log n) Laufzeit, O(n) Speicher
Worst Case:
Meiner: O(n^2) Laufzeit, O(n) Speicher
Vorheriger: O(n^2) Laufzeit, O(n^2) Speicher
...

Komplexität vom Verständnis her...

Naja, ich kann zum Ausgleich einen Kommentar hinzufügen. *g*

<?php
function quicksortimpl(array &$arr, $beg, $end)
{
    if($end - $beg <= 1)
        return; // Arrays mit Länge <= 1 sind immer sortiert
    $pivot = $arr[$beg]; // Pivot-Element
    $pivotpos = $beg; // Position des Pivot-Elements
    for($i = $end-1; $i != $pivotpos; )
    { // Elemente, die kleiner als das Pivot sind,
       // aber dahinter stehen, werden vertauscht,
       // daher die Schleife rückwärts
        if($arr[$i] < $pivot)
        {
            $arr[$pivotpos] = $arr[$i]; // Element hinter der alten Pivot-Position
            $arr[$i] = $arr[++$pivotpos]; // wird auf die aktuelle Position gelegt
            $arr[$pivotpos] = $pivot; // Pivot nun eins weiter rechts
        }
        else
            --$i; // Wenn kein Fehlstand: weiter nach links
    }
    quicksortimpl(&$arr, $beg, $pivotpos); // Links vom Pivot sortieren
    quicksortimpl(&$arr, $pivotpos + 1, $end); // Rechts vom Pivot sortieren
}
function &quicksort(array $arr)
{
    quicksortimpl(&$arr, 0, count($arr)); // Aufruf mit Bereichsangabe
    return $arr;
}