slow algorithm execution time

[drkstr]

Any algorithum junkies out there?

My algorithm I wrote takes about 20 seconds to run, but from what I can tell, it only goes though a few iterations. I'm pretty knew to PHP so maybe there are things I need to be carful of when iterating? Would anyone mind sanity checking it for me?

Here is what I'm doing:

The objects
------------------
DriveList
properties:
  private $myDisks = array(); #array of Disks

Disk
properties:
  var $myDiskName; #device name of disk
  var $myCyls; #number of cyllinders on disk
  var $myHeads; #number of heads on disk
  var $mySects;  #number of sectors per track
  var $mySize;  #size of disk in bytes
  var $myPartitions = array(); #array of partitions

Partition
properties:
  var $myInfo = array();

DriveList Contains an array of Disks which contains an array of partitions:

The algorithm
--------------------
The DriveList constructor reads in the partition table from the disk and fills in the info accordingly. This part works fine (only takes 1 - 2 seconds to run). The problem is, I need the array of Partitions (contained in Disk) to be sorted by location on the Disk, not the device name. So I wrote a sorting algorithm but it greatly reduces the execution time.

Note: the throwError function is just an error parsing routine I wrote for this project. Also note the following definitions:
#define info we can get from partition. #'s represent array elements
define('PNAME', 0);  # PNAME = Partition Name
define('SCYL', 1);  # SCYL = Start Cyllinder
define('ECYL', 2);  # ECYL = End Cyllinder
define('PSIZE', 4);  # PSIZE = Partition Size in Kb (Blocks)
define('FSTYP', 6);  # FSTYPE = File System Type

[code]<?php
#move new partition into correct place
    $length = count($this->myPartitions);
    if ( $this->myPartitions[$length-1]->myInfo[FSTYP] != 'Empty' ) { #if not Empty, sort by start cyllinder
      $end = $length-1;
      throwError("Primary Partition found at end = $end ".$this->myPartitions[$end]->myInfo[PNAME], DBG);
      #sift partition down until SCYL of $end-1 is not larger
      while ( ($end > 0) &&
              ($this->myPartitions[$end]->myInfo[SCYL] < $this->myPartitions[$end-1]->myInfo[SCYL] ||
              $this->myPartitions[$end-1]->myInfo[FSTYP] == 'Empty') # keep empty partitions at end of table
            ) {
        throwError("Primary Partition at end = $end ".$this->myPartitions[$end]->myInfo[PNAME].
                  " is now end = ". ($end-1), DBG);
        $tmpPart = $this->myPartitions[$end-1];
        $this->myPartitions[$end-1] = $this->myPartitions[$end];
        $this->myPartitions[$end] = $tmpPart;
        $end--;
      }
    }
    else { #if Empty partition, see if we can place it in some free space
      $end = $length-1; $strt = -1;
      throwError("Empty Partition found at end = $end ".$this->myPartitions[$end]->myInfo[PNAME], DBG);
      do {
        $strt++;
        throwError("Checking for empty space at strt = $strt ".$this->myPartitions[$strt]->myInfo[PNAME], DBG);
        #if this is the last item, see if space available at end of disk
        if ( $this->myPartitions[$strt]->myInfo[FSTYP] == 'Empty' ) {
          if ( $this->myPartitions[$strt]->myInfo[ECYL] < $this->myCyls - BUF ) {
            throwError("end of disk is empy strt = $strt", DBG);
            $this->myPartitions[$strt]->myInfo[SCYL] = $this->myPartitions[$strt-1]->myInfo[ECYL];
            $this->myPartitions[$strt]->myInfo[ECYL] = $this->myCyls;
            $this->myPartitions[$strt]->myInfo[FSTYP] = "Free Space";
            break; #found what we were looking for
          }
        }
        else if ( $this->myPartitions[$strt]->myInfo[ECYL] <  #if current partitions's end cyl is < the next partition's start cyl
            $this->myPartitions[$strt+1]->myInfo[SCYL] - BUF ) {  #then must be free space (BUF is tollerance on misalignment)
          throwError("Free space found after partition $strt ".$this->myPartitions[$strt]->myInfo[PNAME], DBG);
          #start at the end and shift up to make room for insertion
          $tmpPart = $this->myPartitions[$length-1];
          for ($end = $length-1; $end > $strt+1; $end-- ) {
            throwError("Sifting p $end " ." " .$this->myPartitions[$end]->myInfo[PNAME].
                      " is now p " .($end-1), DBG);
            $this->myPartitions[$end] = $this->myPartitions[$end-1];
          }
          #now that it's in place, update it's information
          $this->myPartitions[$end] = $tmpPart;
          $this->myPartitions[$end]->myInfo[SCYL] = $this->myPartitions[$end-1]->myInfo[ECYL];
          $this->myPartitions[$end]->myInfo[ECYL] = $this->myPartitions[$end+1]->myInfo[SCYL];
          $nSize = ($this->myPartitions[$end]->myInfo[ECYL] - $this->myPartitions[$end]->myInfo[SCYL])
                  * ($this->myHeads) * ($this->mySects);
          $this->myPartitions[$end]->myInfo[PSIZE] = $nSize;
          $this->myPartitions[$end]->myInfo[FSTYP] = "Free Space";
          break; #found what we were looking for
        }
      } while ( $strt < $length ); #failsafe if something goes wrong
    }
?>[/code]

Output:
[code] ** Debug: Primary Partition found at end = 0 /dev/hda1 **

** Debug: Primary Partition found at end = 1 /dev/hda2 **

** Debug: Primary Partition found at end = 2 /dev/hda3 **

** Debug: Primary Partition at end = 2 /dev/hda3 is now end = 1 **

** Debug: Empty Partition found at end = 3 /dev/hda4 **

** Debug: Checking for empty space at strt = 0 /dev/hda1 **

** Debug: Checking for empty space at strt = 1 /dev/hda3 **

** Debug: Free space found after partition 1 /dev/hda3 **

** Debug: Sifting p 3 /dev/hda4 is now p 2 ***[/code]

This is the partition table this output is based on:  from 
popen( "sudo /usr/sbin/sfdisk -l | grep dev", "r" )[code]Disk /dev/hda: 19485 cylinders, 16 heads, 63 sectors/track
/dev/hda1          0+    16463-  16464-  8297541  83  Linux
/dev/hda2      18407+  19484    1078-    542902+  82  Linux swap
/dev/hda3      16463+  18013-  1550    781200    83  Linux
/dev/hda4          0              -      0          0        0    Empty
[/code]

Thanks for your time!
...drkstr