Insertion Sort Algorithm

by Devansh


Posted on 23 Oct 2018 12:10:08 (3 weeks ago)




Insertion sort is an in place comparison based sorting algorithm. Here, a sub-list is maintained which is always sorted.

function insertionSort($arr) {
    $len = count($arr);
    for ($i=1; $i<$len; $i++) {
      $key = $arr[$i];
      $j = $i - 1;
      while($j >= 0 && $arr[$j] > $key) {
          $arr[$j+1] = $arr[$j];
          $j--;
      }
      $arr[$j+1] = $key;
    }
    return $arr;
}

function insertionSortA($arr) {
    $len = count($arr);
    for ($i=1; $i<$len; $i++) {
      $value = $arr[$i];
      $hole = $i;
      while($hole > 0 && $arr[$hole-1] > $value) {
          $arr[$hole] = $arr[$hole-1];
          $hole--;
      }
      $arr[$hole] = $value;
    }
    return $arr;
}

$arr = [10, 20, 5, 11, 6, 25, 1, 9, 21];
print_r(insertionSortA($arr));