3 min read

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 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()

Output:

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 complexityO(n^2)
Average Case Time ComplexityO(n^2)
Worst Case Time ComplexityO(n^2)
Auxiliary Space:O(1)
StabilityThe default implementation is not stable. However it can be made stable
InplaceYes, 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.

1+

Vishal Sharma

Currently pursuing Computer Science degree from G.B Pant Government Engineering college, New Delhi.

0 Comments

Leave a Reply