Zend Framework Blog

Faster Autoloading With Zend Framework 2

2013 May 2

by Richard Knop

Standard autoloader that comes with Zend Framework 2 is not and ideal one to use in production environment. I would suggest using a classmap autoloader which is faster. Here is how it works. When installing dependencies specified in composer.json, use -o option in order to generate classmap file:

php composer.phar install -o

It will create a PHP file at vendor/composer/autoload_classmap.php path which contains a static array of all knows classes from dependencies (Zend Framework 2, Doctrine 2 etc) with namespaces and paths to files.

You should also autoload all your modules in the same way. Either do it manually – cd into module folder and generate the classmap file:

cd module/Foo
../../vendor/bin/classmap_generator.php -w

Or use ANT:

<target name="classmapgenerator" description="">
<exec executable="php">
<arg value="${basedir}/vendor/zendframework/zendframework/bin/classmap_generator.php" />
<arg value="-w" />
<arg value="-l" />
<arg value="module/Foo" />
</exec>
<exec executable="php">
<arg value="${basedir}/vendor/zendframework/zendframework/bin/classmap_generator.php" />
<arg value="-w" />
<arg value="-l" />
<arg value="module/Bar" />
</exec>
</target>

Inside your Module.php, change getAutoloaderConfig() method to look like this:

public function getAutoloaderConfig()
{
return array(
'Zend\Loader\ClassMapAutoloader' => array(
__DIR__ . '/autoload_classmap.php',
),
);
}

Finally, change your init_autoloader.php file:

require_once __DIR__ . '/vendor/zendframework/zendframework/library/Zend/Loader/AutoloaderFactory.php';
require_once __DIR__ . '/vendor/zendframework/zendframework/library/Zend/Loader/ClassMapAutoloader.php';
Zend\Loader\AutoloaderFactory::factory(array(
'Zend\Loader\ClassMapAutoloader' => array(
'Composer' => __DIR__ . '/vendor/composer/autoload_classmap.php',
)
));

Done! I don’t have any benchmarks at the moment. If I will have more free time, I will run some benchmarks to see how much faster it is actually.

Select a radio button with Mink / Behat

2013 April 30

1 Comment

tags: Behat, Gherkin, Mink

by Richard Knop

Either I am completely blind or I just haven’t found an out-of-box solution for selecting a radio button with Mink / Behat. I have written a simple step definition which does this for me. In order for it to work, you have to have the radio button input element wrapped by a label element. Use the label text as argument:

/**

* @When /^I check the "([^"]*)" radio button$/
*/
public function iCheckTheRadioButton($labelText)
{
foreach ($this->getMainContext()->getSession()->getPage()->findAll('css', 'label') as $label) {
if ($labelText === $label->getText() && $label->has('css', 'input[type="radio"]')) {
$this->getMainContext()->fillField($label->find('css', 'input[type="radio"]')->getAttribute('name'), $label->find('css', 'input[type="radio"]')->getAttribute('value'));
return;
}
}
throw new \Exception('Radio button not found');
}

Use it like this inside your feature:

When I check the "Enabled" radio button

Introduction to boto (Python interface to AWS)

2013 February 23

Leave a comment

tags: boto, S3

by Richard Knop

More and more companies are using cloud storage for their files these days. There are many cloud services you can choose from (Windows Azure, Ubuntu Cloud, Amazon Web Services etc). I have used mainly Amazon Web Services (AWS) so I will show you how to easily upload files to S3 and how to copy files on S3 to different locations from Python script.

The only thing you need is Python and boto which is a Python interface to AWS. You can install it via pip:

pip install boto

Before uploading files to S3 you need to know your access key and secret key which will be provided to you by Amazon. You also need to create a bucket which is something like a namespace or a directory on S3. Once you have your access key, secret key and you have created a bucket, it’s easy to upload files to it with boto.

