In the world of computer science, Selection Sort algorithm plays a important part where we are talking about comparison based approach and then swap that with other smallest element in the entire group.
Like if i will compare selection sort algorithm with other algorithms like Merge Sort, radix Sort and many more it is easy to implement and efficient. In this blog we will be covering about the selection sort algorithms, complexity analysis, advantages, disadvantages and applications.
What is a Selection Sort Algorithm?
Selection sort is a simple sorting algorithm that works by repeatedly finding the smallest element from the unsorted part of the list and swapping it with the first unsorted element.
It starts at the beginning of the list and scans through the entire list to find the smallest value and then swaps it with the element in the first position. Then it moves to the next position and repeats the process for the remaining unsorted elements. This continues until all the elements are sorted in order.
Although it is easy to understand and implement selection sort which is not very efficient for large lists because it requires repeatedly scanning through the remaining elements which is making it slower compared to more advanced sorting methods.
How Selection Sort Algorithm Works?
Selection Sort works by dividing the list into two parts which is the sorted part and the unsorted part. The sorted part is empty, and the unsorted part is the entire list.
The algorithm repeatedly finds the smallest element from the unsorted part and swaps it with the first unsorted element which is adding it to the sorted part. This process continues until the entire list is sorted.
Let us say we have a list:
[29, 10, 14, 37, 13]
- Find the smallest element → 10
Swap it with the first element → [10, 29, 14, 37, 13] - Find the smallest in remaining list → 13
Swap with second element → [10, 13, 14, 37, 29] - Find smallest in remaining → 14
Already in place → [10, 13, 14, 37, 29] - Find smallest in remaining → 29
Swap with 37 → [10, 13, 14, 29, 37]
Now the given list of array is sorted.
Implementation of Selection Sort Algorithm
The implementation of selection sort algorithm is explained below in that we have taken array [15, 8, 2, 20, 11, 4] and the easy implementation of code in python programming language.
arr = [15, 8, 2, 20, 11, 4]
n = len(arr)
# Selection Sort
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# Swap
arr[i], arr[min_idx] = arr[min_idx], arr[i]
print("Sorted array:", arr)
Complexity Analysis of Selection Sort Algorithm
This table shows the complexity analysis of selection sort algorithms in every possible way whether it is best case, average case and worst case. These complexities are really helpful when it comes to solve a real problems or requires logic.
| Type | Complexity |
| Best Case | O(n²) |
| Average Case | O(n²) |
| Worst Case | O(n²) |
| Space Complexity | O(1) |
Advantages of Selection Sort
- This algorithm is easy to apply when it compared with other algorithms and it is great for the learning purposes.
- It requires the constant amount of extra memory i.e, O(1) and not additional storage.
- For small datasets its simplicity is more than enough to apply.
- It swaps elements when it is necessary because swapping operation is costly to perform.
- It only performs comparisons in its initial order.
Disadvantages of Selection Sort
- It is not suitable for large datasets because it takes too much time as the number of elements increases.
- It always goes through the entire list to find the smallest element even if the list is already sorted.
- Its time complexity is always O(n2)O(n^2)O(n2) so it is slower than other efficient algorithms like Merge Sort or Quick Sort.
- It is not a stable sorting algorithm which means it may change the relative order of equal elements.
- It does not take advantage of the already sorted part of the list, unlike algorithms like Insertion Sort.
Applications of Selection Sort
- It is used in teaching and learning to help beginners understand how sorting works step by step.
- It is helpful when memory space is very limited since it does not use extra memory.
- It can be used in cases where the number of swaps needs to be minimized, like in hardware-related operations.
- It is sometimes used in embedded systems where simplicity matters more than speed.
- It is suitable for sorting small datasets where performance is not a major concern.
FAQs of Selection Sort Algorithm
What is a Selection Sort?
Selection sort algorithm works on the comparison and swapping based algorithm where we are swapping the current element with the small one through comparison in the whole array.
How does Selection Sort work?
Selection Sort works in the following way:
- Start with the first element.
- Find the smallest element in the unsorted part.
- Swap it with the first element.
- Repeat the process for the remaining unsorted elements.
What is the time complexity of Selection Sort?
- Best Case: O(n²)
- Average Case: O(n²)
- Worst Case: O(n²)
It always performs n(n-1)/2 comparisons regardless of the initial order.
What is the space complexity of Selection Sort?
Selection Sort is an in-place algorithm, so it requires O(1) auxiliary space.
Is Selection Sort stable?
No, Selection Sort is not stable by default. Equal elements may not retain their original order after sorting.
Is Selection Sort adaptive?
No, Selection Sort is not adaptive, meaning it does not take advantage of existing order in the array.
When is Selection Sort used?
Selection Sort is mostly used:
- In teaching sorting algorithm concepts.
- When memory writes are costly since it performs minimal swaps.
- For small datasets where performance is not critical.
What are the advantages of Selection Sort?
- Simple to understand and implement.
- Performs well on small datasets.
- Minimizes the number of swaps (at most n-1 swaps).
What are the disadvantages of Selection Sort?
- Inefficient for large datasets due to O(n²) time complexity.
- Not stable or adaptive.
- Does not work well with partially sorted data.
How many swaps and comparisons does Selection Sort make?
Swaps covers O(n) includes at most n-1 swaps and Comparisons covers O(n²) that always makes n(n-1)/2 comparisons.