Advanced Sorting and Searching Algorithms in PHP: Quick Sort, Merge Sort, Heap Sort, and Binary Search Trees

Advanced Sorting and Searching Algorithms in PHP: Quick Sort, Merge Sort, Heap Sort, and Binary Search Trees

On26th Nov 2024, 2024-12-04T09:52:41+05:30 ByKarthik Kumar D K | read
Listen Pause Resume Stop

Sorting and searching are foundational operations in computer science. Understanding the efficient algorithms for these tasks can significantly enhance the performance of your applications.

In this article, we’ll explore three advanced sorting algorithms — Quick Sort, Merge Sort, and Heap Sort — and dive into implementing Binary Search Trees (BST) in PHP 8.

We’ll include clear explanations along with sample code for each algorithm. This will help you not only understand their inner workings but also implement them efficiently in your projects.

1. Quick Sort

  • Quick Sort is a divide-and-conquer algorithm that selects a pivot element and partitions the array into two subarrays, one containing elements smaller than the pivot and the other containing elements greater than the pivot.
  • It recursively sorts these subarrays.
  • Quick Sort is efficient, with an average time complexity of O(n log n), though in the worst case (when the pivot is poorly chosen), it can degrade to O(n²).

Quick Sort Implementation in PHP8:

function quickSort(array $arr): array {

    if (count($arr) < 2) {

        return $arr; // Base case: a single element is already sorted

    }

    $pivot = $arr[0]; // Take the first element as the pivot

    $left = $right = [];

    // Partitioning step

    foreach (array_slice($arr, 1) as $value) {

        if ($value < $pivot) {

            $left[] = $value;

        } else {

            $right[] = $value;

        }

    }

    // Recursively apply quickSort to the left and right subarrays, then concatenate

    return array_merge(quickSort($left), [$pivot], quickSort($right));

}

$numbers = [10, 3, 15, 7, 8, 23, 74, 18];

$sorted = quickSort($numbers);

print_r($sorted);

2. Merge Sort

  • Merge Sort is another divide-and-conquer algorithm.
  • It works by recursively dividing the array in half until each subarray has only one element.
  • Then, it merges the sorted subarrays back together.
  • Merge Sort has a guaranteed time complexity of O(n log n), even in the worst case.

Merge Sort Implementation in PHP8:

function mergeSort(array $arr): array {

    // Base case: single element or empty array is already sorted

    if (count($arr) < 2) {

        return $arr;

    }

    $mid = floor(count($arr) / 2);

    $left = array_slice($arr, 0, $mid);

    $right = array_slice($arr, $mid);

    // Recursively split and merge the arrays

    return merge(mergeSort($left), mergeSort($right));

}

function merge(array $left, array $right): array {

    $result = [];

    while (count($left) > 0 && count($right) > 0) {

        if ($left[0] < $right[0]) {

            $result[] = array_shift($left);

        } else {

            $result[] = array_shift($right);

        }

    }

    // Append remaining elements

    return array_merge($result, $left, $right);

}

$numbers = [10, 3, 15, 7, 8, 23, 74, 18];

$sorted = mergeSort($numbers);

print_r($sorted);

3. Heap Sort

  • Heap Sort is based on the binary heap data structure, where the heap is a complete binary tree.
  • It repeatedly extracts the maximum element from the heap (for descending order) or the minimum element (for ascending order) and reconstructs the heap until the array is sorted.

Heap Sort Implementation in PHP8:

function heapSort(array $arr): array {

    $n = count($arr);

    // Build max heap

    for ($i = floor($n / 2) - 1; $i >= 0; $i--) {

        heapify($arr, $n, $i);

    }

    // Extract elements from heap

    for ($i = $n - 1; $i > 0; $i--) {

        // Swap the root (max) with the last element

        list($arr[$i], $arr[0]) = [$arr[0], $arr[$i]];

        heapify($arr, $i, 0); // Rebuild the heap

    }

    return $arr;

}

function heapify(array &$arr, int $n, int $i) {

    $largest = $i; // Initialize largest as root

    $left = 2 * $i + 1; // left = 2*i + 1

    $right = 2 * $i + 2; // right = 2*i + 2

    if ($left < $n && $arr[$left] > $arr[$largest]) {

        $largest = $left;

    }

    if ($right < $n && $arr[$right] > $arr[$largest]) {

        $largest = $right;

    }

    if ($largest != $i) {

        // Swap and recursively heapify the affected subtree

        list($arr[$i], $arr[$largest]) = [$arr[$largest], $arr[$i]];

        heapify($arr, $n, $largest);

    }

}

$numbers = [10, 3, 15, 7, 8, 23, 74, 18];

$sorted = heapSort($numbers);

print_r($sorted);

4. Implementing Binary Search Trees (BST)

  • A Binary Search Tree (BST) is a data structure where each node has at most two children, and for each node, the left child is smaller, and the right child is larger than the node itself.
  • BSTs allow for efficient searching, insertion, and deletion operations, each with an average time complexity of O(log n) for balanced trees.

BST Implementation in PHP8:

class Node {

    public $value;

    public $left;

    public $right;

    public function __construct($value) {

        $this->value = $value;

        $this->left = null;

        $this->right = null;

    }

}

class BinarySearchTree {

    private $root = null;

    public function insert($value) {

        $this->root = $this->insertNode($this->root, $value);

    }

    private function insertNode($node, $value) {

        if ($node === null) {

            return new Node($value);

        }

        if ($value < $node->value) {

            $node->left = $this->insertNode($node->left, $value);

        } else {

            $node->right = $this->insertNode($node->right, $value);

        }

        return $node;

    }

    public function search($value) {

        return $this->searchNode($this->root, $value);

    }

    private function searchNode($node, $value) {

        if ($node === null || $node->value === $value) {

            return $node;

        }

        if ($value < $node->value) {

            return $this->searchNode($node->left, $value);

        } else {

            return $this->searchNode($node->right, $value);

        }

    }

    public function inOrderTraversal() {

        $this->inOrder($this->root);

    }

    private function inOrder($node) {

        if ($node !== null) {

            $this->inOrder($node->left);

            echo $node->value . " ";

            $this->inOrder($node->right);

        }

    }

}

// Example Usage

$bst = new BinarySearchTree();

$bst->insert(10);

$bst->insert(5);

$bst->insert(15);

$bst->insert(3);

$bst->insert(7);

$bst->insert(18);

$bst->inOrderTraversal(); // Should output: 3 5 7 10 15 18

echo "\nSearch for 7: ";

$node = $bst->search(7);

if ($node) {

    echo "Found: " . $node->value;

} else {

    echo "Not found";

}

Conclusion

Mastering advanced sorting algorithms like Quick Sort, Merge Sort, and Heap Sort, as well as data structures like Binary Search Trees (BST), will help you solve complex problems efficiently. Understanding how each algorithm works and when to apply them can lead to significant performance improvements in your applications.

By using PHP 8, which offers robust performance and modern features, you can implement these algorithms with ease and ensure your applications are optimized for speed and reliability.

Thanks for reading the article, for more Science & Technology related articles read and subscribe to peoples blog articles.

Labels


Related Articles

Recent Articles

Recent Quick Read

Recent Great People

We Need Your Consent
By clicking “Accept Cookies”, you agree to the storing of cookies on your device to enhance your site navigation experience.
I Accept Cookies