• Data Structure and Algorithm - Insertion Sort
  • Problem to Solve
  • Pseudocode
  • PHP Implementation
  • The End

#Data Structure and Algorithm - Insertion Sort

In this tutorial, we will learn a simple sorting algorithm - Insertion Sort.

#Problem to Solve

Given a list of numbers as shown below, please sort them in ascending order.

$numbers = [21,25,100,98,89,77];

Requirements:

• You are required to use Insertion Sort algorithm when sorting the numbers.
• You are required to implement the algorithm in PHP language.

#Pseudocode

Insertion Sort works by maintaining a sorted sub-list, extracting the master list's items one by one and inserting them into a the sub-list until all items are moved from master list to the sub-list.

Pseudocode of Insertion Sort algorithm can be written as follows:

FOR each element of the master list
 
    Extract the current item
 
        Locate the position to insert by comparing with items from sub-list
 
        Insert the item to the position
 
END FOR

#PHP Implementation

We need a FOR loop and a WHILE loop. We are using the FOR loop to iterate the master list and the WHILE loop to locate the position to insert the item.

<?php
$masterList = [21, 25, 100, 98, 89, 77];
 
$subList = [];
 
for ($i = 0; $i < count($masterList); $i++) {
 
    $extractItem = $masterList[$i];
 
    $subList[] = $extractItem;
 
    // Locate the position to insert by comparing with items from sub-list
    $positionFound = $i;
 
    while ($positionFound > 0 && $extractItem < $subList[$positionFound - 1]) {
        $subList[$positionFound] = $subList[$positionFound - 1];
        $positionFound = $positionFound - 1;
    }
 
    // Insert the item to the position
    $subList[$positionFound] = $extractItem;
 
}
 
print_r($subList);
 
// Output:
/*
Array
(
    [0] => 21
    [1] => 25
    [2] => 77
    [3] => 89
    [4] => 98
    [5] => 100
)
*/

The only piece that needs a bit of explanation is the probably the WHILE loop. Pay attention to the conditions of the loop, besides the constraint of the sub-list's length, we also need to make sure that we do not run the loop when we extract the first element ($positionFound=0).

#The End

If you like our post, please follow us on Twitter and help spread the word. We need your support to continue. If you have questions or find our mistakes in above tutorial, do leave a comment below to let us know.