Selection Sort Algorithm
The selection sort in C++ algorithm can be broken down into a series of repeatable steps designed to arrange a list in a certain order, either from smallest to largest or vice versa. Let’s see each step of the selection sort algorithm:
-
Initialize the Sorted Region: Start with an empty sorted region. At the beginning, this sorted region is just a hypothetical area at the start of the list.
-
Find the Minimum Element: From the current position in the list, scan the remaining elements to find the smallest one. This involves comparing each element with the current minimum and updating the minimum when a smaller element is found.
-
Swap Elements: After finding the minimum element in the unsorted region, swap it with the first element of the unsorted region. If the smallest element is already in the first position, no swap is needed.
-
Expand the Sorted Region: Move the boundary of the sorted region one step to the right. The element that was just swapped now becomes part of the sorted region.
- Repeat Until Sorted: Repeat the process of finding the minimum, swapping, and expanding the sorted region until all elements are included in the sorted region. This is generally when the unsorted region has only one element left, which means the entire array is sorted.
Note: The selection sort algorithm is famous for its simplicity, but it’s not the fastest for sorting large lists. It’s particularly useful for understanding the basics of sorting mechanisms and for sorting small arrays or lists where speed is not an issue.
Implementation of Selection Sort in C++
Let’s see a basic implementation of selection sort in C++ :
C++
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// Find the minimum element in the unsorted part
int min_index = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
// Swap the found minimum element with the first element of the unsorted part
swap(arr[min_index], arr[i]);
}
}
int main() {
int array[] = {64, 25, 12, 22, 11};
int n = sizeof(array) / sizeof(array[0]);
selectionSort(array, n);
cout << "Sorted array: \n";
for (int i = 0; i < n; i++)
cout << array[i] << " ";
return 0;
}
You can also try this code with Online C++ Compiler
Output
11 12 22 25 64
Explanation of the Code
-
Include Libraries & Namespace: We start by including the necessary library for input and output operations and use the standard namespace to avoid prefixing our functions with std::.
-
Function Definition: The selectionSort function sorts an array. It takes two parameters: the array arr[] and its size n.
-
Sorting Logic: Inside the function, we use two loops. The outer loop runs from the start of the array to the second-to-last element, establishing the boundary of the sorted region. The inner loop finds the minimum element in the unsorted region, starting from the current position of the outer loop.
-
Finding the Minimum: We maintain a variable min_index to store the index of the minimum element. As we find smaller elements, we update min_index.
-
Swap: Once the minimum element is found, we swap it with the first element of the unsorted region, effectively growing the sorted region.
- Main Function: In the main function, we define an array, sort it using the selection sort, and then print the sorted array.
Complexity Analysis of Selection Sort
Time Complexity
-
Best Case Scenario: Even in the best case, where the array is already sorted, selection sort makes the same number of comparisons. This is because it still goes through the process of finding the minimum element for each position in the array. Therefore, the best case time complexity is O(n^2), where n is the number of items in the array.
-
Worst Case Scenario: The worst case happens when the array is sorted in reverse order. In this case, selection sort also performs in O(n^2) time because it needs to scan and swap every element to its correct position.
- Average Case: For average cases, regardless of the initial order of the elements, the selection sort consistently performs in O(n^2) time.
Space Complexity
Selection sort is an in-place sorting algorithm, meaning it does not require any additional storage and thus has a space complexity of O(1). This aspect makes the selection sort a memory-efficient option when working with limited space, as it only uses the original array for sorting without needing extra space for temporary storage.
Note: Even though selection sort is simple, the quadratic time complexity of selection sort makes it less efficient for larger arrays compared to more advanced sorting algorithms like quicksort or mergesort. However, for small or nearly sorted datasets, selection sort is very useful due to their unique and low memory usage.
Characteristics of Selection Sort
Here are the key characteristics of the selection sort:
-
Simplicity: Selection sort is simple to understand and implement, making it an excellent choice for beginner programmers to learn about sorting algorithms. The algorithm’s steps are straightforward and involve repetitive finding and swapping of the minimum or maximum element.
-
Not Adaptive: The performance of selection sort does not improve even if the input array is partially sorted. It performs the same number of comparisons and swaps regardless of the initial order of the elements.
-
In-Place Sorting: As an in-place sorting algorithm, selection sort does not require extra space for data storage apart from minimal temporary storage used for swapping elements. This makes it space-efficient and useful in scenarios where memory usage is a constraint.
-
Performance Consistency: Unlike some algorithms that have significantly different best and worst-case times, selection sort has a consistent performance. Its time complexity is always O(n^2) for both best and worst-case scenarios, which makes its behavior predictable.
-
Stability: Selection sort is not a stable sorting algorithm. Stability in sorting algorithms means that two objects with equal keys appear in the same order in the sorted output as they appear in the input array to be sorted. During selection sort, swapping elements might change the initial order of equal elements.
- Minimal Data Movement: It makes the minimum possible number of swaps during sorting, which is n-1 swaps in the best case. This characteristic is particularly useful when the cost of swapping items is high.
Advantages of Selection Sort
-
Selection sort is simple and easy to understand, making it great for beginners learning sorting algorithms.
-
It does not require extra memory, as it sorts the array in place, making it efficient in terms of space.
-
Selection sort performs well on small datasets where efficiency is not a major concern.
- It works well in cases where data movement needs to be minimal, as it makes a limited number of swaps.
Disadvantages of Selection Sort
-
Selection sort is slow for large datasets because it has a time complexity of O(n²).
-
It always goes through the entire array, even if it is already sorted, making it inefficient.
-
The algorithm does not perform well compared to advanced sorting techniques like quicksort and mergesort.
- Selection sort is not stable, meaning it may change the order of equal elements in the original array.
Applications of Selection Sort
-
Selection sort is useful when sorting small lists or datasets where performance is not a concern.
-
It is used in cases where swapping operations should be minimized, as it performs fewer swaps.
-
The algorithm helps in scenarios where memory usage needs to be minimal since it sorts in place.
-
Selection sort is often used in teaching sorting concepts due to its simplicity and easy implementation.
- It can be applied in situations where data is nearly sorted, as it still performs consistently.
Frequently Asked Questions
Why is selection sort not suitable for large datasets?
Selection sort has a time complexity of O(n^2), which means its execution time increases significantly with the size of the dataset. This makes it inefficient for sorting large arrays compared to faster algorithms like quicksort or mergesort.
Can selection sort be used on linked lists?
Yes, selection sort can be applied to linked lists. The implementation would need to be adjusted to handle node pointers instead of array indices, but the fundamental steps of finding the minimum element and swapping remain the same.
Is selection sort better than bubble sort?
While both have similar time complexities (O(n^2)), selection sort generally performs fewer swaps compared to bubble sort, which can make it slightly more efficient in scenarios where writing data is more costly than reading data.
What is the time complexity of Selection Sort?
Selection Sort has a time complexity of O(n^2) in the best, average, and worst cases.
Does Selection Sort require extra memory?
No, Selection Sort is an in-place sorting algorithm and requires only O(1) additional space.
Conclusion
In this article, we have learned the fundamentals of selection sort, including how it works, how to implement it in C++, and its complexity analysis. We also explained the characteristics that show why this algorithm is very famous for sorting small data sets or lists. However, it's not the fastest for large datasets, but it still offers simplicity and predictable performance that can again be useful for small to medium-sized datasets where ease of implementation is a priority.
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.
7+ registered 
