Home PHP Page 3 - Collections and Sorting Continued

# Sort Algorithms of n log n Complexity - PHP

In the first part of this series we implemented a basic sortable collection class. We used a Bubble Sort algorithm to order the elements in the collection, which came with a disclaimer regarding what a slow sort it is. This article will examine the primary sorting algorithms with code examples, and some empirical data regarding how they perform in relation to one another, as well as the size of the data set in question.

By: David Fells
Rating:  / 7
April 04, 2006

SEARCH DEV SHED

TOOLS YOU CAN USE

Heap Sort:

public function HeapSort()
{
for (\$i = (\$this->data->count() / 2) - 1; \$i >= 0; \$i--)
\$this->HeapSortSiftDown(\$i, \$this->data->count());

for (\$i = \$this->data->count() - 1; \$i >= 1; \$i--)
{
\$tmp = \$this->data[0];
\$this->data->offsetSet(0, \$this->data[\$i]);
\$this->data->offsetSet(\$i, \$tmp);
\$this->HeapSortSiftDown(0, \$i - 1);
}
}

private function HeapSortSiftDown(\$i, \$arraySize)
{
\$done = 0;
while ((\$i * 2 <= \$arraySize) && (!\$done))
{
if (\$i * 2 == \$arraySize)
\$maxChild = \$i * 2;
elseif (strcmp(\$this->data[\$i * 2]->GetSortKey(),
\$this->data[\$i * 2 + 1]->GetSortKey()) > 0)
\$maxChild = \$i * 2;
else
\$maxChild = \$i * 2 +
1;

if (strcmp(\$this->data[\$i]->GetSortKey(),
\$this->data[\$maxChild]) < 0)
{
\$tmp = \$this->data[\$i];
\$this->data->offsetSet(\$i, \$this->data
[\$maxChild]);
\$this->data->offsetSet(\$maxChild, \$temp);
\$i = \$maxChild;
}
else
\$done = 1;
}
}

Merge Sort:

public function MergeSort()
{
\$this->MSort(\$this->data, array(), 0, \$this->data->count
() - 1);
}

private function MSort(\$data, \$temp, \$left, \$right)
{
if (\$right > \$left)
{
\$mid = (\$right + \$left) / 2;
\$this->MSort(\$data, \$temp, \$left, \$mid);
\$this->MSort(\$data, \$temp, \$mid + 1,
\$right);

\$this->Merge(\$data, \$temp, \$left, \$mid + 1,
\$right);
}
}
private function Merge(\$data, \$temp, \$left, \$mid, \$right)
{
\$leftEnd = \$mid - 1;
\$tmpPos = \$left;
\$numElements = \$right - \$left + 1;

while ((\$left <= \$leftEnd) && (\$mid <= \$right))
{
if (strcmp(\$data[\$left]->GetSortKey(),
\$data[\$mid]->GetSortKey()) <= 0)
{
\$temp[\$tmpPos] = \$data[\$left];
\$tmpPos++;
\$left++;
}
else
{
\$temp[\$tmpPos] = \$data[\$mid];
\$tmpPos++;
\$mid++;
}
}

while (\$left <= \$leftEnd)
{
\$temp[\$tmpPos] = \$data[\$left];
\$left++;
\$tmpPos++;
}
while (\$mid <= \$right)
{
\$tmp[\$tmpPos] = \$data[\$mid];
\$mid++;
\$tmpPos++;
}
for (\$i = 0; \$i <= \$numElements; \$i++)
{
\$data->offsetSet(\$right, \$temp[\$right]);
\$right--;
}
}

Quick Sort:

public function QuickSort()
{
\$this->QSort(\$this->data, 0, \$this->data->count() -
1);
}

private function QSort(\$data, \$left, \$right)
{
\$lHold = \$left;
\$rHold = \$right;
\$pivot = \$data[\$left];

while (\$left < \$right)
{
while ((strcmp(\$data[\$right]->GetSortKey(),
\$pivot->GetSortKey()) >= 0) &&
(\$left < \$right))
{
\$right--;
}
if (\$left != \$right)
{
\$data->offsetSet(\$left, \$data[\$right]);
\$left++;
}
while ((strcmp(\$data[\$left]->GetSortKey(),
\$pivot->GetSortKey()) <= 0) &&
(\$left > \$right))
{
\$left++;
}
if (\$left != \$right)
{
\$data->offsetSet(\$right, \$data[\$left]);
\$right--;
}
}

\$data->offsetSet(\$left, \$pivot);
\$pivot = \$left;
\$left = \$lHold;
\$right = \$rHold;
if (\$left < \$pivot)
\$this->QSort(\$data, \$left, \$pivot - 1);
if (\$right > \$pivot)
\$this->QSort(\$data, \$pivot + 1, \$right);
}

In order to test these algorithms, I simply added them to my class and then in Sort(), called whichever one I wanted to use.

 >>> More PHP Articles          >>> More By David Fells