Will Oller .com

Learning to match the beat of the Old World man.

Jul 14, 2006

Sorting Algorithms: Laser Sort

Sorting

There are lots of sorting algorithms out there. Bubble, Shell, Heap, Quick, Library come readily to mind, and still the list goes on.

So, of course, I had to come across a sorting problem that I couldn’t solve with my Beginning Programming textbook. It’s not a particularly compex problem, and the solution is even simpler, but coming to that simple solution was not.

The Setup

First, here is an example of the type of data I am working with. This is the simplest part, because the data is as average run-of-the-mill as data can be.

ID	Article	Date Published
1	Willoller.com	12-July-2006
2	Wikipedia.com	31-Jan-2004
3	Redvsblue.com	14-Aug-2003

The $_POST is then passed to a function that works like this:function supersort( $post_in ) { foreach ( $post_in as $k => $i ) { // Iterate through the $_POST if ( is_numeric( $k ) ) { // If the key is a number $new[$k] = $i; // Push it onto $new } } asort($new); // Sort the array by the values


   $counter = 1;                         // Start with 1

   foreach ( $new as $k => $i ) {        // Iterate through $new

      $update[$k] = $count;              // Populate $update using $count, to be sure

      $count++;                          //    we get a nice sequence in the UPDATE

   }

}

Then it gets inserted into the DB using the $new[$key] and its value to create the UPDATE.

The Problem

“It appears to be working” you may say. “Don’t reinvent the wheel!” says the voice in my head.

And yes, all is well and good indeed, unless the user repeats numbers. That is, rather than inputting 2,1,3, they lazily input 1,1,3 with the expectation that the 2nd item will become the new 1st item, like so:

ID	Article	Date Published
2	Wikipedia.com	31-Jan-2004
1	Willoller.com	12-July-2006
3	Redvsblue.com	14-Aug-2003

In practice, the asort()’s outcome will be unreliable, and the new value will only swap places with the old value approximately half the time. So, how to force the new change to take precedence over the old change? To accomplish this, we will need to retrieve the previous values from the database, and use an array of commands.

The Solution.

Not everybody likes to dive right into the code. But, if you’re still reading this, you are not everybody.

/* $old is populated from the database $new comes from the form submission Both are of the format $primary_key => $sort_value */


   asort($new);
   $prev = false;
   foreach ($new as $k=>$i) {

      if ($new[$k] == 1 && $prev[1] == 1) {

         $update[] = array($prev[0], 2);

         $update[] = array($k, 1);

      }

      if($new[$k] == $old[$k] && $prev && prev[1] == $new[$k]) {

         $update[] = array($k, $i-1);

      }

      $prev = array($k, $i);

   }

   foreach ($update as $i) {

      $new[$i[0]] = $i[1];

   }

   $count = 1;

   foreach ($new as $k => $i) {

      $new[$k] = $count;

      $count++;

   }

Couldn’t be easier. But, for those of you not madly in love with php’s various array-handling methods, I will happily give a quick overview of what’s going on here.

First, we asort($new). Why not $old as well? Becaouse we never actually iterate on $old. Besides, you already ordered by sort in the query that generated $old, right?

Second, I found that the standard algorithm I devised choked when the first values were both 1, because the $prev variable has not been set yet and also because I don’t like negative numbers. So, there is a little bit of logic in there to make double-sure that the ordering goes smoothly when 1’s are the doubled number.

Third, the real good part. The algorithm checks to see if the sort value of a particular item has been updated, and if it has, it takes priority in the numbering, pushing the old number up to get out of the way. If 2 2’s are submitted, the newest 2 gets the spot and the old 2 becomes a 3.

These updates are passed by means of the update array. After the whole $new array is run through, the update array is traversed, and the $new array is augmented with the replacement values.

Finally, the numbers in the $new array are recalculated, starting from 1. This is also a double-check to be sure every number is in its place and no sort is ambiguous.