As the name suggest, It referring to something about the selection, so now the question arises what type of selection? So here selection means to minimum value element selection.
Selection Sort algorithm is an in-place(does not require extra place) comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.
The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary by one element to the right.
Selection Sort algorithm is not suitable for large data sets as it’s average and worst-case complexities are of Ο(n2), where n is the number of items.
Algorithm for selection sort
- Step -- 1: Set Min at zero location
- Step -- 2: Find out the minimum value element inside the input list.
- Step -- 3: You swapping method to swap the location with minimum value element
- Step -- 4: Move MIN forward to point to the next element of the input list.
- Step -- 5: Repeat until the input list gets sorted.
Let visualize the above algorithm with Gif.
Selection Sort in Python Code
# Selection Sort Published on Freshlybuilt.com def selection_sort(input_list): # Traverse through all array elements for idx in range(len(input_list)): min_idx = idx # Find the minimum element in remaining unsorted array for j in range(idx + 1, len(input_list)): if input_list[min_idx] > input_list[j]: min_idx = j # Swap the minimum value with the compared value input_list[idx], input_list[min_idx] = input_list[min_idx], input_list[idx] return input_list def main(): lst = [8, 17, 3, 9] print("Initial Unsorted List:", lst) print("After Sorting:", selection_sort(lst)) if __name__ == "__main__": main()
Initial Unsorted List: [8, 17, 3, 9] After Sorting: [3, 8, 9, 17]
Flow Chart for selection sort in Python
Finally time has come for the short video on Youtube for above code 🙂
Some facts about Selection Sort
|Best Case time complexity||O(n^2)|
|Average Case Time Complexity||O(n^2)|
|Worst Case Time Complexity||O(n^2)|
|Stability||The default implementation is not stable. However it can be made stable|
|Inplace||Yes, the Selection sort does not require extra space.|
Now our blog comes to end, If you liked it please like and share to your friend.