How to become an author
Search
Write a publication
Pull to refresh

Пузырьковая сортировка и бинарный поиск на PHP (обучение, эксперименты)

Reading time10 min
Views18K
PHP*Delirium codingAlgorithms*

Введение


Хотел бы поделиться с сообществом своей реализацией пузырьковой сортировки и бинарного поиска. Проект сделал исключительно в учебных целях.

Когда меня раньше спрашивали на собеседовании об алгоритмах сортировки и реализации поиска по массивам данных — я терялся и считал, что для реализации подобных вещей надо быть как минимум талантливым отличником-олимпиадником, что это сложно-долго-малоизучено и т.п. :) Так же я находил курсы, где за несколько недель (месяцев) предлагают научить всех желающих всему-всему по алгоритмам, сортировкам, криптографии. Но ведь сейчас есть Интернет, а в нем уже все выложено и известно? Остается только поднять и изучить нужные знания и практически реализовать и закрепить приобретенные знания.

Итак, приступим к реализации самих алгоритмов. Забегая вперед скажу, что статья состоит из трех логических частей: реализация алгоритмов, тестирование написанного кода (PHPUnit) и проведение нагрузочных тестов (базовые функции языка VS написанный код).

Т.е. как бы имитируется разработка некой системы (выполнение практической задачи) и прохождение по всем обязательным этапам (исходя из существующих на сейчас «стандартов» разработки).



Пузырьковая сортировка


НА Википедии и в профильных статьях довольно подробно и детально описаны все виды поиска. Сортировки анимированны, а на Ютубе есть видео с основными видами сортировок и наглядным отображением самого процесса упорядочивания массивов.

Перед началом написания кода я специально не вглядывался в код реализаций такой сортировки (для чистоты эксперимента), а лишь читал условия задачи. Начал писать код, подбросил тестовые данные, запустил скрипт в первый раз и смотрю на результат: массив отсортирован! В голове легкая паника! Что я сделал не так? Где ошибка? Ошибки нет — массив отсортирован верно.

Несколько строк кода — это и есть вся реализация пузырьковой сортировки?! Почему же я раньше считал, что это очень сложно и доступно не всем?

Код под спойлером
    /**
     * 
     * @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;
    }


Бинарный поиск


Реализация бинарного поиска далась немного труднее. Несколько раз переписывал код, удалял и заново компоновал его. Часть времени пошла на подготовку тестовых данных и проверку различных ситуаций, при которых поиск должен работать корректно.

Но все успешно заработало. Единственное, что я не сейчас не знаю, что такое «переполнение целого при вычислении среднего индекса» :)

Код под спойлером
    /**
     *
     * @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;
        }
    }


Тестирование кода


Код классов разнесен по отдельным файлам. Логично будет покрыть код юнит-тестами и, если мы внесем в реализацию какие-то изменения, иметь возможность быстро перепроверить работоспособность базового функционала.

При тестировании бинарного поиска были учтены следующие ситуации:

  • на вход передаем массив из 0 / 1 / 2 элементов
  • первый / последний элемент
  • элемента в массиве нет
  • обращение к элементам за пределами массива

Код под спойлером
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); 
    }     
    
}


Пузырьковая сортировка тестируется достаточно просто — сравниваем результат, ожидаем корректный массив данных.

Код под спойлером
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);
    }
}


Нагрузочное тестирование


Код файла тестов
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>


Сортировка, нагрузочные тесты

 PHP::sort()
сек.
 BubbleSort()->sort()
сек.
Массив из 100 элементов
 0.0000 0.0023
Массив из 1000 элементов
 0.0002 0.2305
Массив из 10000 элементов
 0.0031 23.1601

Поиск позиции элемента, нагрузочные тесты

 PHP::array_search()
сек.
 PHP::in_array()
сек.
 BinarySearch()->search()
сек.
Массив из 100 элементов
 0.000012 0.000004 0.000032
Массив из 1000 элементов
 0.000003 0.000003 0.000026
Массив из 10000 элементов
 0.000004 0.000003 0.000034
Массив из 100000 элементов
 0.000005 0.000003 0.000046
Массив из 1000000 элементов
 0.000003 0.000003 0.000005

Выводы по результатам тестирования:

  • Встроенная в PHP сортировка на три-четыре порядка эффективнее, нежели написанная автором. И это на достаточно небольших массивах данных (на больших массивах разница будет увеличиваться).
  • Бинарный поиска, на удивление, показал всего лишь на порядок меньшую скорость поиска позиции элемента (по сравненнию с встроенными в язык функциями). Увеличение объемов входных данных на эффективность бинарного поиска оказывает малое влияние.

Заключение


Буду рад, если подходы, мысли и идеи, которые я применял при написании этого кода пригодятся людям или послужат основой для обсуждения и нахождения более оптимальных решений.

Понимаю, что многие разработчики уже давно прошли подобные этапы взросления и становления как специалисты. Подобные задачи почти наверняка входят в университетскую программу лабораторных работ по программированию.

Весь код, приведенный в этой статье выложен на GitHub.

Готов выслушать ваши замечания и предложения.
Tags:
Hubs:
+1
Comments17
48
Karma
0
Rating
Владимир @volmir

Веб-программист

Send message

Articles

Show the best of all time
Change theme settings

Your account

Sections

Information

Services

Support
© 2006–2024, Habr