In this blog post, we’ll be exploring selection sort’s inner workings and discovering its strengths and limitations. Along the way, we’ll uncover the answer to a common question: Is selection sorting as efficient as other sorting algorithms? So, grab your curiosity and join us on this sorting adventure!
Table of Contents
Explore the world of data structures and algorithms with this YouTube video—your gateway to a comprehensive learning experience!
What is the Selection Sort Algorithm?
Selection sort is a straightforward and observant sorting algorithm that repeatedly finds the minimum element from the unsorted array and places it at the beginning. The algorithm segments the array into a sorted and unsorted region, iteratively growing the sorted region by selecting the smallest (or largest, depending upon the sorting order) element from the unsorted portion and swapping it with the first unsorted element. This process continues until the entire array is sorted.
Being conceptually simple, selection sort is not the most efficient algorithm for large datasets due to its time complexity of O(n^2), making it better suited for small lists or as an educational tool to illustrate the sorting principle.
How Does the Selection Sort Algorithm Work?
The steps in the selection sort algorithm are as follows:
Step 1: Selection: The algorithm divides the input list into two parts: the sorted and the unsorted sublists. Initially, the entire list is unsorted.
Step 2: Finding the Minimum: It starts by assuming the first element of the unsorted sublist as the minimum value. Then, it iterates through the unsorted sublist to find the minimum element.
Step 3: Swapping: Once the minimum element is identified within the unsorted sublist, it swaps that element with the first element of the unsorted sublist. This action effectively expands the sorted sublist by one element and reduces the unsorted sublist by one element.
Step 4: Repeat: Steps 2 and 3 are repeated for the remaining unsorted sublist, finding the minimum element and placing it in its correct position within the growing sorted sublist.
Step 5: Completion: The process continues until the entire list is sorted. At each iteration, the smallest remaining element from the unsorted sublist is added to the end of the sorted sublist until no unsorted elements remain, resulting in a fully sorted list.
The selection sort algorithm sorts the list in place, swapping elements as needed, and gradually builds up the sorted portion until the entire list is sorted in ascending or descending order, depending on the desired sorting order.
Here’s a graphical illustration of the workings of the selection sort algorithm:
Let the unsorted input array be:
Select the minimum element from the unsorted portion of the array and place it at the beginning. Swap this element with the element at the first position of the unsorted array.
In pass 1, as the smallest element is 1 so it is swapped with 4 and placed at the first position in the array.
Recursively repeat the process for the remaining unsorted elements, finding the minimum and placing it at the start of the unsorted section.
In pass 2 of sorting, 2 is the smallest element in the unsorted array so it is swapped with 4 and comes at the second position of the sorted array.
In pass 3, 3 is the smallest element after 1 and 2 so it comes at the second index and third position of the sorted array after getting swapped with 9.
In pass 4, there is no swapping needed as element 4 is at the right position in the sorted array. So we moved to the next element and swapped 6 with 9 as it is the smallest number after 4.
In the final pass, no swapping is needed as the last element is already sorted and we get our complete sorted array.
Get 100% Hike!
Master Most in Demand Skills Now!
Implementation of Selection Sort
Below is the code in the C programming language that shows the practical implementation of the selection sort algorithm.
#include <stdio.h>
void selection_sort(int arr[], int n)
{
int i, j, min;
for (i = 0; i < n-1; i++) // One by one move boundary of unsorted subarray
{
min = i; //minimum element in unsorted array
for (j = i+1; j < n; j++)
if (arr[j] < arr[min])
min = j;
// Swap the minimum element with the first element
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
void Arr_print(int a[], int n) /* function to print the array */
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main()
{
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("elements before sorting are \n");
Arr_print(a, n);
selection(a, n);
printf("\nelements after sorting are \n");
Arr_print(a, n);
return 0;
}
Output:
elements before sorting are
12 31 25 8 32 17
elements after sorting are
8 12 17 25 31 32
Complexities of Selection Sort
Complexity refers to the measure of resources (time or space) required by an algorithm or a data structure to perform operations such as insertion, deletion, search, or sorting on a dataset. It indicates how the performance of an algorithm or a data structure varies with the size of the input.
Time Complexity: Time complexity refers to the estimation of the amount of time taken by an algorithm to execute as a function of the length of the input. It quantifies the computational steps an algorithm needs to perform in the worst-case scenario.
The time complexity of the selection sort algorithm is as follows:
| Best Case | O(n^2) |
| Average Case | O(n^2) |
| Worst Case | O(n^2) |
Space Complexity: Space complexity denotes the amount of memory space an algorithm needs concerning its input size. It estimates the total memory space an algorithm requires in the worst-case scenario. The space complexity of the selection sort algorithm is as follows:
Advantages and Disadvantages of Selection Sort
Knowing the advantages and disadvantages is crucial, as every algorithm has its benefits and drawbacks. So, let’s look at some of the advantages and disadvantages of the selection sort algorithm.
- Advantages:
- Simple to implement and understand
- In-place sorting, hence minimal memory usage
- Reduces the number of swaps compared to some other algorithms
- Disadvantages:
- Quadratic time complexity (O(n^2))
- Not adaptive, performs the same regardless of the initial order
- Not stable in maintaining the order of equal elements
- Inefficient for large datasets compared to other algorithms
Wrap-Up
Selection sort is a straightforward yet efficient sorting algorithm that iterates through the list to progressively arrange elements in ascending or descending order. Despite its simplicity, it demonstrates effectiveness for smaller datasets or nearly-sorted lists. By consistently selecting the minimum (or maximum) element and placing it at the beginning (or end) of the sorted partition, selection sort demonstrates a clear step-by-step process, making it easy to comprehend and implement. However, its performance reduces for larger datasets due to its time complexity of O(n^2), prompting exploration into more optimized sorting algorithms for substantial datasets.
FAQs
Is selection sort stable?
No, the selection sort is not stable. It might change the relative order of equal elements during sorting, depending on the implementation.
When should selection sort be used?
The selection sort is suitable for small datasets or educational purposes due to its simplicity. It may be useful in situations where memory space is a concern because it sorts in place without requiring additional memory.
Can selection sort be optimized?
While its basic form has limitations, optimizations can be made to reduce the number of comparisons or swaps, but it will still retain its time complexity in the worst case.
How does selection S\sort compare to other sorting algorithms?
Selection sort is simpler to implement compared to more advanced algorithms like merge sort or quick sort. However, it’s less efficient for larger datasets compared to these algorithms, which have better time complexities.
What makes selection sort an unstable sorting algorithm?
In cases where equal elements are encountered, selection sort might not maintain its original order after sorting, thus making it an unstable sorting algorithm.
Does selection sort perform better or worse than bubble sort?
Generally, selection sort performs slightly better than bubble sort because it reduces the number of swaps, but both have similar time complexities.
Can selection sort be used for data that's nearly sorted?
Selection sort doesn’t adapt to partially sorted data. It performs the same number of comparisons regardless of the input order, so it doesn’t gain an advantage with nearly sorted data.
Is selection sorting considered an efficient sorting algorithm?
No, selection sort is not considered efficient for large datasets due to its quadratic time complexity. Other sorting algorithms, like merge sort or quick sort, offer better performance for larger datasets.