from boto.s3.connection import S3Connection
YOUR_ACCESS_KEY_ID = "MY_ACCESS_KEY"
YOUR_SECRET_ACCESS_KEY = "MY_SECRET_KEY"
BUCKET = "MY_COOL_BUCKET"
conn = S3Connection(YOUR_ACCESS_KEY_ID, YOUR_SECRET_ACCESS_KEY)
bucket = conn.get_bucket(BUCKET)
files_to_upload = {
'/path/to/hello.txt': 'hello_on_s3.txt'
'/path/to/world.txt': 'world_on_s3.txt'
}
for file_to_upload, s3_destination in files_to_upload.iteritems():
key = bucket.new_key(s3_destination)
key.set_contents_from_filename(file_to_upload)
key.set_acl('public-read')

Next thing you might want to do is to copy a file already uploaded to S3 bucket to a different location. This is how you do it:

from boto.s3.connection import S3Connection
YOUR_ACCESS_KEY_ID = "MY_ACCESS_KEY"
YOUR_SECRET_ACCESS_KEY = "MY_SECRET_KEY"
BUCKET = "MY_COOL_BUCKET"
conn = S3Connection(YOUR_ACCESS_KEY_ID, YOUR_SECRET_ACCESS_KEY)
bucket = conn.get_bucket(BUCKET)
files_to_copy = {
'hello_on_s3.txt' => 'foo_on_s3.txt',
'world_on_s3.txt' => 'bar_on_s3.txt'
}
for file_to_copy, new_destination in files_to_copy.iteritems():
bucket.copy_key(
new_destination,
BUCKET,
file_to_copy
)

The above code will copy the files to a different location in the same bucket. You can also specify a different bucket as well.

There are much more things you can do with boto. This post was just an introduction. Feel free to read the full boto documentation.

Access entity manager in Zend Framework 2 unit tests

2012 September 25

Leave a comment

tags: Entity manager

by Richard Knop

In order to access the entity manager in your unit tests you will have to make your PHPUnit bootstrap file a little bit more complex. You will need to access the entity manager if you are using Doctrine module together with Zend Framework 2.

Here is what I have done:

<?php
use Zend\ServiceManager\ServiceManager,
Zend\Mvc\Service\ServiceManagerConfig;
class Bootstrap
{
static public $config;
static public $sm;
static public $em;
static public function go()
{
chdir(dirname(__DIR__));
include __DIR__ . '/../init_autoloader.php';
self::$config = include 'config/application.config.php';
Zend\Mvc\Application::init(self::$config);
self::$sm = self::getServiceManager(self::$config);
self::$em = self::getEntityManager(self::$sm);
}
static public function getServiceManager($config)
{
$serviceManager = new ServiceManager(new ServiceManagerConfig);
$serviceManager->setService('ApplicationConfig', $config);
$serviceManager->get('ModuleManager')->loadModules();
return $serviceManager;
}
static public function getEntityManager($serviceManager)
{
return $serviceManager->get('doctrine.entitymanager.orm_default');
}
}
Bootstrap::go();

And then in your unit tests you can access the entity manager simply by:

Bootstrap:$em

That was quite easy actually.

How to unit test redirecting in Zend Framework 2

2012 September 25

Leave a comment

tags: Unit testing with Zend Framework 2

by Richard Knop

I’ve been working with Zend Framework 2 last couple of weeks and so far I like it better than the legacy Zend Framework. Proper namespaces and separate bootstrap for each module are nice features. I am still learning all the new features so I will be documenting some helpful ideas.

One problem I had today was I needed to write a unit test for a controller action which under certain condition redirects to a different action using the redirect helper:

$this->redirect->roToute('routeName', array('controller' => 'index', 'action' = 'index'));

Unit testing a controller action was not a problem, I figured that out a week or two ago. In order to write an assertion for redirection, you will need to create a new instance of Zend\Mvc\Router\SimpleRouteStack and add routes you are testing for to it. Then attach the router to Zend\Mvc\MvcEvent.

So include few classes from Zend library plus the controller you want to test:

use MyModule\Controller\IndexController,
Zend\Http\Request,
Zend\Http\Response,
Zend\Mvc\MvcEvent,
Zend\Mvc\Router\RouteMatch,
Zend\Mvc\Router\SimpleRouteStack,
Zend\Mvc\Router\Http\Segment,

Then put this inside your PHPUnit test case’s setUp method:

