Yes! It’s really really fast, and it’s far quicker than the quicksort algorithm, which is considered as the fastest sorting algorithm in practice. However how it’s possible to be faster than the quicksort, which is the fastest algorithm?! Is that true? Actually it’s true, but only in few cases. It works with integers, you’ve to know the first and the last element from that set and you’ve to be sure that every element is unique

Imagine you’ve a set of numbers all of them greater than 1 and lesser than 1000. Of course you’re not suppose to have all of the integers between 1 and 1000, but only few of them – think of 500 numbers between 1 and 1000! Here’s important to note – that this is only an example, you can have far more than only few numbers between 1 and 1000 – what about the numbers between 1 and 1,000,000 – this is a big set, isn’t it.

The question is – if there are so many constraints, why should I use that algorithm instead of quicksort, or another sorting algorithm, that works with everything. The answer is clear – yes, you’d prefer quicksort if you’ve to sort some arbitrary data, but when it comes to integers, and you’ve, let’s say, 1,000,000 integers, my advice is – use this algorithm!

Sorting the Set

1. First Pass

First we have an unsorted array, but we know the minimum and maximum of the set.

On the first pass initialize an empty array with as many elements, as they are between the first and the last element of the set – for a set between 1 and 1000 – that will be an array with 1000 elements – each of which will be a zero in the beginning.

Than loop trough the set and for every element in the set – you should put a 1 on it’s place

Now we have an array of 0 and 1.

2. Second Pass

After the first pass, you’d guess what you’ve to do – loop trough the second array and print the keys of the elements different from 0 – those that are 1.

Now the array is sorted!

Source Code

var a = [34, 203, 3, 746, 200, 984, 198, 764];
 
function setSort(arr)
{
    var t = [], len = arr.length;
    for (var i = 0; i < 1000; i++) {
        t[i] = 0;
    }
 
    for (i = 0; i < len; i++) {
        t[arr[i]] = 1;
    }
 
    for (i = 0; i < 1000; i++) {
        if (1 == t[i]) {
            console.log(i);
        }
    }
}
 
setSort(a);

Now that you’ve seen that algorithm, perhaps you’d guess that it’s no so difficult to change from integers to any other set, and once again I should say that in many cases this is the best algorithm for sorting! Very often quicksort is preferred, but not always there isn’t something faster!

There is a view helper that can inject a head or inline script into your code.

Simply by putting some JavaScript code into the view script wont do the job, because the .phtml file is grabbed and parsed by the Zend Framework and thus the code there wont be parsed as JavaScript and it wont be executed as well by the browser.

The Most Simple Way …

is to put some place holder into the layout .phtml file and than from the controller’s action you can assign some JS code:

// layout.phtml
<?php
...
echo $this->layout()->scriptTags;
...

<?php
 
class IndexController extends Zend_Controller_Action
{
	public function indexAction() 
	{
		$this->view->layout()->scriptTags = '<script src="my.js"></script>';	
	}	
}

Solution No. 2

Although the first solution is correct it’s not the most clearest way, because you put the JavaScript code into the PHP, and this sooner or later becomes a mess.

<?php
 
class IndexController extends Zend_Controller_Action
{
	public function indexAction() 
	{
		$this->view->layout()->scriptTags = '<script src="my.js"></script>';
						  . '<script>alert("here\'s my" + "test")</script>';
	}	
}

The IDE is not highlighting the code, and you’ve to deal with too many quotes, which is bad! There is a better solution however – the inline script:

// script tags
/* @var $scripts Zend_View_Helper_InlineScript */
$scripts = $this->view->inlineScript();
$scripts->appendFile('my.js');

Simply the Best

Yeah, the best solution is something even better than the second one. Although the solution I’ve just mentioned is fine for including JS files, when you’ve to add some JS code you’ll have to put it again into the PHP.

$msg = 'some dynamically generated message';
 
// script tags
/* @var $scripts Zend_View_Helper_InlineScript */
$scripts = $this->view->inlineScript();
$scripts->appendFile('my.js');
$scripts->appendScript('alert("' . $msg . '")');

If there’s no relation between JavaScript and PHP you can simply put all this code into a separate .js file and load it from there. This is by the way the best solution because the file is cached by the browser, if the cache is enabled. But most of the time you perhaps have to send some variables from PHP to the JavaScript code.

It would be perfect if you had some kind of a variable placeholders – exactly as you have it in the Zend Framework’s view scripts!

Another View

