Code Coverage for /var/www/html/dev/src/phpOMS/Algorithm/Sort/IntroSort.php

1	<?php
2	/**
3	* Jingga
4	*
5	* PHP Version 8.1
6	*
7	* @package phpOMS\Algorithm\Sort;
8	* @copyright Dennis Eichhorn
9	* @license OMS License 2.0
10	* @version 1.0.0
11	* @link https://jingga.app
12	*/
13	declare(strict_types=1);
14
15	namespace phpOMS\Algorithm\Sort;
16
17	/**
18	* IntroSort class.
19	*
20	* @package phpOMS\Algorithm\Sort;
21	* @license OMS License 2.0
22	* @link https://jingga.app
23	* @since 1.0.0
24	*/
25	final class IntroSort implements SortInterface
26	{
27	/**
28	* Constructor
29	*
30	* @since 1.0.0
31	* @codeCoverageIgnore
32	*/
33	private function __construct()
34	{
35	}
36
37	/**
38	* {@inheritdoc}
39	*/
40	public static function sort(array $list, int $order = SortOrder::ASC) : array
41	{
42	$clone = $list;
43	$size = self::partition($clone, 0, \count($list) - 1, $order);
44
45	if ($size < 16) {
46	return InsertionSort::sort($clone, $order);
47	}
48
49	if ($size > \log(\count($list)) * 2) {
50	return HeapSort::sort($clone, $order);
51	}
52
53	return QuickSort::sort($clone);
54	}
55
56	/**
57	* Partition list and return the size
58	*
59	* @param array $list List reference
60	* @param int $lo Low or left side
61	* @param int $hi High or right side
62	* @param int $order Order type
63	*
64	* @return int
65	*
66	* @since 1.0.0
67	*/
68	private static function partition(array &$list, int $lo, int $hi, int $order) : int
69	{
70	$pivot = $list[$hi];
71	$i = $lo;
72
73	for ($j = $lo; $j < $hi; ++$j) {
74	if ($list[$j]->compare($pivot, $order)) {
75	$temp = $list[$j];
76	$list[$j] = $list[$i];
77	$list[$i] = $temp;
78
79	++$i;
80	}
81	}
82
83	$list[$hi] = $list[$i];
84	$list[$i] = $pivot;
85
86	return $i;
87	}
88	}