Sorting is one of the most important tasks to be executed by computers. These examples show the implementation in PHP of the most commonly used algorithms for sorting data.
Bubble Sort:
Bubble sort is a simple sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order. The algorithm continues iterating through the array until no more swaps are required. Bubble sort has a time complexity of O(n^2), where n is the number of elements in the array. It is not recommended for large arrays due to its inefficiency.
//...
function bubbleSort(array &$arr) {
$n = count($arr);
// Traverse through all array elements
for ($i = 0; $i < $n - 1; $i++) {
// Last $i elements are already in place
for ($j = 0; $j < $n - $i - 1; $j++) {
// Swap if the current element is greater than the next element
if ($arr[$j] > $arr[$j + 1]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
}
}
}
}
//...
// Example usage
$numbers = [64, 34, 25, 12, 22, 11, 90];
bubbleSort($numbers);
echo "Sorted array: ";
foreach ($numbers as $value) {
echo $value . " ";
}
//...In this example, the bubbleSort() function takes an array by reference &$arr as a parameter. It performs the Bubble Sort algorithm on the given array.
The outer loop for ($i = 0; $i < $n - 1; $i++) iterates through the array, and in each iteration, the inner loop for ($j = 0; $j < $n - $i - 1; $j++) compares adjacent elements and swaps them if they are in the wrong order.
During each iteration of the inner loop, the largest unsorted element "bubbles" up to its correct position in the array. This process continues until the entire array is sorted.
Finally, after calling bubbleSort($numbers), the sorted array is printed using a foreach loop.
When you run this code, you'll see the output:
Sorted array: 11 12 22 25 34 64 90
The Bubble Sort algorithm repeatedly compares adjacent elements and swaps them if necessary, which gradually "bubbles" the largest elements to the end of the array. It is not the most efficient sorting algorithm for large arrays, but it provides a straightforward implementation for educational purposes or for small datasets.
Selection Sort:
Selection sort works by repeatedly finding the minimum element from the unsorted portion of the array and placing it at the beginning. The algorithm divides the array into two parts: the sorted and the unsorted. Selection sort has a time complexity of O(n^2) and is also inefficient for large arrays.
function selectionSort(array &$arr) {
$n = count($arr);
// Traverse through all array elements
for ($i = 0; $i < $n - 1; $i++) {
// Find the minimum element in the unsorted part of the array
$minIndex = $i;
for ($j = $i + 1; $j < $n; $j++) {
if ($arr[$j] < $arr[$minIndex]) {
$minIndex = $j;
}
}
// Swap the minimum element with the first element of the unsorted part
$temp = $arr[$minIndex];
$arr[$minIndex] = $arr[$i];
$arr[$i] = $temp;
}
}
// Example usage
$numbers = [64, 34, 25, 12, 22, 11, 90];
selectionSort($numbers);
echo "Sorted array: ";
foreach ($numbers as $value) {
echo $value . " ";
}In this example, the selectionSort() function takes an array by reference &$arr as a parameter. It performs the Selection Sort algorithm on the given array.
The outer loop for ($i = 0; $i < $n - 1; $i++) iterates through the array, and in each iteration, it finds the minimum element in the unsorted part of the array using the inner loop.
The inner loop for ($j = $i + 1; $j < $n; $j++) starts from the element next to the current position $i and compares it with the remaining elements to find the smallest element. The index of the smallest element is stored in $minIndex.
After finding the smallest element, the function swaps it with the first element of the unsorted part of the array. This ensures that the smallest element is moved to its correct position in each iteration.
Finally, after calling selectionSort($numbers), the sorted array is printed using a foreach loop.
When you run this code, you'll see the output:
Sorted array: 11 12 22 25 34 64 90The Selection Sort algorithm divides the array into a sorted and an unsorted part. In each iteration, it finds the smallest element from the unsorted part and places it at the beginning of the sorted part. This process continues until the entire array is sorted. Selection Sort has a time complexity of O(n^2), making it less efficient for large arrays compared to other sorting algorithms like Merge Sort or Quick Sort.
Insertion Sort:
Insertion sort builds the final sorted array one element at a time. It iterates through the array, comparing each element with the elements before it and inserting it into the correct position. Insertion sort has a time complexity of O(n^2), but it performs well for small arrays and is efficient for partially sorted arrays.
function insertionSort(array &$arr) {
$n = count($arr);
// Traverse through all array elements
for ($i = 1; $i < $n; $i++) {
$key = $arr[$i];
$j = $i - 1;
// Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
while ($j >= 0 && $arr[$j] > $key) {
$arr[$j + 1] = $arr[$j];
$j = $j - 1;
}
$arr[$j + 1] = $key;
}
}
// Example usage
$numbers = [64, 34, 25, 12, 22, 11, 90];
insertionSort($numbers);
echo "Sorted array: ";
foreach ($numbers as $value) {
echo $value . " ";
}
In this example, the insertionSort() function takes an array by reference &$arr as a parameter. It performs the Insertion Sort algorithm on the given array.
The outer loop for ($i = 1; $i < $n; $i++) starts from the second element $i = 1 and traverses through the array. In each iteration, it selects an element as key and compares it with the elements before it.
The inner loop while ($j >= 0 && $arr[$j] > $key) checks if the current element $arr[$j] is greater than the key and moves the elements greater than the key one position ahead.
By moving the greater elements ahead, the algorithm creates the correct position for the key element within the sorted part of the array.
Finally, after calling insertionSort($numbers), the sorted array is printed using a foreach loop.
When you run this code, you'll see the output:
Merge Sort:
Merge sort is a divide-and-conquer algorithm that divides the array into smaller subarrays, sorts them, and then merges them to produce the final sorted array. It has a time complexity of O(n log n) and is considered an efficient sorting algorithm. Merge sort is stable and can handle large arrays effectively.
function mergeSort(array &$arr) {
$n = count($arr);
if ($n <= 1) {
return;
}
// Divide the array into two halves
$mid = (int) ($n / 2);
$left = array_slice($arr, 0, $mid);
$right = array_slice($arr, $mid);
// Recursively sort the two halves
mergeSort($left);
mergeSort($right);
// Merge the sorted halves
merge($left, $right, $arr);
}
function merge(array &$left, array &$right, array &$arr) {
$i = $j = $k = 0;
$nLeft = count($left);
$nRight = count($right);
// Compare elements from both halves and merge them in ascending order
while ($i < $nLeft && $j < $nRight) {
if ($left[$i] <= $right[$j]) {
$arr[$k] = $left[$i];
$i++;
} else {
$arr[$k] = $right[$j];
$j++;
}
$k++;
}
// Copy the remaining elements from the left half, if any
while ($i < $nLeft) {
$arr[$k] = $left[$i];
$i++;
$k++;
}
// Copy the remaining elements from the right half, if any
while ($j < $nRight) {
$arr[$k] = $right[$j];
$j++;
$k++;
}
}
// Example usage
$numbers = [64, 34, 25, 12, 22, 11, 90];
mergeSort($numbers);
echo "Sorted array: ";
foreach ($numbers as $value) {
echo $value . " ";
}
In this example, the mergeSort() function takes an array by reference &$arr as a parameter. It performs the Merge Sort algorithm on the given array.
The mergeSort() function first checks if the length of the array is less than or equal to 1. If so, it returns immediately as there is no need for sorting.
Otherwise, the array is divided into two halves: left and right. The midpoint of the array is calculated using $mid = (int) ($n / 2), where $n is the length of the array. The array_slice() function is used to split the array into the left and right halves.
The mergeSort() function is then recursively called on the left and right halves to sort them.
After sorting the halves, the merge() function is called to merge the sorted halves back into the original array. It compares the elements from both halves and merges them in ascending order.
Finally, after calling mergeSort($numbers), the sorted array is printed using a foreach loop.
When you run this code, you'll see the output:
Sorted array: 11 12 22 25 34 64 90
The Merge Sort algorithm follows the divide-and-conquer approach. It repeatedly divides the array into smaller subarrays, sorts them, and then merges them to produce the final sorted array. Merge Sort has a time complexity of O(n log n) and is considered an efficient sorting algorithm.
Quick Sort:
Quick sort is also a divide-and-conquer algorithm that works by selecting a pivot element and partitioning the array into two subarrays, one with elements less than the pivot and another with elements greater than the pivot. The process is repeated recursively for each subarray. Quick sort has an average time complexity of O(n log n), but it can degrade to O(n^2) in the worst case. It is widely used due to its efficiency and versatility.
function quickSort(array &$arr, $low, $high) {
if ($low < $high) {
// Partition the array and get the pivot index
$pivotIndex = partition($arr, $low, $high);
// Recursively sort the left and right subarrays
quickSort($arr, $low, $pivotIndex - 1);
quickSort($arr, $pivotIndex + 1, $high);
}
}
function partition(array &$arr, $low, $high) {
// Choose the rightmost element as the pivot
$pivot = $arr[$high];
$i = $low - 1;
for ($j = $low; $j < $high; $j++) {
// If current element is smaller than or equal to the pivot, swap it with the element at the i-th position
if ($arr[$j] <= $pivot) {
$i++;
swap($arr, $i, $j);
}
}
// Swap the pivot with the element at the (i+1)-th position
swap($arr, $i + 1, $high);
// Return the pivot index
return $i + 1;
}
function swap(array &$arr, $i, $j) {
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}
// Example usage
$numbers = [64, 34, 25, 12, 22, 11, 90];
$size = count($numbers);
quickSort($numbers, 0, $size - 1);
echo "Sorted array: ";
foreach ($numbers as $value) {
echo $value . " ";
}
In this example, the quickSort() function takes an array by reference &$arr, and the indices $low and $high as parameters. It performs the Quick Sort algorithm on the given array within the range defined by $low and $high.
The quickSort() function first checks if $low is less than $high, indicating that there are at least two elements to be sorted. If so, it proceeds with the partitioning step and recursive sorting.
The partition() function is responsible for partitioning the array. It chooses the rightmost element $pivot = $arr[$high] as the pivot and divides the array into two parts: elements smaller than the pivot and elements greater than the pivot. It uses the variables $i and $j to keep track of the positions during the partitioning process.
The swap() function is a utility function that swaps two elements in the array.
After partitioning, the pivot element is placed in its correct sorted position by swapping it with the element at the (i+1)-th position (swap($arr, $i + 1, $high)). The function then returns the pivot index ($i + 1).
The quickSort() function is recursively called on the left subarray ($low to $pivotIndex - 1) and the right subarray ($pivotIndex + 1 to $high) to sort them.
Finally, after calling quickSort($numbers, 0, $size - 1), the sorted array is printed using a foreach loop.
When you run this code, you'll see the output:
Sorted array: 11 12 22 25 34 64 90
TheQuick Sort algorithm follows the divide-and-conquer approach. It selects a pivot element and partitions the array into two subarrays, one with elements smaller than the pivot and another with elements greater than the pivot. The process is repeated recursively for each subarray. Quick Sort has an average time complexity of O(n log n), making it an efficient sorting algorithm for most cases.
Heap Sort:
Heap sort utilizes the concept of a binary heap, a complete binary tree where each parent node is greater (or smaller) than its children. The algorithm builds a max-heap (for ascending order) or a min-heap (for descending order) from the array and repeatedly extracts the root element until the array is sorted. Heap sort has a time complexity of O(n log n) and is an in-place sorting algorithm.
function heapSort(array &$arr) {
$n = count($arr);
// Build the initial max heap
buildMaxHeap($arr, $n);
// Heapify the array starting from the last element
for ($i = $n - 1; $i > 0; $i--) {
// Swap the root (maximum element) with the last element
swap($arr, 0, $i);
// Perform heapify on the reduced heap
heapify($arr, $i, 0);
}
}
function buildMaxHeap(array &$arr, $n) {
// Build a max heap by performing heapify on each non-leaf node in reverse order
for ($i = (int) ($n / 2) - 1; $i >= 0; $i--) {
heapify($arr, $n, $i);
}
}
function heapify(array &$arr, $n, $root) {
$largest = $root;
$left = 2 * $root + 1;
$right = 2 * $root + 2;
// Check if the left child is larger than the root
if ($left < $n && $arr[$left] > $arr[$largest]) {
$largest = $left;
}
// Check if the right child is larger than the current largest
if ($right < $n && $arr[$right] > $arr[$largest]) {
$largest = $right;
}
// If the largest element is not the root, swap them and perform heapify on the affected subtree
if ($largest != $root) {
swap($arr, $root, $largest);
heapify($arr, $n, $largest);
}
}
function swap(array &$arr, $i, $j) {
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}
// Example usage
$numbers = [64, 34, 25, 12, 22, 11, 90];
heapSort($numbers);
echo "Sorted array: ";
foreach ($numbers as $value) {
echo $value . " ";
}
In this example, the heapSort() function takes an array by reference &$arr as a parameter. It performs the Heap Sort algorithm on the given array.
The buildMaxHeap() function is responsible for building the initial max heap. It iterates through each non-leaf node in reverse order and calls the heapify() function on each node to ensure that the heap property is satisfied.
The heapify() function takes an array, the size of the heap ($n), and the index of the root as parameters. It compares the root with its left and right children to find the largest element among them. If the largest element is not the root, it is swapped with the root, and heapify() is recursively called on the affected subtree to maintain the heap property.
After building the max heap, the heapSort() function starts heapifying the array from the last element ($i = $n - 1) and swaps the root (maximum element) with the last element. It then reduces the size of the heap by one and performs heapify on the reduced heap. This process is repeated until the entire array is sorted.
Finally, after calling heapSort($numbers), the sorted array is printed using a foreach loop.
When you run this code, you'll see the output:
Sorted array: 11 12 22 25 34 64 90
The Heap Sort algorithm utilizes the concept of a binary heap, a complete binary tree where each parent node is greater (or smaller) than its children. It first builds a max heap by heapifying the array, ensuring that the maximum element is at the root. Then, it repeatedly swaps the root (maximum element) with the last element, reduces the heap size, and heapifies the reduced heap to find the next maximum element. Heap Sort has a time complexity of O(n log n) and is an in-place sorting algorithm.
These are some of the most common sorting algorithms used in PHP. The choice of algorithm depends on the specific requirements of the task, the size of the array, and the expected performance characteristics.
PHP provides an extensive set of built-in functions such as sort(), asort(), usort(), etc., which internally use different sorting algorithms based on the context and the type of sorting needed.