public function setUp()
{
$this->_controller = new IndexController;
$this->_request = new Request;
$this->_response = new Response;
$this->_event = new MvcEvent();
$routeStack = new SimpleRouteStack;
$route = new Segment('/mymodule/[:controller/[:action/]]');
$routeStack->addRoute('mymodule', $route);
$this->_event->setRouter($routeStack);
$routeMatch = new RouteMatch(array('controller' => 'index', 'action' => 'index'));
$routeMatch->setMatchedRouteName('admin');
$this->_event->setRouteMatch($routeMatch);
$this->_controller->setEvent($this->_event);
}

After you have done all that, there are two ways how to assert a redirection has actually happened.

First, you can test for a 302 HTTP status:

public function testIndexActionRedirectsByHttpStatus()
{
$this->_controller->dispatch($this->_request, $this->_response);
$this->assertEquals(302, $this->_response->getStatusCode());
}

Second, you can check for the Location header:

public function testIndexActionRedirectsToCorrectUri()
{
$this->_controller->dispatch($this->_request, $this->_response);
$this->assertEquals('/mymodule/mycontroller/myaction/', $this->_event->getResponse()->getHeaders()->get('Location')->getUri());
}

Ideally use both assertions to be sure.

Create a self signed X509 certificate in Python

2012 August 5

Leave a comment

tags: Asynchronous encryption, RSA, Self signed certificate, X509

by Richard Knop

Here is how to create a self signed certificate in Python using OpenSSL:

from OpenSSL import crypto, SSL
from socket import gethostname
from pprint import pprint
from time import gmtime, mktime
CERT_FILE = "selfsigned.crt"
KEY_FILE = "private.key"
def create_self_signed_cert():
# create a key pair
k = crypto.PKey()
k.generate_key(crypto.TYPE_RSA, 1024)
# create a self-signed cert
cert = crypto.X509()
cert.get_subject().C = "UK"
cert.get_subject().ST = "London"
cert.get_subject().L = "London"
cert.get_subject().O = "Dummy Company Ltd"
cert.get_subject().OU = "Dummy Company Ltd"
cert.get_subject().CN = gethostname()
cert.set_serial_number(1000)
cert.gmtime_adj_notBefore(0)
cert.gmtime_adj_notAfter(10*365*24*60*60)
cert.set_issuer(cert.get_subject())
cert.set_pubkey(k)
cert.sign(k, 'sha1')
open(CERT_FILE, "wt").write(
crypto.dump_certificate(crypto.FILETYPE_PEM, cert))
open(KEY_FILE, "wt").write(
crypto.dump_privatekey(crypto.FILETYPE_PEM, k))
create_self_signed_cert()

You can then use m2crypto library to encrypt and decrypt data using this self signed certificate. You use public key to encrypt and private key to decrypt:

f = open(CERT_FILE)
cert_buffer = f.read()
f.close()
from M2Crypto import RSA, X509
cert = X509.load_cert_string(cert_buffer, X509.FORMAT_PEM)
pub_key = cert.get_pubkey()
rsa_key = pub_key.get_rsa()
cipher = rsa_key.public_encrypt('plaintext', RSA.pkcs1_padding)
print cipher
ReadRSA = RSA.load_key(KEY_FILE)
try:
plaintext = ReadRSA.private_decrypt (cipher, RSA.pkcs1_padding)
except:
print "Error: wrong key?"
plaintext = ""
print plaintext

Merge sort PHP implementation

2012 June 27

1 Comment

tags: Merge sort

by Richard Knop

After a short pause I am continuing my challenge to implement all sorting algorithms listed on Wikipedia in PHP. Merge sort is a bit more advanced than previous algorithms but once you figure it out it’s quite neat.

Personally, I hate recursion and try to avoid it as much as possible (speaking of recursion, check out my weblogs about Adjacency list model and Nested set model – which is in my opinion a better solution in most cases) – but sorting is one area where recursion is needed.

Merge sort was invented by John Von Neumann, a big name in computer science history. It is a divide and conquer algorithm. It sorts arrays by dividing them recursively into halves (divide) and then sorting and merging them back together (conquer).

The good thing about this algorithm is it preserves order of equal elements (if you have two 25s in an array, merge sort will place the one that came earlier in the original array on the left side).

Here is my PHP implementation consisting of two functions: divide and conquer:

