Selection Sort | Sorting Algorithm | Data Structure | PHP | Visualization

#php #sortingalgorithm #selectionsort #visualization

Selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list. The algorithm repeatedly selects the smallest (or largest) element from the unsorted portion of the list and swaps it with the first element of the unsorted portion. This process is repeated for the remaining unsorted portion of the list until the entire list is sorted. One variation of selection sort is called “Bidirectional selection sort” that goes through the list of elements by alternating between the smallest and largest element, this way the algorithm can be faster in some cases.

The algorithm maintains two subarrays in a given array.

The subarray which already sorted.
The remaining subarray was unsorted.
In every iteration of the selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the beginning of unsorted subarray.

After every iteration sorted subarray size increase by one and unsorted subarray size decrease by one.

Follow the below steps to solve the problem:

1. Initialize minimum value(min_idx) to location 0.
2. Traverse the array to find the minimum element in the array.
3. While traversing if any element smaller than min_idx is found then swap both the values.
4. Then, increment min_idx to point to the next element.
5. Repeat until the array is sorted.

Complexity Analysis of Selection Sort:
Time Complexity: The time complexity of Selection Sort is O(N2) as there are two nested loops:

One loop to select an element of Array one by one = O(N)
Another loop to compare that element with every other Array element = O(N)
Therefore overall complexity = O(N) * O(N) = O(N*N) = O(N2)

Auxiliary Space: O(1) as the only extra memory used is for temporary variables while swapping two values in Array. The selection sort never makes more than O(N) swaps and can be useful when memory write is a costly operation.

Tools Used:
Visualization : https://www.hackerearth.com/practice/algorithms/sorting/selection-sort/visualize/
IDE: https://onlinephp.io/
Content: https://www.geeksforgeeks.org/selection-sort/?ref=lbp