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);
Google Ad 1
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);
Google Ad 2
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);
Google Ad 3
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.