<?php
$arr = array();
for ($i = 0; $i < 100; ++$i) {
$arr[] = $i;
}
shuffle($arr);
$sortedArr = divide($arr);
var_dump($sortedArr);
function divide(array $arr) {
if (1 === count($arr)) {
return $arr;
}
$left = $right = array();
$middle = round(count($arr)/2);
for ($i = 0; $i < $middle; ++$i) {
$left[] = $arr[$i];
}
for ($i = $middle; $i < count($arr); ++$i) {
$right[] = $arr[$i];
}
$left = divide($left);
$right = divide($right);
return conquer($left, $right);
}
function conquer(array $left, array $right) {
$result = array();
while (count($left) > 0 || count($right) > 0) {
if (count($left) > 0 && count($right) > 0) {
$firstLeft = current($left);
$firstRight = current($right);
if ($firstLeft <= $firstRight) {
$result[] = array_shift($left);
} else {
$result[] = array_shift($right);
}
} else if (count($left) > 0) {
$result[] = array_shift($left);
} else if (count($right) > 0) {
$result[] = array_shift($right);
}
}
return $result;
}

Which will output:

array(100) {
  [0]=>
  int(0)
  [1]=>
  int(1)
  [2]=>
  int(2)
  [3]=>
  int(3)
  [4]=>
  int(4)
  [5]=>
  int(5)
  [6]=>
  int(6)
  [7]=>
  int(7)
  [8]=>
  int(8)
  [9]=>
  int(9)
  [10]=>
  int(10)
  [11]=>
  int(11)
  [12]=>
  int(12)
  [13]=>
  int(13)
  [14]=>
  int(14)
  [15]=>
  int(15)
  [16]=>
  int(16)
  [17]=>
  int(17)
  [18]=>
  int(18)
  [19]=>
  int(19)
  [20]=>
  int(20)
  [21]=>
  int(21)
  [22]=>
  int(22)
  [23]=>
  int(23)
  [24]=>
  int(24)
  [25]=>
  int(25)
  [26]=>
  int(26)
  [27]=>
  int(27)
  [28]=>
  int(28)
  [29]=>
  int(29)
  [30]=>
  int(30)
  [31]=>
  int(31)
  [32]=>
  int(32)
  [33]=>
  int(33)
  [34]=>
  int(34)
  [35]=>
  int(35)
  [36]=>
  int(36)
  [37]=>
  int(37)
  [38]=>
  int(38)
  [39]=>
  int(39)
  [40]=>
  int(40)
  [41]=>
  int(41)
  [42]=>
  int(42)
  [43]=>
  int(43)
  [44]=>
  int(44)
  [45]=>
  int(45)
  [46]=>
  int(46)
  [47]=>
  int(47)
  [48]=>
  int(48)
  [49]=>
  int(49)
  [50]=>
  int(50)
  [51]=>
  int(51)
  [52]=>
  int(52)
  [53]=>
  int(53)
  [54]=>
  int(54)
  [55]=>
  int(55)
  [56]=>
  int(56)
  [57]=>
  int(57)
  [58]=>
  int(58)
  [59]=>
  int(59)
  [60]=>
  int(60)
  [61]=>
  int(61)
  [62]=>
  int(62)
  [63]=>
  int(63)
  [64]=>
  int(64)
  [65]=>
  int(65)
  [66]=>
  int(66)
  [67]=>
  int(67)
  [68]=>
  int(68)
  [69]=>
  int(69)
  [70]=>
  int(70)
  [71]=>
  int(71)
  [72]=>
  int(72)
  [73]=>
  int(73)
  [74]=>
  int(74)
  [75]=>
  int(75)
  [76]=>
  int(76)
  [77]=>
  int(77)
  [78]=>
  int(78)
  [79]=>
  int(79)
  [80]=>
  int(80)
  [81]=>
  int(81)
  [82]=>
  int(82)
  [83]=>
  int(83)
  [84]=>
  int(84)
  [85]=>
  int(85)
  [86]=>
  int(86)
  [87]=>
  int(87)
  [88]=>
  int(88)
  [89]=>
  int(89)
  [90]=>
  int(90)
  [91]=>
  int(91)
  [92]=>
  int(92)
  [93]=>
  int(93)
  [94]=>
  int(94)
  [95]=>
  int(95)
  [96]=>
  int(96)
  [97]=>
  int(97)
  [98]=>
  int(98)
  [99]=>
  int(99)
}

