BubbleSort делает что-то странное
Я медленно пытаюсь выяснить реализацию пузырьковой сортировки, концепция достаточно проста для понимания. в основном я имею это далеко с этим:
<?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
Итак, вот функция, я хотел написать функцию сам, а не использовать встроенную функцию PHP. Я также использую phpspec, чтобы проверить их, и мои переменные определены здесь, вот спецификация:
<?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]);
}
}
И когда я запускаю спецификацию, вот что я получаю:
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
Любая помощь или указатель будет принята с благодарностью
У меня действительно работает сортировка вставок, поэтому некоторые пропущены, неудачные — для пузыря.
Еще раз, я очень новичок в этом, так что дайте мне немного передышки для пропуска каких-либо основных вещей. я пытаюсь получить это в моем мозгу: P
Решение
В вашем коде есть некоторые ошибки. Во-первых, алгоритм:
$holder = $integers[$j];
if ($integers[$j] < $integers[$j-1]){
$integers[$i] = $integers[$j-1];
$integers[$j-1] = $holder;
}
Второе задание выше должно гласить:
$integers[$j] = $integers[$j-1];
потому что вы меняете $integers[$j] с $integers[$j-1] если они в неправильном порядке (я уверен, что это просто опечатка).
Эта ошибка, вероятно, приводит к сбою второго контрольного примера в спецификации.
Первый тестовый пример:
function it_can_sort_an_array_of_four_integers()
{
$integers = [8, 4, 6, 2];
$this->sort($integers)->shouldReturn(['2, 4, 6, 8']);
}
должен прочесть:
$this->sort($integers)->shouldReturn([2, 4, 6, 8]);
Обратите внимание, что это массив из четырех целых чисел, а ваш код проверяет результат по массиву, содержащему одну строку.
Дальнейшие улучшения:
Ты бежишь count($integers) проходит через массив, проверяя пары соседних значений, которые находятся в неправильном порядке. Хотя это максимальное количество необходимых проходов, во многих случаях оно завершается раньше.
Лучшая реализация состоит в том, чтобы сохранить флаг, который запоминает после каждого прохода, если это было сделано, и замену делать, и выходить из цикла, когда его не было (так как массив уже отсортирован).
Что-то вроде этого:
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;
}
Другие решения
Прежде всего, использование пузырьковой сортировки не очень хорошая идея. Он имеет сложность O (n ^ 2). Вы должны использовать php usort, который на самом деле представляет собой сложность реализации сортировки слиянием O (n * log (n)), или вы можете реализовать ее самостоятельно.
В любом случае, ваша сортировка пузырьков неверна, вы путаете индексы.
Попробуй это:
public function bubbleSort(array $numbers)
{
for ( $i = 0; $i < count($numbers); $i++ ) {
for ($j = 0; $j < count($numbers) $j++ ) {
if ($numbers[$i] < $numbers[$j]) {
$temp = $numbers[$i];
$numbers[$i] = $numbers[$j];
$numbers[$j] = $temp;
}
}
}
return $numbers;
}