How to implement selection sort algorithm with PHP

How to use PHP to implement selection sorting algorithm

Selection sorting is a simple and intuitive sorting algorithm. Its basic idea is to select the smallest (or largest) from the data elements to be sorted in each pass. An element is stored at the beginning of the result sequence until all data elements to be sorted are exhausted. Below we will implement the selection sort algorithm through PHP code and explain it in detail.

First, let’s take a look at the implementation steps of the selection sort algorithm:

1. Traverse the entire array to be sorted, taking the first element as the minimum value (default).
2. According to the minimum value, traverse the remaining elements, find elements smaller than the current minimum value, and update the minimum value.
3. Exchange the minimum value with the current traversed position.
4. Repeat steps 2-3 until the array sorting is completed.

The following is a code example of using PHP to implement the selection sort algorithm:

function selectionSort($arr) {
    $len = count($arr);
    
    for($i = 0; $i < $len - 1; $i++) {
        $minIndex = $i;
        
        for($j = $i + 1; $j < $len; $j++) {
            if($arr[$j] < $arr[$minIndex]) {
                $minIndex = $j;
            }
        }
        
        // Swap the minimum value with the current position
        $temp = $arr[$minIndex];
        $arr[$minIndex] = $arr[$i];
        $arr[$i] = $temp;
    }
    
    return $arr;
}

// Test the selectionSort function
$testArray = [64, 25, 12, 22, 11];
echo "Before sorting: ";
print_r($testArray);
echo "After sorting: ";
print_r(selectionSort($testArray));

Run the above code, the output result will be:

Before sorting: Array ( [0] => 64 [1] => 25 [2] => 12 [3] => 22 [4] => 11 )
After sorting: Array ( [0] => 11 [1] => 12 [2] => 22 [3] => 25 [4] => 64 )

This is sorting by selection The result of an algorithm sorting an array. Next, let’s explain the specific implementation process of the code.

In the code, we define a function named selectionSort, which accepts an array to be sorted as a parameter and returns the sorted array.

First, we use the count function to get the length of the array and assign it to the variable $len. We then use two nested for loops to iterate through the entire array.

In the outer for loop, we define a variable $minIndex to save the index of the current minimum value, which defaults to the current loop variable $i. In the inner for loop, we update the index of the minimum value by comparing the size of the current element and the minimum value.

When the inner for loop ends, we exchange the current minimum value with the current position. Swap the values ​​of two elements by using a temporary variable $temp.

Finally, we return the sorted array.

The time complexity of the selection sort algorithm is O(n^2), where n is the length of the array to be sorted. This is because each traversal needs to find the minimum value among the remaining elements and perform a swap operation. Regardless of the initial state of the array, n-1 traversals must be performed.

I hope that through the code examples and explanations in this article, you can better understand the implementation process of the selection sort algorithm and be able to use it flexibly in actual development.

The above is the detailed content of How to implement selection sort algorithm with PHP. For more information, please follow other related articles on the PHP Chinese website!