I am slowly trying to figure out the implementation of bubble Sort, the concept is easy enough to understand. basically i have this far with it:
<?php
namespace TeamRock;
class BubbleSort
{
public function sort(array $integers)
{
if (count ($integers) > 0)
{
//if value of array is over one do this-->
for ($i = 0; $i<count($integers); $i++) //iterating through the array
{
for($j = 1; $j<count($integers);$j++)
{
//where the sorting happens
$holder = $integers[$j];
if ($integers[$j] < $integers[$j-1]){
$integers[$i] = $integers[$j-1];
$integers[$j-1] = $holder;
}
}
}
return $integers;
}
else{
return $integers;
}
}
}
Sudo Code-
//For each element in array
//Look at the element to direct right
//If the element on the left is greater than the element to the direct right
//Then we should swap these elements positions
//
//restart at start of loop until all numbers are numbered
Ok so thats the function, i wanted to write the function myself instead of using the built in php function. Im am also using phpspec to test these and have my variables defined in there heres the spec:
<?php
namespace phpspec\TeamRock;
use PhpSpec\ObjectBehavior;
class BubbleSortSpec extends ObjectBehavior
{
function it_is_initializable()
{
$this->shouldHaveType('TeamRock\BubbleSort');
}
function it_can_sort_an_array_of_four_integers()
{
$integers = [8, 4, 6, 2];
$this->sort($integers)->shouldReturn(['2, 4, 6, 8']);
}
function it_can_sort_an_array_of_five_integers()
{
$integers = [6, 11, 0, 9, 3];
$this->sort($integers)->shouldReturn([0, 3, 6, 9, 11]);
}
}
And when i run the spec this is what i get:
TeamRock/BubbleSort
15 - it can sort an array of four integers
expected [array:1], but got [array:4].
@@ -1,3 +1,6 @@
[
- 0 => ""2, 4, 6, 8"...",
+ 0 => 2,
+ 1 => 2,
+ 2 => 2,
+ 3 => 2,
]
17 $integers = [8, 4, 6, 2];
18
19 $this->sort($integers)->shouldReturn(['2, 4, 6, 8']);
20 }
21 function it_can_sort_an_array_of_five_integers()
22 {
0 vendor/phpspec/phpspec/src/PhpSpec/Matcher/IdentityMatcher.php:78
throw new PhpSpec\Exception\Example\NotEqualException("Expected [array:1]...")
1 [internal]
phpspec\TeamRock\BubbleSortSpec->it_can_sort_an_array_of_four_integers()
TeamRock/BubbleSort
21 - it can sort an array of five integers
expected [array:5], but got [array:5].
@@ -1,7 +1,7 @@
[
0 => 0,
- 1 => 3,
- 2 => 6,
- 3 => 9,
- 4 => 11,
+ 1 => 0,
+ 2 => 0,
+ 3 => 3,
+ 4 => 3,
]
23 $integers = [6, 11, 0, 9, 3];
24
25 $this->sort($integers)->shouldReturn([0, 3, 6, 9, 11]);
26 }
27 }
0 vendor/phpspec/phpspec/src/PhpSpec/Matcher/IdentityMatcher.php:78
throw new PhpSpec\Exception\Example\NotEqualException("Expected [array:5]...")
1 [internal]
phpspec\TeamRock\BubbleSortSpec->it_can_sort_an_array_of_five_integers()
71% 28% 7
2 specs
7 examples (5 passed, 2 failed)
19ms
Any help or pointer would be greatly appreciated
I do have an insertion sort working fine, thats why there are some passed, the ones that have failed are for the bubble.
Once again im very new to this so give me a little breathing space for missing any basic stuff. im trying to get this in my brain :P
There are some errors in your code. First, the algorithm:
$holder = $integers[$j];
if ($integers[$j] < $integers[$j-1]){
$integers[$i] = $integers[$j-1];
$integers[$j-1] = $holder;
}
The second assignment above should read:
$integers[$j] = $integers[$j-1];
because you are swapping $integers[$j] with $integers[$j-1] if they are in the wrong order (I am sure this is just a typo).
This error probably makes the second test case in the specs fail.
The first test case:
function it_can_sort_an_array_of_four_integers()
{
$integers = [8, 4, 6, 2];
$this->sort($integers)->shouldReturn(['2, 4, 6, 8']);
}
should read:
$this->sort($integers)->shouldReturn([2, 4, 6, 8]);
Notice this is an array of four integers while your code checks the result against an array containing one string.
Further improvements:
You run count($integers) passes through the array checking for pairs of neighbour values that are in the wrong order. While this is the maximum number of passes needed, a lot of times it completes earlier.
A better implementation is to keep a flag that remembers after each pass if there was and swapping done and exit the loop when there was none (because the array is already sorted).
Something like this:
public function sort(array $integers)
{
// Call count() only once before the loop because it doesn't change
$count = count($integers);
do {
// Didn't swap any neighbour values yet in this loop
$swapped = FALSE;
// Run through the list, swap neighbour values if needed
for ($j = 1; $j < $count; $j ++)
{
// Check neighbour values
// Initialize $holder only when it is needed (to swap values)
if ($integers[$j] < $integers[$j - 1]) {
// Swap the values
$holder = $integers[$j];
$integers[$i] = $integers[$j - 1];
$integers[$j - 1] = $holder;
// Remember we did at least one swap on this pass
$swapped = TRUE;
}
}
// Keep passing through the array while at least one swap was done
// When there was no swap then the values are in the desired order
} while ($swapped);
// Return the sorted array
return $integers;
}