Best way to understand how it works is to apply it to a smaller array and add a little debugging inside the functions so we can see what’s happening. After a little tweaking:

<?php
$arr = array(4, 5, 1, 3, 2);
$sortedArr = divide($arr);
var_dump($sortedArr);
function divide(array $arr) {
if (1 === count($arr)) {
return $arr;
}
$left = $right = array();
$middle = round(count($arr)/2);
for ($i = 0; $i < $middle; ++$i) {
$left[] = $arr[$i];
}
for ($i = $middle; $i < count($arr); ++$i) {
$right[] = $arr[$i];
}
$left = divide($left);
$right = divide($right);
echo "We are going to conquer these two arrays:\narray(",
implode(", ", $left), ")\narray(", implode(", ", $right), ")\n";
$conquered = conquer($left, $right);
echo "After conquering we get: array(", implode(", ", $conquered), ")\n\n";
return $conquered;
}
function conquer(array $left, array $right) {
$result = array();
while (count($left) > 0 || count($right) > 0) {
if (count($left) > 0 && count($right) > 0) {
$firstLeft = current($left);
$firstRight = current($right);
if ($firstLeft <= $firstRight) {
$result[] = array_shift($left);
} else {
$result[] = array_shift($right);
}
} else if (count($left) > 0) {
$result[] = array_shift($left);
} else if (count($right) > 0) {
$result[] = array_shift($right);
}
}
return $result;
}

Which will output a nice explanation of what’s happening, we can see what steps are being done and in what order:

We are going to conquer these two arrays:
array(4)
array(5)
After conquering we get: array(4, 5)

We are going to conquer these two arrays:
array(4, 5)
array(1)
After conquering we get: array(1, 4, 5)

We are going to conquer these two arrays:
array(3)
array(2)
After conquering we get: array(2, 3)

We are going to conquer these two arrays:
array(1, 4, 5)
array(2, 3)
After conquering we get: array(1, 2, 3, 4, 5)

array(5) {
  [0]=>
  int(1)
  [1]=>
  int(2)
  [2]=>
  int(3)
  [3]=>
  int(4)
  [4]=>
  int(5)
}

By the way, here are my previous posts from this challenge:

Comb sort PHP implementation

2012 June 19

2 Comments

tags: Comb sort

by Richard Knop

After tackling the Shellsort, Comb sort is very similar. Shellsort was basically a generalisation of the Insertion sort, Comb sort is a generalisation of the Bubble sort. In the same way Shellsort was decreasing a gap between elements for subarrays been sent as input to the Insertion sort function, Comb sort is also decreasing the gap after every iteration and sending increasingly lengthy subarrays to the Bubble sort function.

According to Wikipedia, this algorithm works best with a shrink factor of around 1.3 (a little less than that but let’s keep this simple).

Here is my implementation:

<?php
define('SHRINK_FACTOR', 1.3);
$arr = array();
for ($i = 0; $i < 100; ++$i) {
$arr[] = $i;
}
shuffle($arr);
$sortedArr = combSort($arr);
var_dump($sortedArr);
function combSort(array $arr) {
$gap = floor(count($arr)/SHRINK_FACTOR);
while ($gap > 0) {
for ($i = 0; $i < count($arr)-$gap; ++$i) {
$arrWithGapsKeys = array();
$arrWithGaps = array();
$loop = true;
$j = $i;
while ($loop) {
if (isset($arr[$j])) {
$arrWithGapsKeys[] = (int)$j;
$arrWithGaps[] = $arr[$j];
$j += $gap;
} else {
$loop = false;
}
}
$arrWithGapsOrdered = bubbleSort($arrWithGaps);
foreach ($arrWithGapsKeys as $key) {
$arr[$key] = current($arrWithGapsOrdered);
next($arrWithGapsOrdered);
}
}
$gap = floor($gap/SHRINK_FACTOR);
}
return $arr;
}
function bubbleSort(array $arr) {
$sorted = false;
while (false === $sorted) {
$sorted = true;
for ($i = 0; $i < count($arr)-1; ++$i) {
$current = $arr[$i];
$next = $arr[$i+1];
if ($next < $current) {
$arr[$i] = $next;
$arr[$i+1] = $current;
$sorted = false;
}
}
}
return $arr;
}

