PHP Searching and Sorting Algorithm: Insertion sort

Last update on December 20 2024 10:21:51 (UTC/GMT +8 hours)

Write a PHP program to sort a list of elements using Insertion sort.

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Visual Presentation : Insertion Sort

A graphical example of insertion sort :

Animation Credits : Swfung8

Sample Solution:

PHP Code :

<?php
// Function to perform insertion sort on an array
function insertion_Sort($my_array)
{
    // Iterate over each element in the array
    for ($i = 0; $i < count($my_array); $i++) {
        $val = $my_array[$i]; // Store the current element
        $j = $i - 1; // Initialize index for the previous element
        
        // Shift elements of my_array[0..i-1] that are greater than val
        // to one position ahead of their current position
        while ($j >= 0 && $my_array[$j] > $val) {
            $my_array[$j + 1] = $my_array[$j];
            $j--;
        }
        $my_array[$j + 1] = $val; // Place val at its correct position
    }
    return $my_array; // Return the sorted array
}

$test_array = array(3, 0, 2, 5, -1, 4, 1);

echo "Original Array :\n";
echo implode(', ', $test_array); // Display original array
echo "\nSorted Array :\n";
print_r(insertion_Sort($test_array)); // Display sorted array
?>

Output:

Original Array :                                                    
3, 0, 2, 5, -1, 4, 1                                                
Sorted Array :                                                      
Array                                                               
(                                                                   
    [0] => -1                                                       
    [1] => 0                                                        
    [2] => 1                                                        
    [3] => 2                                                        
    [4] => 3                                                        
    [5] => 4                                                        
    [6] => 5                                                        
) 

Explanation:

In the exercise above,

• The code defines a function named "insertion_Sort()" which takes an array '$my_array' as input and returns the sorted array.
• Insertion Sort Algorithm:
• The function iterates over each element in the array using a for loop.
• For each element, it compares it with the elements before it and shifts the elements to the right until it finds the correct position to insert the current element.
• Once the correct position is found, it inserts the element into that position.
• Output:
• After sorting the array using the "insertion_Sort()" function, the code prints the original array and the sorted array using the 'echo' and "print_r()" functions respectively.
• Usage:
• The function is then called with an example array '$test_array' containing unsorted numbers.
• It prints the original array and the sorted array to the console.

Flowchart :

PHP Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Write a PHP program to sort a list of elements using Heap sort.
Next: Write a PHP program to sort a list of elements using Selection sort.