Code Coverage |
||||||||||
Classes and Traits |
Functions and Methods |
Lines |
||||||||
Total | |
0.00% |
0 / 1 |
|
52.63% |
10 / 19 |
CRAP | |
78.34% |
170 / 217 |
Sortable | |
0.00% |
0 / 1 |
|
52.63% |
10 / 19 |
112.61 | |
78.34% |
170 / 217 |
__construct | |
100.00% |
1 / 1 |
1 | |
100.00% |
2 / 2 |
|||
count | |
0.00% |
0 / 1 |
20 | |
0.00% |
0 / 11 |
|||
reverse | |
0.00% |
0 / 1 |
2 | |
0.00% |
0 / 1 |
|||
findLastElement | |
0.00% |
0 / 1 |
30 | |
0.00% |
0 / 13 |
|||
isSorted | |
0.00% |
0 / 1 |
2 | |
0.00% |
0 / 1 |
|||
isUnique | |
0.00% |
0 / 1 |
20 | |
0.00% |
0 / 13 |
|||
bucketSort | |
100.00% |
1 / 1 |
3 | |
100.00% |
11 / 11 |
|||
quick3Sort | |
0.00% |
0 / 1 |
2 | |
0.00% |
0 / 1 |
|||
quickSort | |
100.00% |
1 / 1 |
5 | |
100.00% |
21 / 21 |
|||
split | |
0.00% |
0 / 1 |
4.05 | |
85.71% |
18 / 21 |
|||
append | |
100.00% |
1 / 1 |
3 | |
100.00% |
11 / 11 |
|||
merge | |
0.00% |
0 / 1 |
8.14 | |
86.96% |
20 / 23 |
|||
mergeSort | |
100.00% |
1 / 1 |
2 | |
100.00% |
6 / 6 |
|||
bubbleSort | |
100.00% |
1 / 1 |
4 | |
100.00% |
14 / 14 |
|||
selectionSort | |
100.00% |
1 / 1 |
4 | |
100.00% |
16 / 16 |
|||
shellSort | |
100.00% |
1 / 1 |
7 | |
100.00% |
25 / 25 |
|||
insertionSortArray | |
100.00% |
1 / 1 |
4 | |
100.00% |
11 / 11 |
|||
insertionSort | |
100.00% |
1 / 1 |
5 | |
100.00% |
15 / 15 |
|||
heapSort | |
0.00% |
0 / 1 |
2 | |
0.00% |
0 / 1 |
<?php | |
namespace Mtkocak\DataStructures; | |
class Sortable | |
{ | |
private $dataStructure; | |
public function __construct(DataStructure $dataStructure) | |
{ | |
$this->dataStructure = $dataStructure; | |
} | |
/** | |
* If there is not a length property | |
*/ | |
public function count() | |
{ | |
if (! method_exists($this->dataStructure, 'count')) { | |
$count = 0; | |
$this->dataStructure->rewind(); | |
if (! $this->dataStructure->isEmpty()) { | |
while ($this->dataStructure->current()) { | |
$count ++; | |
$this->dataStructure->next(); | |
} | |
} | |
return $count; | |
} else { | |
return $this->dataStructure->count(); | |
} | |
} | |
public function reverse() | |
{ | |
// all next should be prev | |
// all prev should be next | |
// top should be bottom | |
// bottom should be top | |
} | |
/** | |
* If there is not a pointer to show last element | |
*/ | |
public function findLastElement() | |
{ | |
if (! method_exists($this->dataStructure, 'top')) { | |
if (! $this->dataStructure->isEmpty()) { | |
$this->dataStructure->rewind(); | |
while ($this->dataStructure->current()) { | |
if ($this->dataStructure->current()->next() == NULL) { | |
return $this->dataStructure->current()->get(); | |
} | |
$this->dataStructure->next(); | |
} | |
} else { | |
return $dataStructure->bottom(); | |
} | |
} else { | |
return $dataStructure->top(); | |
} | |
return false; | |
} | |
public function isSorted() | |
{} | |
public function isUnique() | |
{ | |
$values = []; | |
if (! $this->dataStructure->isEmpty()) { | |
$this->dataStructure->rewind(); | |
while ($this->dataStructure->current()) { | |
$value = $this->dataStructure->current()->get(); | |
if (! isset($value[$value])) { | |
$values[$value] = 1; | |
} else { | |
return false; | |
} | |
$this->dataStructure->next(); | |
} | |
} | |
} | |
public function bucketSort() | |
{ | |
$count = $this->dataStructure->count(); | |
$bucket = []; | |
for ($i = 1; $i <= $count; $i ++) { | |
$bucket[$i] = 0; | |
} | |
$current = $this->dataStructure->bottom; | |
while ($current) { | |
$bucket[$current->get()] ++; | |
$current = $current->next(); | |
} | |
return array_keys($bucket); | |
} | |
public function quick3Sort(DataStructure $dataStructure) | |
{} | |
public function quickSort(DataStructure $dataStructure) | |
{ | |
if ($dataStructure->isEmpty()) { | |
return $dataStructure; | |
} | |
$listToReturn = new DoubleLinkedList(); | |
$smallerList = new DoubleLinkedList(); | |
$biggerList = new DoubleLinkedList(); | |
$current = $dataStructure->bottom; | |
$pivot = $current->get(); | |
$listToReturn->add($pivot); | |
while ($current) { | |
if ($current->get() < $pivot) { | |
$smallerList->add($current->get()); | |
} elseif ($current->get() > $pivot) { | |
$biggerList->add($current->get()); | |
} | |
$current = $current->next(); | |
} | |
$sortedFirst = $this->quickSort($smallerList); | |
$sortedSecond = $this->quickSort($biggerList); | |
$listToReturn = $this->append($sortedFirst, $listToReturn); | |
$listToReturn = $this->append($listToReturn, $sortedSecond); | |
return $listToReturn; | |
} | |
private function split(DataStructure $dataStructure) | |
{ | |
if ($dataStructure->count() == 1) { | |
$arrayToReturn['firstPart'] = $dataStructure; | |
$arrayToReturn['secondPart'] = NULL; | |
} | |
$arrayToReturn = []; | |
$count = $dataStructure->count(); | |
$middle = ceil($count / 2); | |
$arrayToReturn['firstPart'] = new DoubleLinkedList(); | |
$arrayToReturn['secondPart'] = new DoubleLinkedList(); | |
$current = $dataStructure->bottom; | |
$counter = 1; | |
while ($current) { | |
$value = $current->get(); | |
if ($counter <= $middle) { | |
$arrayToReturn['firstPart']->add($value); | |
} else { | |
$arrayToReturn['secondPart']->add($value); | |
} | |
$counter ++; | |
$current = $current->next(); | |
} | |
return $arrayToReturn; | |
} | |
private function append(DataStructure $first, DataStructure $second) | |
{ | |
$listToReturn = new DoubleLinkedList(); | |
if ($first->isEmpty()) { | |
$listToReturn = $second; | |
} elseif ($second->isEmpty()) { | |
$listToReturn = $first; | |
} else { | |
$second->bottom->prev($first->top); | |
$first->top->next($second->bottom); | |
$listToReturn->bottom = $first->bottom; | |
$listToReturn->top = $second->top; | |
} | |
return $listToReturn; | |
} | |
/** | |
* Merges two sorted linked lists non recursively | |
*/ | |
private function merge(DataStructure $first, DataStructure $second) | |
{ | |
$listToReturn = new DoubleLinkedList(); | |
if ($first == NULL) { | |
$listToReturn = $second; | |
} elseif ($second == NULL) { | |
$listToReturn = $first; | |
} else { | |
while (! $first->isEmpty() && ! $second->isEmpty()) { | |
// echo $first->bottom()." and ".$second->bottom()."\n"; | |
if ($first->bottom() < $second->bottom()) { | |
$listToReturn->push($first->bottom()); | |
$first->delete(); | |
} else { | |
$listToReturn->push($second->bottom()); | |
$second->delete(); | |
} | |
} | |
while (! $first->isEmpty()) { | |
$listToReturn->push($first->bottom()); | |
$first->delete(); | |
} | |
while (! $second->isEmpty()) { | |
$listToReturn->push($second->bottom()); | |
$second->delete(); | |
} | |
} | |
return $listToReturn; | |
} | |
/** | |
* Does not change object's loaded datastructure. | |
* Is a recursive function. | |
*/ | |
public function mergeSort(DataStructure $dataStructure) | |
{ | |
if ($dataStructure->count() == 1) { | |
return $dataStructure; | |
} | |
$array = $this->split($dataStructure); | |
$first = $this->mergeSort($array['firstPart']); | |
$second = $this->mergeSort($array['secondPart']); | |
return $this->merge($first, $second); | |
} | |
public function bubbleSort() | |
{ | |
$current = $this->dataStructure->bottom; | |
while ($current) { | |
$selectedToCompare = $current->next(); | |
while ($selectedToCompare) { | |
if ($current->get() > $selectedToCompare->get()) { | |
$temp = $selectedToCompare->get(); | |
// echo $current->get()." and ".$temp." swapped\n"; | |
$selectedToCompare->set($current->get()); | |
$current->set($temp); | |
} | |
$selectedToCompare = $selectedToCompare->next(); | |
} | |
$current = $current->next(); | |
} | |
} | |
public function selectionSort() | |
{ | |
$current = $this->dataStructure->bottom; | |
while ($current) { | |
$minElement = $current; | |
$selectedToCompare = $current->next(); | |
while ($selectedToCompare) { | |
if ((int) $minElement->get() > (int) $selectedToCompare->get()) { | |
$minElement = $selectedToCompare; | |
} | |
$selectedToCompare = $selectedToCompare->next(); | |
} | |
$tmp = $current->get(); | |
$current->set($minElement->get()); | |
$minElement->set($tmp); | |
$current = $current->next(); | |
} | |
} | |
public function shellSort() | |
{ | |
$gaps = [ | |
701, | |
301, | |
132, | |
57, | |
23, | |
10, | |
4, | |
1 | |
]; | |
$array = $this->dataStructure; | |
foreach ($gaps as $gap) { | |
if ($gap < count($array)) { | |
for ($k = 0; $k < $gap; $k ++) { | |
for ($i = 1 + $k; $i < count($array); $i = $i + $gap) { | |
for ($j = $i; $j >= 1; $j = $j - $gap) { | |
if ($array[$j] < $array[$j - 1]) { | |
$tmp = $array[$j]; | |
$array[$j] = $array[$j - 1]; | |
$array[$j - 1] = $tmp; | |
} | |
} | |
} | |
} | |
} | |
} | |
} | |
public function insertionSortArray() | |
{ | |
$array = $this->dataStructure; | |
for ($i = 1; $i < count($array); $i ++) { | |
for ($j = $i; $j >= 1; $j --) { | |
if ($array[$j] < $array[$j - 1]) { | |
$tmp = $array[$j]; | |
$array[$j] = $array[$j - 1]; | |
$array[$j - 1] = $tmp; | |
} | |
} | |
} | |
} | |
public function insertionSort() | |
{ | |
$current = $this->dataStructure->bottom; | |
while ($current) { | |
// echo $current->get()."\n"; | |
$selectedToCompare = $current; | |
while ($selectedToCompare) { | |
if ($selectedToCompare->prev() != NULL && $selectedToCompare->get() < $selectedToCompare->prev()->get()) { | |
$tmp = $selectedToCompare->get(); | |
$selectedToCompare->set($selectedToCompare->prev() | |
->get()); | |
$selectedToCompare->prev()->set($tmp); | |
} | |
// echo "\t".$selectedToCompare->get()."\n"; | |
$selectedToCompare = $selectedToCompare->prev(); | |
} | |
$current = $current->next(); | |
} | |
} | |
public function heapSort() | |
{} | |
} |