Which will result in:

array(100) {
  [0]=>
  int(0)
  [1]=>
  int(1)
  [2]=>
  int(2)
  [3]=>
  int(3)
  [4]=>
  int(4)
  [5]=>
  int(5)
  [6]=>
  int(6)
  [7]=>
  int(7)
  [8]=>
  int(8)
  [9]=>
  int(9)
  [10]=>
  int(10)
  [11]=>
  int(11)
  [12]=>
  int(12)
  [13]=>
  int(13)
  [14]=>
  int(14)
  [15]=>
  int(15)
  [16]=>
  int(16)
  [17]=>
  int(17)
  [18]=>
  int(18)
  [19]=>
  int(19)
  [20]=>
  int(20)
  [21]=>
  int(21)
  [22]=>
  int(22)
  [23]=>
  int(23)
  [24]=>
  int(24)
  [25]=>
  int(25)
  [26]=>
  int(26)
  [27]=>
  int(27)
  [28]=>
  int(28)
  [29]=>
  int(29)
  [30]=>
  int(30)
  [31]=>
  int(31)
  [32]=>
  int(32)
  [33]=>
  int(33)
  [34]=>
  int(34)
  [35]=>
  int(35)
  [36]=>
  int(36)
  [37]=>
  int(37)
  [38]=>
  int(38)
  [39]=>
  int(39)
  [40]=>
  int(40)
  [41]=>
  int(41)
  [42]=>
  int(42)
  [43]=>
  int(43)
  [44]=>
  int(44)
  [45]=>
  int(45)
  [46]=>
  int(46)
  [47]=>
  int(47)
  [48]=>
  int(48)
  [49]=>
  int(49)
  [50]=>
  int(50)
  [51]=>
  int(51)
  [52]=>
  int(52)
  [53]=>
  int(53)
  [54]=>
  int(54)
  [55]=>
  int(55)
  [56]=>
  int(56)
  [57]=>
  int(57)
  [58]=>
  int(58)
  [59]=>
  int(59)
  [60]=>
  int(60)
  [61]=>
  int(61)
  [62]=>
  int(62)
  [63]=>
  int(63)
  [64]=>
  int(64)
  [65]=>
  int(65)
  [66]=>
  int(66)
  [67]=>
  int(67)
  [68]=>
  int(68)
  [69]=>
  int(69)
  [70]=>
  int(70)
  [71]=>
  int(71)
  [72]=>
  int(72)
  [73]=>
  int(73)
  [74]=>
  int(74)
  [75]=>
  int(75)
  [76]=>
  int(76)
  [77]=>
  int(77)
  [78]=>
  int(78)
  [79]=>
  int(79)
  [80]=>
  int(80)
  [81]=>
  int(81)
  [82]=>
  int(82)
  [83]=>
  int(83)
  [84]=>
  int(84)
  [85]=>
  int(85)
  [86]=>
  int(86)
  [87]=>
  int(87)
  [88]=>
  int(88)
  [89]=>
  int(89)
  [90]=>
  int(90)
  [91]=>
  int(91)
  [92]=>
  int(92)
  [93]=>
  int(93)
  [94]=>
  int(94)
  [95]=>
  int(95)
  [96]=>
  int(96)
  [97]=>
  int(97)
  [98]=>
  int(98)
  [99]=>
  int(99)
}

There are some variations of the Comb sort algorithm Combsort11 or Combsort with different end. I will show you how to implement them in the future.

Shellsort PHP implementation

2012 June 19

2 Comments

tags: Shellsort

by Richard Knop

Continuing my challenge, after implementing Bubble sort, Selection sort and Insertion sort, here comes Shellsort. Named after Donald Shell, it is basically a generalisation of simpler algorithms like Bubble sort or Insertion sort. It starts with far apart elements. The gap between elements is then decreased after every iteration.

That means we start with small subarrays and then with every iteration the subarrays are getting bigger as we are decreasing the gap between elements. I chose to start with a gap equal to half of the array length rounded down. After every iteration I divide the gap by two and round down again until zero is reached.

Example:

