Algorithms in javascript

Selection Sort

Learn Simpli September 12, 2019 2 Comments

Selection Sort

How selection sort works

How it works

It divides the array into two parts,
First sub-array: The part of the array that’s been sorted, its remains on the left side.,
Second sub-array: The remaining is an unsorted array and has to be sorted, it remains on the right side

Process

The entire array is an unsorted array,
When it starts the iteration,
It finds the minimum value by scanning the unsorted array sequentially,
If the minimum value found, it moves to the left side sorted array

Performance

Best case perfoarmace: Time complexity O(n2) for sorted array,
Average case performance: Time complexity O(n2) for unsorted array,
Worst case performace: Time complexity O(n2) for unsorted array,
N the first iteration, finding the first minimum value needs scanning the N number of elements sequentially,
In the second iteration, finding the second minimum value needs scanning the n-1 number of elements sequentially. And so on,
(n − 1) + (n − 2) + …+ 2 + 1 = n(n − 1)/2

Advantages

It is considered an in-place sorting algorithm,
It gives the best performance when the list is small,
Temporary memory is only required to hold the original memory

Disadvantages

Not fit for a very large list of the array,
It’s suitable for only the unsorted array.

Source code:

function selectionSorJavaScript(array)
{
    for(var i = 0; i < array.length; i++)
    {
        //
        var min = i;
        for(var j = i+1; j < array.length; j++)
        {
            if(array[j] &lt; array[min]){
            min = j;
        }
    }

    var temp = array[i];
    array[i] = array[min];
    array[min] = temp;
  }

    return array;
}

var array = [10,9,5,1,7,8,3,4,6];
console.log(selectionSorJavaScript(array));
// output
// [1, 3, 4, 5, 6, 7, 8, 9, 10]

function selectionSortPHP($array=null)
{
    if($array===null)
    {
        return "No input...";
    }
    $lenthOfArray=count($array);
    $minValue=null;    
    $temp=null;
 
    for($i=0; $i < $lenthOfArray-1; $i++)//outer loop
    {
 
        $minValue=$i;
        for($j=$i+1; $j&lt;$lenthOfArray; $j++)//inner loop
        {
            if( $array[$j] < $array[$minValue] ) //change the &lt; to &gt; for descending order
            {
                $minValue=$j; 
            }
        }
 
        //swap the current index of the outer loop with the next min value
        $temp=$array[$i];
        $array[$i]=$array[$minValue];
        $array[$minValue]=$temp;
    }
 
    return $array;
}
 
$array=array(10,9,5,1,7,8,3,4,6);
$response=selectionSortPHP($array);
echo json_encode($response);
// output
// [1, 3, 4, 5, 6, 7, 8, 9, 10]

def selectionSortPython(inputArray):
   for fillslot in range(len(inputArray)-1,0,-1):
       maxpos=0
       for location in range(1,fillslot+1):
           if inputArray[location]&gt;inputArray[maxpos]:
               maxpos = location

       temp = inputArray[fillslot]
       inputArray[fillslot] = inputArray[maxpos]
       inputArray[maxpos] = temp

inputArray = [14,46,43,27,57,41,45,21,70]
selectionSortPython(inputArray)
print(inputArray)
//Output
// [14, 21, 27, 41, 43, 45, 46, 57, 70]

Selection Sort

Selection Sort

2 thoughts on “Selection Sort”