This is completely possible – just forget about the default view – it renders the view script and it’s bind to the /views/scripts folder. You can make another, completely new, view instead! Here’s some source:

$view = new Zend_View();
$view->setBasePath('path_to_the_js_folder');
 
$view->msg = 'Some dynamically generated message';
 
// script tags
/* @var $scripts Zend_View_Helper_InlineScript */
$scripts = $this->view->inlineScript();
$scripts->appendFile('my.js');
$scripts->appendScript($view->render('inline.js'));

Thus now in the JS file you can have some placeholders!

// inline.js
 
// some js code
// ...
alert('<?php echo $this->msg ?>');

What’s the Task?

First of all let me explain what is the task. If there’s a select menu with several options, each of which are with a given value attribute, the task is to get the text into the option tag, and not that of the value attribute.

In that scenario let’s assume that we have the following HTML:

<select id="my-select">
    <option value="1">value 1</option>
    <option value="2">value 2</option>
</select>

Note that in the official jQuery doc page, the selector is described in the same context, but with a different markup:

<select id="my-select">
    <option>value 1</option>
    <option>value 2</option>
</select>

than the jQuery snippet looks like that:

$(document).ready(function() {
    $("#my-select").change(function() {
        alert($(this).val());
    });
});

Here’s interesting to note that there’s no value attribute set to the options, thus the selection of an element is correct and the returned value is correct. The problem is that this code doesn’t work correctly once you’ve a different value attribute, from the value enclosed into the option tag. In our case we’ve the markup shown on the first code snippet and we’d like to get the “value 2″ string instead of “2″.

Source Code

<select id="my-select">
    <option value="1">value 1</option>
    <option value="2">value 2</option>
</select>

$(document).ready(function() {
    $("#my-select").change(function() {
        alert($(this).val());
    });
});

Solution

Finally the solution, is pretty simple and clear, but this time is not to so “native” and it’s definitely something you couldn’t expect! The only thing you’ve to do is to change the selector!

$(document).ready(function() {
    $("#my-select).change(function() {
        alert($('#my-select option:selected').html());
    });
});

Short Experiment

Here’s a short optimization of a small chunk of jQuery code. The experiment was to increment the number of DOM element access. In this case this was a change of the innerHTML property – using the $.html() method.

I’ve measured the result with the console.time() method and thus I expect correct results for both cases. In the first case I directly call the jQuery selectors’ html() method:

for (var i = 0; i < 10000; i++) {
    $('#container').html(i);
}

While in the second case I “cache” it before the loop:

var t = $('#container');
for (var i = 0; i < 10000; i++) {
    t.html(i);
}

and here’s the full code in the first case:

<html>
<head>
    <title>jQuery Cache</title>
</head>
<body>
 
<div id="container"></div>
 
<script src="/scripts/library.js"></script>
<script>
 
$(document).ready(function() {
 
    console.time('foo');
    for (var i = 0; i < 10000; i++) {
        $('#container').html(i);
    }
    console.timeEnd('foo');
});
</script>
</body>
</html>

The Results

As expected the second “cached” approach gave better results. With the increment of the iterations the second method began to be slightly better than the first one. That’s not so much, but imagine you have more than one selector in the loop’s body?

Numbers:

Note that in the time is in ms, and, yes, this is not so much, but when you deal with large data and you’ve more than one selector in the loop’s body, this can be critical!

Graphics:

Sorting Algorithms

Last Friday I wrote a quick post showing the recursive version of quicksort on both PHP and JavaScript, but this time let me begin with some breve history. Actually sorting and searching algorithms are widely used in the computer science and are developed and improved many times in the last 60 years or so. As the world goes so wired, all the information around is stored in data bases and the need of fast search methods is critical. But as we all know from our experience, it is far more easy to search into a sorted data structure. Such are all the dictionaries we use. Can you, actually, imagine to search for a word in a dictionary where all the words don’t follow the alphabetical order and are dispersed chaotically instead?

That’s why from the early years of computer science both sorting and searching algorithms go together. I’ll cover more on search algorithms in the future, but as I started with quicksort – one of the many sorting algorithms, let me mention that this algorithm is not anonymous! What I mean is that his author is well known and he’s recognized in the computer science community. His name is …

C. A. R. Hoare

Sir Charles Antony Richard Hoare is born on the 11 of January 1934 in Ceylon, now Sri Lanka, and after finishing his studies in the University of Oxford and being in the Royal Navy for two years, he went to … Moscow where at the age of 26 (in 1960) he developed the famous quicksort algorithm. That’s not everything! Beside the sorting algorithm he’s well recognized with the Hoare logic and the invention of the formal language CSP (Communicating Sequential Processes).