<?php
$arr = array();
for ($i = 0; $i < 100; ++$i) {
$arr[] = $i;
}
shuffle($arr);
$sortedArr = shellSort($arr);
var_dump($sortedArr);
function shellSort(array $arr) {
$gap = floor(count($arr)/2);
while ($gap > 0) {
for ($i = 0; $i < count($arr)-$gap; ++$i) {
$arrWithGapsKeys = array();
$arrWithGaps = array();
$loop = true;
$j = $i;
while ($loop) {
if (isset($arr[$j])) {
$arrWithGapsKeys[] = (int)$j;
$arrWithGaps[] = $arr[$j];
$j += $gap;
} else {
$loop = false;
}
}
$arrWithGapsOrdered = insertionSort($arrWithGaps);
foreach ($arrWithGapsKeys as $key) {
$arr[$key] = current($arrWithGapsOrdered);
next($arrWithGapsOrdered);
}
}
$gap = floor($gap/2);
}
return $arr;
}
function insertionSort(array $table) {
$leftHand = array();
foreach ($table as $card) {
if (0 === count($leftHand)) {
$leftHand[] = $card;
} else {
$insertedCard = false;
$reindexedLeftHand = array();
for ($i = count($leftHand)-1; $i >= 0; –$i) {
if ($card >= $leftHand[$i]) {
for ($j = 0; $j <= $i; ++$j) {
$reindexedLeftHand[$j] = $leftHand[$j];
}
$reindexedLeftHand[] = $card;
for ($j = $i+1; $j < count($leftHand); ++$j) {
$reindexedLeftHand[$j+1] = $leftHand[$j];
}
$insertedCard = true;
break;
}
}
if (false === $insertedCard) {
$reindexedLeftHand[] = $card;
foreach ($leftHand as $cardInLeftHand) {
$reindexedLeftHand[] = $cardInLeftHand;
}
}
$leftHand = $reindexedLeftHand;
}
}
return $leftHand;
}

Will result in:

array(100) {
  [0]=>
  int(0)
  [1]=>
  int(1)
  [2]=>
  int(2)
  [3]=>
  int(3)
  [4]=>
  int(4)
  [5]=>
  int(5)
  [6]=>
  int(6)
  [7]=>
  int(7)
  [8]=>
  int(8)
  [9]=>
  int(9)
  [10]=>
  int(10)
  [11]=>
  int(11)
  [12]=>
  int(12)
  [13]=>
  int(13)
  [14]=>
  int(14)
  [15]=>
  int(15)
  [16]=>
  int(16)
  [17]=>
  int(17)
  [18]=>
  int(18)
  [19]=>
  int(19)
  [20]=>
  int(20)
  [21]=>
  int(21)
  [22]=>
  int(22)
  [23]=>
  int(23)
  [24]=>
  int(24)
  [25]=>
  int(25)
  [26]=>
  int(26)
  [27]=>
  int(27)
  [28]=>
  int(28)
  [29]=>
  int(29)
  [30]=>
  int(30)
  [31]=>
  int(31)
  [32]=>
  int(32)
  [33]=>
  int(33)
  [34]=>
  int(34)
  [35]=>
  int(35)
  [36]=>
  int(36)
  [37]=>
  int(37)
  [38]=>
  int(38)
  [39]=>
  int(39)
  [40]=>
  int(40)
  [41]=>
  int(41)
  [42]=>
  int(42)
  [43]=>
  int(43)
  [44]=>
  int(44)
  [45]=>
  int(45)
  [46]=>
  int(46)
  [47]=>
  int(47)
  [48]=>
  int(48)
  [49]=>
  int(49)
  [50]=>
  int(50)
  [51]=>
  int(51)
  [52]=>
  int(52)
  [53]=>
  int(53)
  [54]=>
  int(54)
  [55]=>
  int(55)
  [56]=>
  int(56)
  [57]=>
  int(57)
  [58]=>
  int(58)
  [59]=>
  int(59)
  [60]=>
  int(60)
  [61]=>
  int(61)
  [62]=>
  int(62)
  [63]=>
  int(63)
  [64]=>
  int(64)
  [65]=>
  int(65)
  [66]=>
  int(66)
  [67]=>
  int(67)
  [68]=>
  int(68)
  [69]=>
  int(69)
  [70]=>
  int(70)
  [71]=>
  int(71)
  [72]=>
  int(72)
  [73]=>
  int(73)
  [74]=>
  int(74)
  [75]=>
  int(75)
  [76]=>
  int(76)
  [77]=>
  int(77)
  [78]=>
  int(78)
  [79]=>
  int(79)
  [80]=>
  int(80)
  [81]=>
  int(81)
  [82]=>
  int(82)
  [83]=>
  int(83)
  [84]=>
  int(84)
  [85]=>
  int(85)
  [86]=>
  int(86)
  [87]=>
  int(87)
  [88]=>
  int(88)
  [89]=>
  int(89)
  [90]=>
  int(90)
  [91]=>
  int(91)
  [92]=>
  int(92)
  [93]=>
  int(93)
  [94]=>
  int(94)
  [95]=>
  int(95)
  [96]=>
  int(96)
  [97]=>
  int(97)
  [98]=>
  int(98)
  [99]=>
  int(99)
}

