Table of contents
1.
Introduction
2.
Working of Selection Sort
3.
Implementation of Selection Sort Algorithm: 
4.
Time Complexity of Selection Sort
4.1.
Complexity Details
5.
Frequently Asked Questions
5.1.
Can selection sort be used for large datasets?
5.2.
Is selection sort stable?
5.3.
What is the main advantage of using selection sort?
6.
Conclusion
Last Updated: Jun 3, 2024
Easy

Selection Sort in Python

Author Ravi Khorwal
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Sorting is a fundamental task in programming that organizes elements in a specific order. The simplest way to do this is with the help of selection sort. This method works well with small lists, where it performs efficiently by repeatedly selecting the smallest or largest element from an unsorted section and moving it to the end of the sorted section. 

Selection Sort Python

This article will help you understand how selection sort works, with it’s implementation in Python. We will also discuss it’s time complexity to see it’s efficiency.

Working of Selection Sort

Selection sort is a straightforward sorting algorithm that organizes elements by repeatedly finding the minimum (or maximum) element from the unsorted part of the list & swapping it with the first element of the unsorted part. Here's how it works:

  1. Start with the first element of the array as the minimum.
     
  2. Compare this minimum with the second element. If the second element is smaller, it becomes the new minimum.
     
  3. Continue this process for all the elements in the array. By the end of the first pass, the smallest element is placed at the beginning of the array.
     
  4. Move to the second element and treat it as the minimum for the next pass, and repeat the process for the remaining part of the array.
     
  5. Continue this until the entire array is sorted.
     

Note : This method is very easy as you can see yourself that it’s scanning through the list, picking the smallest element, & putting it at the front, much like sorting playing cards in your hands.

Implementation of Selection Sort Algorithm: 

Let’s see how to implement the selection sort in Python : 

def selection_sort(arr):
    # Traverse through all array elements
    for i in range(len(arr)):
        # Find the minimum element in remaining unsorted array
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # Swap the found minimum element with the first element
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr


Here’s a breakdown of what each part of the code does:

  1. Function Definition: We define a function selection_sort that takes an array arr as input.
     
  2. Outer Loop: This loop goes through each element of the array from the start to the end. Each iteration of this loop represents a pass through the array where we place the correct element in its final position.
     
  3. Inner Loop: Inside the outer loop, we start from the current position of the outer loop and go through the rest of the array to find the minimum element.
     
  4. Finding the Minimum: We keep track of the index of the minimum element found so far. If we find an element smaller than the current minimum, we update our min_idx.
     
  5. Swapping: After finding the minimum element in the current unsorted part of the array, we swap it with the element at the current position of the outer loop. This step places the element in its correct position within the sorted part of the array.
     
  6. Return: Once all elements have been placed in their correct positions, we return the sorted array.

Time Complexity of Selection Sort

The time complexity of selection sort is simple to understand because each step of the algorithm involves a series of comparisons that grow with the size of the sorted array.

Best, Average, & Worst Case Scenarios: The time complexity of selection sort remains the same, regardless of the order of the elements in the array. This is because, even if the array is already sorted, the algorithm still goes through the entire process of finding the minimum for each position in the array.

Complexity Details

  • Outer Loop: This loop runs n times where n is the number of elements in the array.
     
  • Inner Loop: For each iteration of the outer loop, the inner loop runs approximately n-i times (where i is the current index of the outer loop). This means the first time it runs n-1 times, the second time n-2, and so on, down to 1.
     
  • Total Comparisons: When you add up all the iterations of the inner loop, it sums up to 

n−1+n−2+…+1, which equals n(n−1)/2 comparisons. This formula simplifies to O(n2 ), representing the quadratic time complexity.
 

Note : Despite its simplicity, the O(n2 ) time complexity makes selection sort inefficient for large lists compared to more advanced algorithms like quicksort or mergesort, which have O(nlogn) average time complexities. However, for small or nearly sorted lists, selection sort might still perform adequately due to its simplicity and the low overhead of its operations.

Frequently Asked Questions

Can selection sort be used for large datasets?

Selection sort is not recommended for large datasets due to its O(n2 ) time complexity, which makes it inefficient compared to faster algorithms like quicksort or mergesort.

Is selection sort stable?

By nature, selection sort is not stable because it may swap distant elements, thereby changing the relative order of equal elements. However, it can be modified to be stable with some additional effort.

What is the main advantage of using selection sort?

The main advantage of selection sort is its simplicity and the fact that it makes minimal number of swaps, which can be beneficial when write operations are significantly more costly than reads.

Conclusion

In this article, we have learned the fundamentals of the selection sort algorithm, with it’s steps with the implementation in Python. To see why it cant be useful on large datasets, we saw it’s time complexity. We've seen that while selection sort is straightforward and easy to work with, its efficiency decreases with larger datasets.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry.

Live masterclass