Here’s what Sir C. A. R. Hoare wrote in his lecture “The Emperor’s Old Clothes” published by Communications of the ACM in 1981:

My first task was to implement for the new Elliot 803 computer, a library subroutine for a new fast method of internal sorting just invented by Shell. I greatly enjoyed the challenge of maximizing efficiency in the simple decimal-addressed machine code of those days. My boss and tutor, Pat Shackleton, was very pleased with my completed program. I then said timidly that I thought I had invented a sorting method that would usually run faster than SHELLSORT, without taking much extra store. He bet me sixpence that I had not. Although my method was very difficult to explain, he finally agreed that I had won my bet.

The quicksort was born!

Recursive vs. Iterative

There are two main directions in solving such problems as the sorting algorithms. Recursive way and the iterative way. Every developer knows what is recursive and what’s iterative. We like to say that recursive is more “elegant” solution, than the iterative, but it’s interesting to say that both are completely interchangeable. Yeah, every recursion can be modeled with a stack (as the recursion is always converted into a stack on the machine level), and every loop can be converted to a recursion. It’s interesting to say that the second direction is easier, while the switch from recursion to stack it’s not always obvious and easy!

Here’s a code snippet from the recursive version of the quicksort, I’ve posted last Friday:

return quicksort(left).concat(pivot, quicksort(right));

What actually happens here is that the second call of quicksort() is always delayed for a later execution. Until the first quicksort() doesn’t finish his job, the second is never used! Why than we need a recursion? Why don’t we put the right part of the array in a stack for later execution? In fact this is the solution! Every right part will be put into a stack. Thus while the stack has some elements we pop an element from it and than split it again on two – left and right: the right part enters the stack and the left is yet again sorted.

In that scenario we end with an element split when the left part is with only one element. Here’s important to say that this might not be the perfect solution and there might be some quite good optimizations!

Assuming we’ve the following array – [8,4,6,2,1,9,5], here’s what happens, note that in JavaScript array.pop() pops the rightmost element, in this case 5:

stack = [[8,4,6,2,1,9,5]]
sorted = [];
 
1. step
stack = [5,8,6,9][4,2,1]
sorted = []
 
2. step
stack = [5,8,6,9][4][2,1]
sorted = []
 
3. step
stack = [5,8,6,9][4][2][1]
sorted = []
 
4. step
stack = [8,6,9][5]
sorted = [1,2,4]
 
5. step
stack [8,9][6]
sorted = [1,2,4,5]
...

Code

Here’s the implementation of the iterative version, again on both PHP and JavaScript:

JavaScript:

var a = [8,4,6,2,1,9,5,5,4,3,4,3];
 
function qsort(arr)
{
    var stack = [arr];
    var sorted = [];
 
    while (stack.length) {
 
        var temp = stack.pop(), tl = temp.length;
 
        if (tl == 1) {
            sorted.push(temp[0]);
            continue;
        }
        var pivot = temp[0];
        var left = [], right = [];
 
        for (var i = 1; i < tl; i++) {
            if (temp[i] < pivot) {
                left.push(temp[i]);
            } else {
                right.push(temp[i]);
            }
        }
 
        left.push(pivot);
 
        if (right.length)
            stack.push(right);
        if (left.length)
            stack.push(left);
 
    }
 
    console.log(sorted);
}
qsort(a);

PHP:

$unsorted = array(8,4,6,2,1,9,5,5,4,3,4,3);
 
function qsort($array)
{
    $stack = array($array);
    $sorted = array();
 
    while (count($stack) > 0) {
 
        $temp = array_pop($stack);
 
        if (count($temp) == 1) {
            $sorted[] = $temp[0];
            continue;
        }
 
        $pivot = $temp[0];
        $left = $right = array();
 
        for ($i = 1; $i < count($temp); $i++) {
            if ($pivot > $temp[$i]) {
                $left[] = $temp[$i];
            } else {
                $right[] = $temp[$i];
            }
        }
 
        $left[] = $pivot;
 
        if (count($right))
            array_push($stack, $right);
        if (count($left))
            array_push($stack, $left);
    }
 
    return $sorted;
}
 
$sorted = qsort($unsorted);
print_r($sorted);

First of all this is more code than the recursive solution, and besides that it’s perhaps not the optimal solution – I’ll cover in the future more on how to optimize it and where it can be useful.

Till next Friday!