Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00% covered (success)
100.00%
22 / 22
100.00% covered (success)
100.00%
3 / 3
 CRAP
100.00% covered (success)
100.00%
1 / 1
QuickSort
100.00% covered (success)
100.00%
22 / 22
100.00% covered (success)
100.00%
3 / 3
 8
100.00% covered (success)
100.00%
1 / 1
 __construct
n/a
0 / 0
n/a
0 / 0
 1
 sort
100.00% covered (success)
100.00%
6 / 6
100.00% covered (success)
100.00%
1 / 1
 2
 qsort
100.00% covered (success)
100.00%
4 / 4
100.00% covered (success)
100.00%
1 / 1
 2
 partition
100.00% covered (success)
100.00%
12 / 12
100.00% covered (success)
100.00%
1 / 1
 3
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 */
13declare(strict_types=1);
14
15namespace phpOMS\Algorithm\Sort;
16
17/**
18 * QuickSort class.
19 *
20 * @package phpOMS\Algorithm\Sort;
21 * @license OMS License 2.0
22 * @link    https://jingga.app
23 * @since   1.0.0
24 */
25final class QuickSort 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        $n = \count($list);
43
44        if ($n < 2) {
45            return $list;
46        }
47
48        $copy = $list;
49        self::qsort($copy, 0, $n - 1, $order);
50
51        return $copy;
52    }
53
54    /**
55     * Recursive quick sort
56     *
57     * @param array $list  Data to sort
58     * @param int   $lo    Low or left point to sort
59     * @param int   $hi    High or right point to sort
60     * @param int   $order Sort order
61     *
62     * @return void
63     *
64     * @since 1.0.0
65     */
66    private static function qsort(array &$list, int $lo, int $hi, int $order) : void
67    {
68        if ($lo < $hi) {
69            $i = self::partition($list, $lo, $hi, $order);
70            self::qsort($list, $lo, $i - 1, $order);
71            self::qsort($list, $i + 1, $hi, $order);
72        }
73    }
74
75    /**
76     * Partition data and count the partitions
77     *
78     * @param array $list  Data to sort
79     * @param int   $lo    Low or left point to sort
80     * @param int   $hi    High or right point to sort
81     * @param int   $order Sort order
82     *
83     * @return int
84     *
85     * @since 1.0.0
86     */
87    private static function partition(array &$list, int $lo, int $hi, int $order) : int
88    {
89        $pivot = $list[$hi];
90        $i     = $lo - 1;
91
92        for ($j = $lo; $j <= $hi - 1; ++$j) {
93            if (!$list[$j]->compare($pivot, $order)) {
94                ++$i;
95                $old      = $list[$i];
96                $list[$i] = $list[$j];
97                $list[$j] = $old;
98            }
99        }
100
101        $old          = $list[$i + 1];
102        $list[$i + 1] = $list[$hi];
103        $list[$hi]    = $old;
104
105        return $i + 1;
106    }
107}