Insertion sort algorithm PHP implementation

2012 June 19

1 Comment

tags: Insertion sort

by Richard Knop

This is a third blog post in my challenge to cover as many sorting algorithms as possible, implement them in PHP (without using any array functions) and then benchmark their performance with different inputs. Could be interesting.

Insertion sort is another common sorting algorithm. To explain how it works, try to imagine this. There’s a couple of cards on the table and you want to sort them in a correct order. You will pick a card from the table (based on any criteria, it doesn’t really matter, you can just pick the cards up randomly) and put it in your left hand at a correct position. To determine the correct position, you will compare it with every other card in your left hand starting from the right. This is a similar algorithm you might unconsciously use when playing cards with your friends.

Example:

<?php
$table = array(7, 3, 9, 6, 5, 1, 2, 0, 8, 4);
$leftHand = insertionSort($table);
var_dump($leftHand);
function insertionSort(array $table) {
$leftHand = array();
foreach ($table as $card) {
if (0 === count($leftHand)) {
$leftHand[] = $card;
} else {
$insertedCard = false;
$reindexedLeftHand = array();
for ($i = count($leftHand)-1; $i >= 0; –$i) {
if ($card >= $leftHand[$i]) {
for ($j = 0; $j <= $i; ++$j) {
$reindexedLeftHand[$j] = $leftHand[$j];
}
$reindexedLeftHand[] = $card;
for ($j = $i+1; $j < count($leftHand); ++$j) {
$reindexedLeftHand[$j+1] = $leftHand[$j];
}
$insertedCard = true;
break;
}
}
if (false === $insertedCard) {
$reindexedLeftHand[] = $card;
foreach ($leftHand as $cardInLeftHand) {
$reindexedLeftHand[] = $cardInLeftHand;
}
}
$leftHand = $reindexedLeftHand;
}
}
return $leftHand;
}

Will result in:

array(10) {
  [0]=>
  int(0)
  [1]=>
  int(1)
  [2]=>
  int(2)
  [3]=>
  int(3)
  [4]=>
  int(4)
  [5]=>
  int(5)
  [6]=>
  int(6)
  [7]=>
  int(7)
  [8]=>
  int(8)
  [9]=>
  int(9)
}

Zend Framework Blog

TDD, PHPUnit, RESTful Web Services, MVC, PHP 5.4, Zend Framework 1 & 2, Doctrine 2, Python, Django, AWS, JavaScript, Git, Security, Algorithms and much more

Faster Autoloading With Zend Framework 2

Select a radio button with Mink / Behat

Introduction to boto (Python interface to AWS)

Access entity manager in Zend Framework 2 unit tests

How to unit test redirecting in Zend Framework 2

Create a self signed X509 certificate in Python

Merge sort PHP implementation

Comb sort PHP implementation

Shellsort PHP implementation

Insertion sort algorithm PHP implementation

Search

Recent Comments

Archives

Recent Posts

TDD, PHPUnit, RESTful Web Services, MVC, PHP 5.4, Zend Framework 1 & 2, Doctrine 2, Python, Django, AWS, JavaScript, Git, Security, Algorithms and much more

Search

Recent Comments

Tags

Categories

Archives