[PHP]Bubblesort werkt niet

[CRiMiNaL]

Mijn bubble sort functie werkt niet, geen errors, maar de inhoud van de array word
NIET gesorteerd teruggezet. Nou staat hieronder de door mij zelf geschreven bubblesort functie, maar mischien zie ik iets over het hoofd.

PHP:

function bubsort($on_array)
{
$count = count($on_array);
$l = $count;
$l2 = $count / 2;
for ($k = 0;$k == $l2; $k++)
    {
    for ($m = 1;$m == $l; $m = $m + 2)
        {
        $o = $m - 1;
        $p = $o + 2;
        $n = $m + 2;
        if($on_array[$m] >> $on_array[$n])
            {
            $temp1 = $on_array[$n];
            $temp2 = $on_array[$p];
            $on_array[$n] = $on_array[$m];
            $on_array[$p] = $on_array[$o];
            $on_array[$m] = $temp1;
            $on_array[$o] = $temp2;
            }
        }
    }
$ges_array = $on_array;
return $ges_array;
}

de code is een beetje een zooitje, maar dat komt omdat de array eigenlijk gebaseerd is op een kommatext die als volgt ingedeeld is :
A1;A2;B1;B2; ect.
dat zorgt er dus voor dat als ik de kommatext explode dat ik een array gevuld krijg met

PHP:

Array[1] = A1;
Array[2] = A2;
Array[3] = B1;
Array[4] = B2;

en als ik ze wil sorteren ik dus alle 2 de waardes moet verplaatsen, i.p.v 1.
Ik denk dat ik gewoon iets over het hoofd zie, maar het ongaat me even wat, wie weet de oplossing

[Verwijderd]

Als ik even heel vlug kijk moet regel 11

code:

 if($on_array[$m] >> $on_array[$n])

niet dit zijn?

code:

 if($on_array[$m] > $on_array[$n])

[ Voor 6% gewijzigd door Verwijderd op 04-03-2004 14:12 ]

[Helox-in-a-box]

je for-while statement is volgens mij verkeerd.

dus:

PHP:

