debuggable

Today in the morning I had a very unusual programming job to do - or at least what is for me rather unusual. I was confronted with the question whether it is easy to implement the quicksort algorithmn to sort an array of arrays based on a key in the second-dimension of the array. Join me to find out.

As you probably know from my About me page, I am currently working for LinkLift as a web programmer. The company is the largest German Textlink-Marketplace and soon we will expand to other countries within Europe. When you click on one of the link categories on our homepage, you are presented with (unfortunately German) website from which you can buy textlinks.

(Note: We are using the term “adspace” here for purchasable textlinks on a publisher's website.)

Using the links in the table header, you can sort the adspaces by title, available adspaces, page rank and current value.

Here is an array of adspaces, which we are willing to sort. The data is of course changed to preserve publisher anonymity.

[code]
Array
(
[0] => Array
(
[idv11] => 624059d1f8N0
[url] => http://example0.com,
[title] => Some title0,
[current_pagerank] => 7,
[adspots] => 2,
[current_available] => 1,
[links] => 33,
[links_external] => 5,
)
[1] => Array
(
[idv11] => 67059d1f8N0
[url] => http://example1.com,
[title] => Some title1,
[current_pagerank] => 4,
[adspots] => 4,
[current_available] => 3,
[links] => 132,
[links_external] => 9,
)
[2] => Array
(
[idv11] => 6759d1f8N0
[url] => http://example2.com,
[title] => Some title2,
[current_pagerank] => 2,
[adspots] => 8,
[current_available] => 6,
[links] => 12,
[links_external] => 3,
)
)
[/code]

The idv11 is the primary key. We decided to generate a random number for each new adspace so that our customers cannot guess how many adspaces we have in the marketplace by simply looking at their id. ;) The rest of the information should be straightforward - adspots is the number of textlinks the publisher offers on his site, current_available is the number of textlinks that can be purchased still, links is the number of links on the page where our textlinks will appear and links external is the number of those links that go to an external site.

The old sort algorithmn was rather slow and thus it was my task to optimize it. I tend to be used for optimisation tasks quite often these days.. Okay, so let's look at the old sort algorithmn:

The function might seem a bit overwhelming to you at first, but in fact it's all quite easy. Let's explore the code a bit.

What the function receives is an array of adspaces. Each adspace itself is an array again to hold its information as presented earlier. The second parameter is an integer determining what to sort by. The function call $sortUsBy = determineAdspaceSortBy($sortBy); maps that integer to one of the following strings: "current_available", "link_value", "title" or "current_pagerank". Unfortunately, I cannot show you all of the code, but the person above me will not allow me to do so. It is not a problem, though, in my opinion.

If the $sortBy integer is negative we will sort in descending order. If it is -1, we will sort by adspace "revenue" – the default sortation for each category. Sorting by revenue basically means sorting by the product of current_value * (adspots – current_available). As you can see, revenue in this case means the amount of revenue an adspace has generated for the company already.

Next we declare two arrays - orderedArray, which will be our result array of sorted adspaces, and usedIdv11s, which allows us to track duplicated publishers just in case our input array contained some publishers more than once.

Now the sortation begins. What my colleagues were doing is simply iterating over the array and for each iteration iterate over all existing publishers again, determine the publisher with the highest value to sort by, track it in the ordered array and remove it from the publisher array.

What that means is the number of iterations is n + (n-1) + (n-2) + ... + 1 = (n² + n)/2, where n is the number of adspaces of the input array. The average complexity class is therefore n² and thus the the performance gets a lot worse with increasing numbers of adspaces. By the way, note that the $numResultArray variable gets decreased with every iteration. If we did the outer iteration via

..we would have had another real performance bottleneck. Check my article Optimising For-Loops for more information on that one.

Okay, so now we are basically where I had been at 9:00am this morning. What I did at this point is turn to Wikipedia and searched for Quicksort, one of the fastest sorting algorithmns ever created. I simply remembered quicksort as being a fast sort algorithmn from my past computer science lessons at school. :) Quicksort is rather simple. It determines a random pivot element, then sorts the array so that all elements greater than the pivot are right from it and all which are less than the pivot's value are left to it. After such a sortation the pivot is at the correct place already and we have to sort the two sub-lists via the same approach.

Quicksort does that recursively and it is extremely fast, check the complexity and time analysis at the end of the wikipedia article there. I thought it will be a lot faster than the old publisher sortation algorithmn and off I went implementing quicksort. :)

What I turned up with is the following:

Should not be difficult to understand. We go through all adspaces, determine a pivot by simply using $pivot = $q[0], which takes the first element of the array. Then we determine a value to sort by - either we sort by adspace revenue, which uses our revenue formula or we sort by one of the adspace's keys (current_pagerank, link_value, current_available or title). If the recursion level is zero, we clean up duplicate adspaces and reverse the array if we are to sort in descending order.

The result? The sortation now is lightning fast with an average complexity class of n * log₂n, which is a lot better than n².

Hope you liked my little story from today's morning. Feel free to modify and use this code. :)