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:
-
Function Definition: We define a function selection_sort that takes an array arr as input.
-
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.
-
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.
-
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.
-
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.
- 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 DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry.