Selection sort with PHP

Udemy Generic 728x90

Overview

The algorithm finds the minimum value, swaps it with the value in the first position, and repeats these steps for the remainder of the list. It does no more than n swaps, and thus is useful where swapping is very expensive.

Before we learn about the implementation of Selection sort in php, first we know the basics of algorithm and data structure on which the selection sort is based on.

Data StructureArray

This algorithm use array as a data structure so that we can access the data randomly as per need.

 

Algorithm – Sorting Algorithm

It is an algorithm which put all the elements of an input array in a sequential order

 

Description

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

 

Logical Approach

  1. Find the smallest element in array and swap it with element from first position.
  2. Repeat first step with second smallest element and swap with element from second position.
  3. Continue until array is sorted.

Performance:

  • Worst case: O(n2)
  • Average case: O(n2)
  • Best case: O(n2)

Example

Here is an example of this sort algorithm sorting five elements:

64 25 12 22 11 // this is the initial, starting state of the array
11 25 12 22 64 // sorted sublist = {11}
11 12 25 22 64 // sorted sublist = {11, 12}
11 12 22 25 64 // sorted sublist = {11, 12, 22}
11 12 22 25 64 // sorted sublist = {11, 12, 22, 25}
11 12 22 25 64 // sorted sublist = {11, 12, 22, 25, 64}

PHP implementation

&lt;/span&gt;</p>
<p>function selectionSort(array $arr){</p>
<p>    $n =sizeof($arr);</p>
<p>    for($i =0; $i &lt; $n; $i++) {</p>
<p>        $lowestValueIndex = $i;</p>
<p>        $lowestValue = $arr[$i];</p>
<p>        for($j = $i +1; $j &lt; $n; $j++) {</p>
<p>            if($arr[$j]&lt; $lowestValue) {</p>
<p>                $lowestValueIndex = $j;</p>
<p>                $lowestValue = $arr[$j];</p>
<p>            }</p>
<p>        }</p>
<p>        $arr[$lowestValueIndex]= $arr[$i];</p>
<p>        $arr[$i]= $lowestValue;</p>
<p>    }</p>
<p>    return $arr;</p>
<p>}</p>
<p>// Example:</p>
<p>$arr = array(64,25,12,22,11);</p>
<p>$result = selectionSort($arr);</p>
<p>print_r($result);</p>
<p>

Output

Array

(

    [0]=>11

    [1]=>12

    [2]=>22

    [3]=>25

    [4]=>64

)
Udemy Generic 728x90

Spread the word. Share this post!