Bubble sort and binary PHP search (learning, experimenting)
Introduction
I would like to share with the community my implementation of bubble sorting and binary search. The project is made solely for educational purposes.
When I was asked earlier at an interview about the sorting algorithms and the implementation of the search for data arrays, I was lost and thought that to implement such things one must be at least a talented excellent student, that this is difficult, long-poorly understood, etc. :) I also found courses where in a few weeks (months) they offer to teach everyone to everything, everything, on algorithms, sorting, cryptography. But now there is the Internet, and everything is already laid out and known in it? It remains only to raise and study the necessary knowledge and practically implement and consolidate the acquired knowledge.
So, we proceed to the implementation of the algorithms themselves. Looking ahead, I will say that the article consists of three logical parts: the implementation of algorithms, testing written code (PHPUnit) and conducting load tests (basic functions of the VS language written code).
')
Those. how would imitate the development of a certain system (the implementation of a practical task) and the passage through all the required steps (based on the existing “standards” of development).
Bubble Sort
On Wikipedia and in the relevant articles in detail and described in detail all types of searches. Sorts are animated, and on Youtube there is a video with the main types of sorting and a visual display of the process of ordering arrays.
Before starting to write code, I did not specifically peer into the code of implementations of such a sort (for the purity of the experiment), but only read the conditions of the problem. I started writing code, threw test data, launched the script for the first time and look at the result: the array is sorted! In my head a slight panic! What have I done wrong? Where is the mistake? No error - the array is sorted correctly.
A few lines of code - this is the whole implementation of bubble sorting? Why did I think earlier that this is very difficult and not accessible to everyone?
Code under the spoiler
/** * * @param array $data * @return array */ public function sort(array $data) { $count_elements = count($data); $iterations = $count_elements - 1; for ($i=0; $i < $count_elements; $i++) { $changes = false; for ($j=0; $j < $iterations; $j++) { if ($data[$j] > $data[($j + 1)]) { $changes = true; list($data[$j], $data[($j + 1)]) = array($data[($j + 1)], $data[$j]); } } $iterations--; if (!$changes) { return $data; } } return $data; } Binary search
The implementation of the binary search was a little more difficult. I rewrote the code several times, deleted and reassembled it. Part of the time was spent on preparing test data and checking various situations in which the search should work correctly.
But everything worked well. The only thing that I don’t know right now is what “overflowing the whole when calculating the average index” :)
Code under the spoiler
/** * * @param int $element * @return mixed */ public function search(int $element, array $data) { $begin = 0; $end = count($data) - 1; $prev_begin = $begin; $prev_end = $end; while (true) { $position = round(($begin + $end) / 2); if (isset($data[$position])) { if ($data[$position] == $element) { return $position; } if ($data[$position] > $element) { $end = floor(($begin + $end) / 2); } elseif ($data[$position] < $element) { $begin = ceil(($begin + $end) / 2); } } if ($prev_begin == $begin && $prev_end == $end) { return false; } $prev_begin = $begin; $prev_end = $end; } }
Code testing
The code of classes is carried on separate files. It will be logical to cover the code with unit tests and, if we make any changes to the implementation, to be able to quickly recheck the performance of the underlying functionality.
When testing a binary search, the following situations were taken into account:
- an array of 0/1/2 elements is passed to the input
- first / last element
- there is no element in the array
- access to elements outside the array
Code under the spoiler
class BinarySearchTest extends PHPUnit_Framework_TestCase { /** * * @var BinarySearch */ public $binary; /** * * @var array */ public $empty_data = []; /** * * @var array */ public $one_element = [1]; /** * * @var array */ public $two_elements = [1,2]; /** * * @var array */ public $many_elements = [-189, -55, -34, -9, 0, 1, 6, 9, 10, 12, 25, 45, 67, 287, 633, 673, 783, 942]; public function setUp() { $this->binary = new BinarySearch(); } public function tearDown() { } public function testEmptyData() { $result = $this->binary->search(1, $this->empty_data); $this->assertEquals($result, false); } public function testOneElement() { $result = $this->binary->search(1, $this->one_element); $this->assertEquals($result, 0); $result = $this->binary->search(2, $this->one_element); $this->assertEquals($result, false); } public function testTwoElements() { $result = $this->binary->search(1, $this->two_elements); $this->assertEquals($result, 0); $result = $this->binary->search(2, $this->two_elements); $this->assertEquals($result, 1); } public function testManyElements() { $result = $this->binary->search(-34, $this->many_elements); $this->assertEquals($result, 2); $result = $this->binary->search(-1, $this->many_elements); $this->assertEquals($result, false); $result = $this->binary->search(0, $this->many_elements); $this->assertEquals($result, 4); $result = $this->binary->search(11, $this->many_elements); $this->assertEquals($result, false); $result = $this->binary->search(25, $this->many_elements); $this->assertEquals($result, 10); $result = $this->binary->search(673, $this->many_elements); $this->assertEquals($result, 15); } public function testLastFirstElement() { $result = $this->binary->search(-189, $this->many_elements); $this->assertEquals($result, 0); $result = $this->binary->search(942, $this->many_elements); $this->assertEquals($result, 17); } public function testOutsideData() { $result = $this->binary->search(-479, $this->many_elements); $this->assertEquals($result, false); $result = $this->binary->search(1294, $this->many_elements); $this->assertEquals($result, false); } }
Bubble sorting is tested quite simply - we compare the result, we expect the correct data array.
Code under the spoiler
class BubbleSortTest extends PHPUnit_Framework_TestCase { /** * * @var BubbleSort */ public $bubble; /** * * @var array */ public $unsorted_data = [2, 0, -1, 3, 1]; /** * * @var array */ public $sorted_data = [-1, 0, 1, 2, 3]; public function setUp() { $this->bubble = new BubbleSort(); } public function tearDown() { } public function testSort() { $sorted_data = $this->bubble->sort($this->unsorted_data); $this->assertInternalType('array', $sorted_data); $this->assertEquals($sorted_data, $this->sorted_data); } }
Stress Testing
Test File Code
set_time_limit(0); include 'src/BinarySearch.php'; include 'src/BubbleSort.php'; include 'lib/Benchmark.php'; $benchmark = new Benchmark(); $array_100 = []; $array_1000 = []; $array_10000 = []; $array_100000 = []; $array_1000000 = []; for ($i=0; $i<100; $i++) { $array_100[] = mt_rand(0, 100); } for ($i=0; $i<1000; $i++) { $array_1000[] = mt_rand(0, 1000); } for ($i=0; $i<10000; $i++) { $array_10000[] = mt_rand(0, 10000); } for ($i=0; $i<100000; $i++) { $array_100000[] = mt_rand(0, 100000); } for ($i=0; $i<1000000; $i++) { $array_100000[] = mt_rand(0, 1000000); } $array_100_copy = $array_100; $array_1000_copy = $array_1000; $array_10000_copy = $array_10000; /** * Test bubble sort */ $bubble = new BubbleSort(); $benchmark->mark('begin_sort_100'); sort($array_100); $sort_100 = $benchmark->elapsedTime('begin_sort_100', 'end_sort_100'); $benchmark->mark('begin_sort_100_copy'); $bubble->sort($array_100_copy); $sort_100_copy = $benchmark->elapsedTime('begin_sort_100_copy', 'end_sort_100_copy'); $benchmark->mark('begin_sort_1000'); sort($array_1000); $sort_1000 = $benchmark->elapsedTime('begin_sort_1000', 'end_sort_1000'); $benchmark->mark('begin_sort_1000_copy'); $bubble->sort($array_1000_copy); $sort_1000_copy = $benchmark->elapsedTime('begin_sort_1000_copy', 'end_sort_1000_copy'); $benchmark->mark('begin_sort_10000'); sort($array_10000); $sort_10000 = $benchmark->elapsedTime('begin_sort_10000', 'end_sort_10000'); $benchmark->mark('begin_sort_10000_copy'); $bubble->sort($array_10000_copy); $sort_10000_copy = $benchmark->elapsedTime('begin_sort_10000_copy', 'end_sort_10000_copy'); /** * Test binary search */ $binary = new BinarySearch(); sort($array_100); sort($array_1000); sort($array_10000); sort($array_100000); sort($array_1000000); reset($array_100); reset($array_1000); reset($array_10000); reset($array_100000); reset($array_1000000); $benchmark->mark('begin_search_100'); $position = array_search(50, $array_100); $search_100 = $benchmark->elapsedTime('begin_search_100', 'end_search_100', 6); $benchmark->mark('begin_search_100_in_array'); $position = in_array(50, $array_100); $search_100_in_array = $benchmark->elapsedTime('begin_search_100_in_array', 'end_search_100_in_array', 6); $benchmark->mark('begin_search_100_second'); $position = $binary->search(50, $array_100); $search_100_second = $benchmark->elapsedTime('begin_search_100_second', 'end_search_100_second', 6); $benchmark->mark('begin_search_1000'); $position = array_search(50, $array_1000); $search_1000 = $benchmark->elapsedTime('begin_search_1000', 'end_search_1000', 6); $benchmark->mark('begin_search_1000_in_array'); $position = in_array(50, $array_1000); $search_1000_in_array = $benchmark->elapsedTime('begin_search_1000_in_array', 'end_search_1000_in_array', 6); $benchmark->mark('begin_search_1000_second'); $position = $binary->search(50, $array_1000); $search_1000_second = $benchmark->elapsedTime('begin_search_1000_second', 'end_search_1000_second', 6); $benchmark->mark('begin_search_10000'); $position = array_search(50, $array_10000); $search_10000 = $benchmark->elapsedTime('begin_search_10000', 'end_search_10000', 6); $benchmark->mark('begin_search_10000_in_array'); $position = in_array(50, $array_10000); $search_10000_in_array = $benchmark->elapsedTime('begin_search_10000_in_array', 'end_search_10000_in_array', 6); $benchmark->mark('begin_search_10000_second'); $position = $binary->search(50, $array_10000); $search_10000_second = $benchmark->elapsedTime('begin_search_10000_second', 'end_search_10000_second', 6); $benchmark->mark('begin_search_100000'); $position = array_search(50, $array_100000); $search_100000 = $benchmark->elapsedTime('begin_search_100000', 'end_search_100000', 6); $benchmark->mark('begin_search_100000_in_array'); $position = in_array(50, $array_100000); $search_100000_in_array = $benchmark->elapsedTime('begin_search_100000_in_array', 'end_search_100000_in_array', 6); $benchmark->mark('begin_search_100000_second'); $position = $binary->search(50, $array_100000); $search_100000_second = $benchmark->elapsedTime('begin_search_100000_second', 'end_search_100000_second', 6); $benchmark->mark('begin_search_1000000'); $position = array_search(50, $array_1000000); $search_1000000 = $benchmark->elapsedTime('begin_search_1000000', 'end_search_1000000', 6); $benchmark->mark('begin_search_1000000_in_array'); $position = in_array(50, $array_1000000); $search_1000000_in_array = $benchmark->elapsedTime('begin_search_1000000_in_array', 'end_search_1000000_in_array', 6); $benchmark->mark('begin_search_1000000_second'); $position = $binary->search(50, $array_1000000); $search_1000000_second = $benchmark->elapsedTime('begin_search_1000000_second', 'end_search_1000000_second', 6); ?> <h3>, </h3> <table> <thead> <tr> <th> </th> <th> PHP::sort() <br>. </th> <th> BubbleSort()->sort() <br>. </th> </tr> </thead> <tbody> <tr> <td> 100 </td> <td><?=$sort_100?></td> <td><?=$sort_100_copy?></td> </tr> <tr> <td> 1000 </td> <td><?=$sort_1000?></td> <td><?=$sort_1000_copy?></td> </tr> <tr> <td> 10000 </td> <td><?=$sort_10000?></td> <td><?=$sort_10000_copy?></td> </tr> </tbody> </table> <h3> , </h3> <table> <thead> <tr> <th> </th> <th> PHP::array_search() <br>. </th> <th> PHP::in_array() <br>. </th> <th> BinarySearch()->search() <br>. </th> </tr> </thead> <tbody> <tr> <td> 100 </td> <td><?=$search_100?></td> <td><?=$search_100_in_array?></td> <td><?=$search_100_second?></td> </tr> <tr> <td> 1000 </td> <td><?=$search_1000?></td> <td><?=$search_1000_in_array?></td> <td><?=$search_1000_second?></td> </tr> <tr> <td> 10000 </td> <td><?=$search_10000?></td> <td><?=$search_10000_in_array?></td> <td><?=$search_10000_second?></td> </tr> <tr> <td> 100000 </td> <td><?=$search_100000?></td> <td><?=$search_100000_in_array?></td> <td><?=$search_100000_second?></td> </tr> <tr> <td> 1000000 </td> <td><?=$search_1000000?></td> <td><?=$search_1000000_in_array?></td> <td><?=$search_1000000_second?></td> </tr> </tbody> </table>
Sorting, load tests
|
| PHP :: sort ()
seconds | BubbleSort () -> sort ()
seconds |
|---|---|---|
| Array of 100 elements
| 0.0000 | 0.0023 |
| Array of 1000 elements
| 0.0002 | 0.2305 |
| An array of 10,000 items
| 0.0031 | 23.1601 |
Item position search, load tests
|
| PHP :: array_search ()
seconds | PHP :: in_array ()
seconds | BinarySearch () -> search ()
seconds |
|---|---|---|---|
| Array of 100 elements
| 0.000012 | 0.000004 | 0.000032 |
| Array of 1000 elements
| 0.000003 | 0.000003 | 0.000026 |
| An array of 10,000 items
| 0.000004 | 0.000003 | 0.000034 |
| An array of 100,000 items
| 0.000005 | 0.000003 | 0.000046 |
| An array of 1,000,000 items
| 0.000003 | 0.000003 | 0.000005 |
Conclusions from the test results:
- The sorting built into PHP is three to four orders of magnitude more efficient than the one written by the author. And this is on fairly small data arrays (on large arrays the difference will increase).
- Binary search, surprisingly, showed only an order of magnitude lower speed of searching for the position of an element (compared to the functions built into the language). Increasing the amount of input data on the efficiency of binary search has little impact.
Conclusion
I would be happy if the approaches, thoughts and ideas that I used when writing this code would be useful to people or serve as a basis for discussing and finding more optimal solutions.
I understand that many developers have long gone through such stages of growing up and becoming as specialists. Such tasks are almost certainly included in the university program of laboratory programming work.
All the code in this article is laid out on GitHub .
Ready to listen to your comments and suggestions.
Source: https://habr.com/ru/post/324792/
All Articles