for ($k = 0;$k < $l2; $k++) 
    { 
    for ($m = 1;$m < $l; $m = $m + 2)

[NMe]

Helox-in-a-box schreef op 04 maart 2004 @ 14:13:
je for-while statement is volgens mij verkeerd.

dus:

PHP:

for ($k = 0;$k < $l2; $k++) 
    { 
    for ($m = 1;$m < $l; $m = $m + 2)

Klopt. Zoals TS het heeft gedaan komt ie de eerste for lus niet eens in, laat staan de tweede. Een for moet je lezen als een while:

PHP:

for ($k = 0;$k == $l2; $k++)
  //doe iets

is hetzelfde als:

PHP:

$k = 0;
while ($k == $l2) {
  //doe iets
  $k++;
}

Zoals je zo misschien beter kan zien is $k bij de eerste stap NOOIT gelijk aan $l2, dus komt ie niet eens in je loop.

[CRiMiNaL]

groot gelijk hebben jullie, een stomme fout die ik over het hoofd had gezien. ik zal met een soort UNTIL in me hoofd. Weet ook niet waar dat vandaan kwam
Werken doet ie alleen nog niet helemaal, 'k ga er dus nog even naar kijken.

[ Voor 20% gewijzigd door CRiMiNaL op 04-03-2004 14:28 ]

[Helox-in-a-box]

van Basic, daar isset een For-Until maar bij PHP isset een For-While

[NMe]

Helox-in-a-box schreef op 04 maart 2004 @ 15:00:
van Basic, daar isset een For-Until maar bij PHP isset een For-While

Kan ook uit Pascal komen... Zelfs C heeft een implementatie van een 'until' (do....while (expressie)).

[Helox-in-a-box]

Zelfs C heeft een implementatie van een 'until' (do....while (expressie)).

Das geen For-X he

[ Voor 9% gewijzigd door Helox-in-a-box op 04-03-2004 15:33 ]

[NMe]

Helox-in-a-box schreef op 04 maart 2004 @ 15:32:
Das geen For-X he

Daar had ook niemand het over.

Even tussendoor: waarom gebruik je bubblesort als er zoveel andere (snellere) algoritmes te vinden zijn? Bekijk quicksort of mergesort eens.

[CRiMiNaL]

ik gebrukte bubblesort omdat die eigenlijk het bekendste bij mij is, en omdat ik verwachte nog tegen genoeg problemen aan te gaan lopen tijdens dit "projectje".
Wat nu ook blijkt dat als ik de array sorteer d.m.v het volgende stukje code de array op sommige plaatsen gewoon leeg is.

PHP:

function bubsort($on_array)
{
$count = count($on_array);
$l = $count;
$l2 = $count / 2;
for ($k = 1;$k <= $l2; $k++)
    {
    $m = 1;
    for ($x = 1;$x <= $l2; $x++)
        {
        $o = $m - 1;
        $p = $m + 1;
        $n = $m + 2;
        if($on_array[$m] > $on_array[$n])
            {
            $temp1 = $on_array[$n];
            $temp2 = $on_array[$p];
            $on_array[$n] = $on_array[$m];
            $on_array[$p] = $on_array[$o];
            $on_array[$m] = $temp1;
            $on_array[$o] = $temp2;
            }
        $m = $m + 2;
        }
    }
$ges_array = $on_array;
return $ges_array;
}

een array die ik er zo instop (gescheiden door ";") :
154;59,36;111;34,78;105;24,87
komt er zo uit
;;105;24,87;111;34,78;59,36;154

go figure

[ Voor 4% gewijzigd door CRiMiNaL op 04-03-2004 16:03 ]

[bigbeng]

Misschien is een array index wel 0-based. Ik heb weinig ervaring met PHP, dus ik weet het niet zeker.

[Soultaker]

Dat is 'ie zeker.

[NMe]

Bubblesort gaat als ik me niet vergis volgens dit principe:

PHP:

for ($i = 0; $i <= $count - 2; $i++) {
  for ($j = 0; $j <= $i; $j++) {
    //sorteer
  }
}

Iets dergelijks in ieder geval. In de binnenste lus moet je de variabele uit de buitenste betrekken.

edit:
En zoals je ziet moet je inderdaad beginnen met 0.

[ Voor 14% gewijzigd door NMe op 04-03-2004 16:34 ]

[CRiMiNaL]

bigbeng schreef op 04 maart 2004 @ 16:23:
Misschien is een array index wel 0-based. Ik heb weinig ervaring met PHP, dus ik weet het niet zeker.

die gebruik ik ook, kijk maar naar de variabele $o die wijst naar index 0; dus ga ik daarvanuit.

NMe84 schreef op 04 maart 2004 @ 16:33:
Bubblesort gaat als ik me niet vergis volgens dit principe:

PHP:

for ($i = 0; $i <= $count - 2; $i++) {
  for ($j = 0; $j <= $i; $j++) {
    //sorteer
  }
}

Iets dergelijks in ieder geval. In de binnenste lus moet je de variabele uit de buitenste betrekken.

edit:
En zoals je ziet moet je inderdaad beginnen met 0.

De logica snap ik hier niet in want de eerste keer $i = 0 dus word ie maar 1 keer uitgevoerd ?

[Grijze Vos]

de variabelen $n en $p heb je helemaal niet nodig voor een bubblesort.

[NMe]

Misschien heb je wat aan een oude bubblesort van mij:

PHP:

  for ($i = $lengte - 1; $i >= 0; $i--)
    for ($j = 1; $j <= $i - 1; $j++)
       if ($lijst[$j] > $lijst[$j + 1]) {
           $lijst[$j]     := $lijst[$j] + $lijst[$j + 1];
           $lijst[$j + 1] := $lijst[$j] - $lijst[$j + 1];
           $lijst[$j]     := $lijst[$j] - $lijst[$j + 1];
         }

edit:
Ik zie dat die zelfs op een gekunstelde manier zonder hulpvariabele werkt. Mooi meegenomen.

[ Voor 17% gewijzigd door NMe op 04-03-2004 16:55 ]

[CRiMiNaL]

Grijze Vos schreef op 04 maart 2004 @ 16:46:
de variabelen $n en $p heb je helemaal niet nodig voor een bubblesort.

Als je de moeite had gedaan om m'n posts te lezen had je gezien van wel. Ik pas de bubblesort methode toe om de 2 indexen. Verschuif daarbij de bijbehorende vorige index mee.

[ Voor 6% gewijzigd door CRiMiNaL op 04-03-2004 16:54 ]

[Grijze Vos]

Mijn excuses, dat had ik niet goed gelezen.

Dus als ik het goed begrijp wil je sorteren op A1, B1, etc, en A2, B2 etc moeten daarbij steeds naast hun 'vriendje' blijven staan?

(Als mijn aanname klopt van wat je nu wil, dan is dit een goede oplossing:)

PHP:

$test_array = array(5,"hoort bij 5",3,"hoort bij 3", 2, "hoort bij 2", 4, "hoort bij 4");

function BubbleSort2($arr)
{
  if(is_array($arr))
  {
    $n = count($arr);
    for($i=0; $i < $n; $i = $i + 2)
    {
      for($j=0; $j < $n - $i - 2; $j = $j + 2)
      {
        if($arr[$j] > $arr[$j+2])
        {
          $tmp = $arr[$j];
          $arr[$j] = $arr[$j+2];
          $arr[$j+2] = $tmp;

          $tmp = $arr[$j+1];
          $arr[$j+1] = $arr[$j+3];
          $arr[$j+3] = $tmp;
        }
      }
    }
  }
  return $arr;
}

print_r($test_array);
$nieuwe_array = BubbleSort2($test_array);
print_r($nieuwe_array);

test output:

code:

Array
(
    [0] => 5
    [1] => hoort bij 5
    [2] => 3
    [3] => hoort bij 3
    [4] => 2
    [5] => hoort bij 2
    [6] => 4
    [7] => hoort bij 4
)
Array
(
    [0] => 2
    [1] => hoort bij 2
    [2] => 3
    [3] => hoort bij 3
    [4] => 4
    [5] => hoort bij 4
    [6] => 5
    [7] => hoort bij 5

[ Voor 77% gewijzigd door Grijze Vos op 04-03-2004 17:20 ]

[CRiMiNaL]

deze werkt inderdaad een stuk beter, Bedankt voor je hulp.

[stekkel]

Waarom gebruik je de php functies niet om arrays te sorteren? Volgens mij zijn de interne php sort functies behoorlijk geoptimaliseerd.

[Verwijderd]

stekkel schreef op 04 maart 2004 @ 19:17:
Waarom gebruik je de php functies niet om arrays te sorteren? Volgens mij zijn de interne php sort functies behoorlijk geoptimaliseerd.

Dit vind ik zelf wel tegenvallen. Met arrays van redelijke grootte kom je een heel eind, maar arrays met een lengte van >250.000 vind php toch niet leuk, is mijn ervaring.

[Cavorka]

Ach... het lijkt me dan ook niet dat je op een webpagina een array van >250000 elementen gaat sorteren, plus dat daarbij komt dat dan je eigen code heus niet sneller zal zijn dan de ingebakken stuff (vermoed ik, gebaseerd op ervaring).

[Soultaker]

Ik denk niet dat de standaard sorteerfuncties bijzonder geoptimaliseerd zijn, maar ze zijn wel geschreven in C in plaats van in PHP zelf. Een algoritme geschreven in PHP moet instructie voor instructie geinterpreteerd worden en het is dan ook moeilijk voor te stellen dat een in PHP geschreven sorteerfunctie zelfs maar in de buurt komt van de snelheid van de standaardfuncties, tenzij de situatie zo anders is dat de standaardfuncties eigenlijk niet geschikt zijn.

[sjokki]

Dus een zelf geschreven bubblesort zou voor 250.000 items efficiënter zijn dan de qsort van PHP zelf?

Misschien wordt het tijd dat je de PHP-developers dan even een handje helpt met een bugreport oid

[Grijze Vos]

In dit geval gaat het om een array dat op een niet-standaard manier gesorteerd wordt. (Jullie maken dezelfde foutieve aanname als ik daarstraks deed.)

Een bubblesort hier toepassen kan prima, als de arrays niet al te groot worden.

[stekkel]

Je zou natuurlijk ook een array_chunk kunnen gebruiken (na de explode) om de paren bij elkaar te houden en daarna een usort toepassen op de multidimensionale array die onstaan is door de array_chunk functie.

[Verwijderd]

sjokki schreef op 04 maart 2004 @ 21:25:
Dus een zelf geschreven bubblesort zou voor 250.000 items efficiënter zijn dan de qsort van PHP zelf?

Misschien wordt het tijd dat je de PHP-developers dan even een handje helpt met een bugreport oid

Ik sorteer die +250.000 items niet met bubblesort Enig idee hoe lang dat duurt? 'k gebruik er mergesort voor.

[NMe]

sjokki schreef op 04 maart 2004 @ 21:25:
Dus een zelf geschreven bubblesort zou voor 250.000 items efficiënter zijn dan de qsort van PHP zelf?

Misschien wordt het tijd dat je de PHP-developers dan even een handje helpt met een bugreport oid

Er is niemand die een snellere sorteringsmethode heeft bedacht dan ongeveer met de orde O(n^2), dus veel sneller dan een merge- of quicksort geschreven in PHP kan het niet zijn. En zoveel verschil zit er kwa snelheid ook weer niet tussen een zelfgeschreven functie en een standaardfunctie van PHP.

[Cavorka]

NMe84 schreef op 05 maart 2004 @ 10:13:
[...]
En zoveel verschil zit er kwa snelheid ook weer niet tussen een zelfgeschreven functie en een standaardfunctie van PHP.

Tsja, dat hangt van de definitie van 'zoveel' af, persoonlijk vind ik het verschil namelijk echt heel erg groot, ik heb vaak genoeg zelf functies geschreven die er al in zaten (voornamelijk array operaties) en de functies die er in zitten zijn echt ordes van grootte sneller hoor:
bijvoorbeeld zelf door een array heen whilen en dan zoeken, of array_search gebruiken scheelde bijvoorbeeld bij mij een factor 6 (!!).

[NMe]

Cavorka schreef op 05 maart 2004 @ 12:08:
[...]
Tsja, dat hangt van de definitie van 'zoveel' af, persoonlijk vind ik het verschil namelijk echt heel erg groot, ik heb vaak genoeg zelf functies geschreven die er al in zaten (voornamelijk array operaties) en de functies die er in zitten zijn echt ordes van grootte sneller hoor:
bijvoorbeeld zelf door een array heen whilen en dan zoeken, of array_search gebruiken scheelde bijvoorbeeld bij mij een factor 6 (!!).

Daarom moet je ook een _goed_ zoekalgoritme gebruiken. Door een array heen lopen in een while lus (oftwel: brute force programmeren) is inderdaad meestal behoorlijk traag in verhouding met een goed geschreven recursief algoritme. Er zijn op het internet aardig wat zoekalgoritmes te vinden die veel sneller werken, en daar zal die factor van het snelheidsverschil _veel_ lager uitpakken. Toch ben ik het met je eens dat een ingebouwde PHP functie waarschijnlijk sowieso sneller is, maar misschien is het makkelijker te maken met je eigen functie of iets dergelijks.

Voor mensen die geïnteresseerd zijn in het optimaliseren van algoritmes is er overigens een goed boek op de markt, namelijk "The Design and Analysis of Algorithms". Ik weet de auteur zo snel niet meer, maar het zal vast wel op bol.com oid staan. In dit boek wordt aan de hand van pseudocode uitgelegd hoe een goed (vaak recursief) algoritme tot stand komt. Het mooie aan dit boek is, dat er geen programmeertaal bij gemoeid is, dus in welke taal je ook programmeert, aan dit boek heb je wel wat.
(Hmm, ik lijk wel een verkoper zo... Naja, tis dan ook een goed boek. )

[Soultaker]

Wat een onzin. In een ongesorteerde lijst kun je niet efficiënt zoeken: je moet altijd alle elementen een keer bekijken. Feit is dat array_search dat ook doet en dat vrijwel zeker sneller kan, omdat de code voor de while-lus niet geïnterpreteerd hoeft te worden.

Hetzelfde geldt voor sorteeralgoritmes. Er bestaan geen zinnige algemeen bruikbare sorteeralgoritmes met een lagere complexiteit dan O(N log(N)) dus het lijkt me sterk dat je een algoritme kunt schrijven dat in het algemeen sneller werkt dan de standaardfunctie.

Als je specifieke kennis hebt over de inhoud van je array (bijvoorbeeld, alle elementen staan al op de goede plek, behalve de eerste 10) dan zou het misschien kunnen dat je zelf een efficiënter sorteeralgoritme kunt schrijven, maar dat dan nog alleen maar omdat je geen equivalent algoritme hebt geschreven, maar een ander, meer op jou situatie toegespitst algoritme. Meestal valt daar echter geen winst bij te behalen; als er een standaardfunctie bestaat die ongeveer doet wat jij wil, gebruik die dan, dat scheelt in snelheid, robuustheid en de tijd die je kwijt bent aan het programmeren.

[Grijze Vos]

Soultaker, PHP interpreteert de code 1x @ runtime, en daarna niet meer hoor. Tis niet dat ie bij elke slag in je lus weer gaat interpreteren.

[stekkel]

Grijze Vos schreef op 05 maart 2004 @ 14:01:
Soultaker, PHP interpreteert de code 1x @ runtime, en daarna niet meer hoor. Tis niet dat ie bij elke slag in je lus weer gaat interpreteren.

Ja, maar de reden van het snelheidsverschil tussen eigen sorteer algoritmes in php en interne php sorteer functies heeft te maken met het feit dat de compiler niet kan zien dat het stukje code een sorteer functie betreft en daardoor heel veel onnodige tussenstappen introduceerd die niet aanwezig zijn bij het direct aanspreken van de interne sort functie.

Verder ben ik nog steeds van mening dat er voor het originele probleem geen custom zoek functie nodig is omdat het probleem met standaard functies ook op te lossen was. Zie mijn vorige post.

[ Voor 14% gewijzigd door stekkel op 05-03-2004 15:06 ]

[Grijze Vos]

stekkel schreef op 05 maart 2004 @ 15:04:
[...]

Ja, maar de reden van het snelheidsverschil tussen eigen sorteer algoritmes in php en interne php sorteer functies heeft te maken met het feit dat de compiler niet kan zien dat het stukje code een sorteer functie betreft en daardoor heel veel onnodige tussenstappen introduceerd die niet aanwezig zijn bij het direct aanspreken van de interne sort functie.

Dat snap ik ook wel. Feit dat de interne functies in C zijn geschreven scheelt ook nogal.

Verder ben ik nog steeds van mening dat er voor het originele probleem geen custom zoek functie nodig is omdat het probleem met standaard functies ook op te lossen was. Zie mijn vorige post.

Als de TS deze oplossing graag ziet, no harm done toch.