WCM Forum - quicksort erklärung

WCM Forum (http://www.wcm.at/forum/index.php)

- Programmierung (http://www.wcm.at/forum/forumdisplay.php?f=17)

- - quicksort erklärung (http://www.wcm.at/forum/showthread.php?t=135955)

quicksort erklärung

PHP-Code:


		
			
<?php

$data = file("data.txt");

foreach($data as $dat)

    echo "$dat | ";



echo "

[b]Daten werden sortiert...
";



$vergleich=0;

$tausch=0;

function quick($links,$rechts) {

    global $data,$pivot,$vergleich,$tausch;

    $i = $links;

    $j = $rechts;

    $pivot = $data[round(($i+$j)/2)];

    while($i<$j) {

        while(($data[$i]+0) < ($pivot+0)) {

            $vergleich++;

            $i++;

        }

        while(($data[$j]+0) > ($pivot+0)) {

            $vergleich++;

            $j--;

        }

        if($i<=$j) {

            $tausch++;

            $temp = $data[$i];

            $data[$i] = $data[$j];

            $data[$j] = $temp;

            $i++;

            $j--;

        }

    }

    if($links < $j)

        quick($links,$j);

    if($i < $rechts)

        quick($i,$rechts);

}

quick(0,(count($data)-1));

echo "
$vergleich Vergleiche und $tausch Vertauschungen waren nötig!
";

echo "Daten sind sortiert und werden ausgegeben...[/b]

";

foreach($data as $dat)

    echo "$dat | ";

?>

Was macht das genau:
if($links < $j)
quick($links,$j);
if($i < $rechts)
quick($i,$rechts);
???

Und bitte nicht einfach nur so eine Antwort wie, "die Grenzen neu setzen" oder "die Funktion rekursiv aufrufen" - ich muss das genau wissen, sodass ich es auch erklären kann!

Die erste if-Schleife ist mir klar, die zählt so lange durch, bis j=links (links ist am Anfang fix 0 und j wird immer kleiner), aber was passiert dann? wie werden jeweils die rechten Hälften (bei Pivot=Mitte) durchsucht?

PS: Gibt es eine andere Möglichkeit aus irgendeiner Variablen eine "Zahl" zu machen als ($var+0) ?? -> Das Problem ist, dass wenn das nicht so geschrieben wird, es so sortiert wird: 1,10,110,2,3,30,4

Prüfung oder Referat, um eine bessere Note zu bekommen? ;) :lol:

Also zum Quicksort solltest Du via Google genug gute Erklärungen bekommen (Auf Wikipedia kann ich ja dank flinx nicht mehr verweisen ;) ).

Nein, nur Matura ;)

Die Erklärung auf wikipedia kenne ich, aber die hilft mir nicht. Mir gehts konkret um die Rekursion - die verstehe ich nicht ganz! Die erste if-Schleife verstehe ich, da rückt die rechte Grenze immer weiter nach links, bis sie gleich ist der linken Grenze und dann wird die nächste if-Schleife ausgeführt, aber was macht die genau???

PS: Gegoogelt hab ich auch schon genug, aber ich konnte noch keine gute Erklärung finden.

Ok, ein Freund hat es mir jetzt erklären können!

Mein Problem war, dass ich vergessen habe, dass, nachdem in der Funktion quick() nochmal die Funktion quick() aufgerufen wurde, die "erste" Funktion quick() ganz normal weitergeht... Ich hab das immer vergessen und das Ende praktisch unter den Tisch fallen lassen, wodurch mein Problem zustande kam, dass ich nicht wusste, wie das ganze dann in die andere Richtung zurückgeht!