Seite 1 von 2 12 LetzteLetzte
Ergebnis 1 bis 10 von 14

Thema: Quicksort in PHP

  1. #1
    HTML Newbie
    Registriert seit
    03.05.2010
    Beiträge
    3
    Danke
    0
    Bekam 0 mal "Danke" in 0 Postings

    Standard Quicksort in PHP

    Hey ho und guten Abend allerseits!

    Ich beschäftige mich im Moment mit dem Thema Quicksort, verstehe auch den Algorithmus, nur bei der Umsetzung hapert es ein wenig.
    Zu meiner bisherigen Erfahrung im Programmieren: Delphi, C++, HTML und nun PHP. Alles eher oberflächlich als tiefgründig !
    Hab zwar auch beim durchforsten des Internets einige Quellcodes gefunden, aber so richtig überzeugt bin ich noch nicht.
    Hier mal mein bestes Ergebnis aus dem Internet bezüglich Quicksort in PHP:


    <?php

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

    function quick_sort($array)
    {
    if (count($array) <= 1) return $array;

    $key = $array[0];
    $left_arr = array();
    $right_arr = array();
    for ($i=1; $i<count($array); $i++){
    if ($array[$i] <= $key)
    $left_arr[] = $array[$i];
    else
    $right_arr[] = $array[$i];
    }
    $left_arr = quick_sort($left_arr);
    $right_arr = quick_sort($right_arr);

    return array_merge($left_arr, array($key), $right_arr);
    }

    $sortiert = quick_sort($array);

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

    ?>

    Es funktioniert zwar, aber so richtig 100% komm ich damit noch nicht klar ... !
    Wäre nett, wenn jemand mal ein paar Minuten für mich Zeit hätte und mir den Quellcode erklären könnte!

    Vielen dank schonmal im Voraus, mfg Zenephret
    Achtung: Dies ist ein alter Thread im HTML und Webmaster Forum
    Diese Diskussion ist älter als 90 Tage. Die darin enthaltenen Informationen sind möglicherweise nicht mehr aktuell. Erstelle bitte zu deiner Frage ein neues Thema im Forum !!!!!
    Geändert von Zenephret (03.05.2010 um 21:32 Uhr)

  2. #2
    Kaiser(in)
    Registriert seit
    29.03.2009
    Ort
    1011 1111 1011 WorldWideWeb
    Beiträge
    2.439
    Danke
    2
    Bekam 6 mal "Danke" in 6 Postings

    Standard AW: 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]
    Der, der weiß dass er nichts weiß, weiß mehr als der, der nicht weiß, dass er nichts weiß.
    Wer nach etwas fragt, geht grundsätzlich das Risiko ein, es auch zu bekommen!

  3. #3
    Jedi Ritter Avatar von Dodo
    Registriert seit
    26.04.2008
    Ort
    Wien
    Alter
    27
    Beiträge
    3.774
    Danke
    0
    Bekam 0 mal "Danke" in 0 Postings
    Blog-Einträge
    1

    Standard AW: Quicksort in PHP

    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?
    Something big is coming. And there will be pirates and ninjas and unicorns...

  4. #4
    HTML Newbie
    Themenstarter

    Registriert seit
    03.05.2010
    Beiträge
    3
    Danke
    0
    Bekam 0 mal "Danke" in 0 Postings

    Standard AW: Quicksort in PHP

    Also, ich brauch einen Quicksort-Algorithmus in PHP.
    Aber da ich nur wenig Erfahrung in PHP habe, weiß ich nicht, welche Variablen welche Werte haben.
    Bzw. wird mit $key = $array [0] das Pivotelement festgelegt ? Wie kann ich das Pivotelement in die Mitte setzen?
    Ich hab keine Ahnung wofür die einzelnen Variablen stehen. Was wann eine Funktion ist oder nicht z.B. $right_arr = quick_sort(left_arr);
    Wird jetzt der Varibale eine Funktion zugeordnet?
    Hoffe, dass es jetzt verstädnlicher ist
    danke für die schnellen Antworten, thumbs up
    Zene

  5. #5
    Jedi Ritter Avatar von Dodo
    Registriert seit
    26.04.2008
    Ort
    Wien
    Alter
    27
    Beiträge
    3.774
    Danke
    0
    Bekam 0 mal "Danke" in 0 Postings
    Blog-Einträge
    1

    Standard AW: Quicksort in PHP

    PHP-Code:
    <?php

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

    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
    Something big is coming. And there will be pirates and ninjas and unicorns...

  6. #6
    HTML Newbie
    Themenstarter

    Registriert seit
    03.05.2010
    Beiträge
    3
    Danke
    0
    Bekam 0 mal "Danke" in 0 Postings

    Standard AW: Quicksort in PHP

    Alles klar, jetzt blick ich durch .
    Danke dir vielmals auch für den Tip (Heapsort), schönen Abend noch!
    mfg Zene

  7. #7
    Jedi Ritter Avatar von Dodo
    Registriert seit
    26.04.2008
    Ort
    Wien
    Alter
    27
    Beiträge
    3.774
    Danke
    0
    Bekam 0 mal "Danke" in 0 Postings
    Blog-Einträge
    1

    Standard AW: Quicksort in PHP

    Immer wieder gerne
    Kannst dich gerne wieder melden (vor allem bei Algorithmik <3) ;D
    Something big is coming. And there will be pirates and ninjas and unicorns...

  8. #8
    Forum Guru Avatar von The User
    Registriert seit
    28.10.2007
    Ort
    Zwischen Pazifik und Atlantik...
    Beiträge
    4.044
    Danke
    0
    Bekam 0 mal "Danke" in 0 Postings

    Standard AW: Quicksort in PHP

    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.

  9. #9
    Jedi Ritter Avatar von Dodo
    Registriert seit
    26.04.2008
    Ort
    Wien
    Alter
    27
    Beiträge
    3.774
    Danke
    0
    Bekam 0 mal "Danke" in 0 Postings
    Blog-Einträge
    1

    Standard AW: Quicksort in PHP

    Zitat Zitat von The User Beitrag anzeigen
    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
    Something big is coming. And there will be pirates and ninjas and unicorns...

  10. #10
    Forum Guru Avatar von The User
    Registriert seit
    28.10.2007
    Ort
    Zwischen Pazifik und Atlantik...
    Beiträge
    4.044
    Danke
    0
    Bekam 0 mal "Danke" in 0 Postings

    Standard AW: Quicksort in PHP

    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-Code:
    <?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(&$arr0count($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.

Stichworte

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •