Bubble Sort Array

idleflow

Hi,

Trying to output a ladder of scores taken from a mysql db..

this is the part that is causing an exception - any help spotting the problem is appreciated.
($positions is an array of objects which consists of specific values such as points, wins, loss etc etc.
I'm trying to sort through the objects by points and output them to a ladder type format...
Am I better of using a key/value - where object is key and its points are the value, i can then do a sort from value?

thanks.

for($pass = 1 ; $pass < count($positions); $pass++){
for($i = 0; $i < count($positions) - 1;$i++){
$teamA = $positions[$i];
$teamB = $positions[$i+1];

//line 105 if($teamA->getPoints() < $teamB->getPoints()){
$hold = $teamA;
unset($positions[$i]);
array_push($positions,$i,$team😎;
unset($positions[$i+1]);
array_push($positions,$i+1,$hold);
}
}
}

Fatal error: Call to a member function getPoints() on a non-object in W:\www\viewLadder.php on line 105

I've tested this - it is an object... i did a quick test and getPoints() prints a value.

laserlight

Let me guess, you want to sort an array according to some getPoints() method?
Complexity issues aside (bubble sort is perhaps the slowest of the O(n**2) sorting algorithms, which are slow to begin with when asymptotic growth is considered), your use of array_push is incorrect. You are actually pushing $i, $teamB, $i+1 and $hold to the end of the array.

What you really want to do is use [man]usort/man with a comparator function, say one created by [man]create_function/man.

usort($positions, create_function('$a, $b', 'return $a->getPoints() - $b->getPoints();'));

idleflow

But if i push the objects with the lowest points to the end of the array then when i output this array wont it display the team(object within the array) with the highest points first? I'm not too worried about performance at the moment... this is just a little project.

Pieman86

You're not using array_push() in the right way when swapping elements. In fact, array_push() can't really be used for swapping elements unless you're willing to do some pretty strange contortions with arrays.

Like laserlight says, bubblesort is not a good sorting algorithm, except in a few special cases, but in any case this should work:

for($pass = 1; $pass < count($positions); $pass++)
{
   for($i = 0; $i < count($positions)-1; $i++)
   {
      $teamA = $positions[$i];
      $teamB = $positions[$i+1];

  if($teamA->getPoints() < $teamB->getPoints())
  {
     $positions[$i] = $teamB;
     $positions[$i+1] = $teamA;
  }
   }
}

laserlight

But if i push the objects with the lowest points to the end of the array then when i output this array wont it display the team(object within the array) with the highest points first?

As I mentioned, you are using array_push wrongly to begin with. Not only are you appending the elements, but you are appending the indices. A more typical implementation of bubblesort would be:

$max = count($positions) - 1;
do
{
	$swap_flag = false;
	for ($i = 0; $i < $max; ++$i)
	{
		if ($positions[$i+1]->getPoints() < $positions[$i]->getPoints())
		{
			$temp = $positions[$i];
			$positions[$i] = $positions[$i+1];
			$positions[$i+1] = $temp;
			$swap_flag = true;
		}
	}
} while ($swap_flag);

I'm not too worried about performance at the moment... this is just a little project.

Well, I suggest that you take the opportunity to learn the use of [man]sort/man, [man]rsort/man, [man]asort/man, [man]ksort/man, [man]natsort/man and [man]array_multisort/man, aside from the usort() that I demonstrated.