Selection Sort Algorithm is one of the easiest sorting algorithms in Data Structures. It is a comparison-based sorting algorithm. It is used to arrange the elements of an array (in ascending order). In this article, we’re going to see how we can implement selection sort in data structures using the Python programming language.
For Example
INPUT Array – 16 12 96 42 21
OUTPUT Array – 12 16 21 42 96
Table of Contents:
- How does the Selection sort algorithm work?
- Algorithm
- Pseudocode of selection sort
- Selection sort algorithm in Python
- Selection sort algorithm in C++
- Time Complexity of Selection sort
- Space Complexity of Selection Sort
- In-place behavior
- Is Selection sort an in-place sorting algorithm?
- Is the Selection sort show adaptive nature?
- Features
Working of Selection Sort Algorithm
In Selection Sort, the given array is divided into two parts – the sorted part and the unsorted part. The sorted part is at the left end of the array and the unsorted part is at the right end of the array respectively.
At the beginning of the algorithm, the sorted part is completely empty and the unsorted part consists of the whole array. But as algo proceeds, the elements that are being sorted becomes a part of the sorted array, and the remaining subarray comes under the unsorted part.
In this sorting algorithm, with every passing iteration, the least valued or the minimum element from the unsorted array is selected, using the linear search technique after that the selected element is swapped with the first element of that array. The new element added at the beginning becomes a part of the sorted array.
Let us understand this with an example.
Consider the given array of elements – 12 45 67 2 3
Algorithm
Selection_Sort ( array a, length n)
Step 1: Start loop from i = 0 to n-2
Step 2: Select smallest element among a[i] , … a[n-1]
Step 3: Swap element with a[i]
Pseudocode
function selection sort A[] : array of elements n : number of elements of an array for i=1 to n-1 /* fix first element of the array as minimum */ min=i /*check for the smallest element by comparing with all the other elements */ for j=i+1 to n if A[j] < A[min] then min=j end if end for /* swap the minimum element with the first element of the array */ if index_min!=i then swap A[min] amd A[i] end if end for end function
Selection sort python code
Code:
#Code by Copyassignment.com
# function
def selection_sort(A):
for i in range(len(A)):
# Finding the minimum element in remaining unsorted array
min_idx = i
for j in range(i+1, len(A)):
if A[min_idx] > A[j]:
min_idx = j
# Swapping A[i] with minimum element
A[i], A[min_idx] = A[min_idx], A[i]
#Driver Code
arr = [12,45,67,2,3,9]
selection_sort(arr) #Calling Function
print("Final array after sorting :\n")
for i in range(len(arr)):
print(arr[i]) #Printing array after sorting
Output:
Final array after sorting : 2 3 9 12 45 67
Selection sort algorithm in C++
Code:
// Code by copyassignment.com
#include <iostream>
using namespace std;
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void Selection_Sort(int arr[], int n)
{
int min_idx;
// moving boundary of unsorted sub array
for (int i = 0; i < n - 1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swapping A[i] element with minimum element
swap(&arr[min_idx], &arr[i]);
}
}
// Driver program to test above functions
int main()
{
int n;
cout << "Enter the size of array : " << endl; //Taking size of array
cin >> n;
int arr[n];
cout << "Enter " << n << " elements:\n";
for (int i = 0; i < n; i++)
cin >> arr[i]; //Taking elements of array
Selection_Sort(arr, n); //Calling Function
cout << "Sorted array: \n";
for (int i = 0; i < n; i++)
cout << arr[i] << " "; //Printing sorted array
return 0;
}Output:
Enter the size of array : 4 Enter 4 elements: 32 54 76 87 Sorted array: 32 54 76 87
Time complexity of selection sort
Time Complexity – In an algorithm, the time complexity is defined as the amount of time taken by the algorithm to completely run and execute all its operations is known as the time complexity of an algorithm.
Selection Sort Algorithm has a time complexity of O(n2) for all the three cases as explained below.
- Best-Case Complexity – Best case is when all the elements of the original array are already sorted. But, even in this case, the algorithm will perform all the comparison operations for each and every element of the array. Thus, its time complexity will remain the same i.e., O(n2).
- Average-Case Complexity – This is the generalized amount of time taken by the algorithm for all the possible averaged inputs. Here, again some of the swapping operations and all the comparison operations will be performed for the elements of the array. As a result, the time complexity will remain the same i.e., O(n2).
- Worst-Case Complexity – Worst case is considered when the given array is reversely sorted i.e., all the elements in descending order. This is the case where all the sorting operations and all the comparison operations will be performed for all the elements of the array. Thus, time complexity, in this case, will be again O(n2).
Space complexity
Space Complexity – For an algorithm, space complexity is defined as the memory space occupied by it to run and execute all its operations.
In this algorithm, all the elements are swapped within the space of a single array, given initially and does not require any extra memory space or array or any other data structure for its execution except one variable temp, which is used to store the element being swapped at a temporary location. Thus, it has a space complexity of O(1).
In-place sorting algorithm?
Yes, Selection sort is an in-place sorting algorithm because it does not require any other array or data structure to perform its operations. All the swapping operations are done within a single array.
Stable sorting algorithm?
No, Selection Sort is an unstable sorting algorithm because it works on the principle of initially finding the minimum element from the list and then putting it at its correct position by swapping it with the element which is present at the beginning of the unsorted array. Due to this swapping, the element present in the later part of the array will come at the beginning even if they have the same value.
Let us understand this with an example –
Input – 4A 5 3 2 4B 1
Output – 1 2 3 4B 4A 5
If it would have been a stable sorting algorithm then the output would be 1 2 3 4A 4B 5
Note: Subscripts are added only for the purpose of understanding.
Adaptive sorting algorithm?
No, it is a non-adaptive sorting algorithm because even if some of the elements of the array are sorted itself, the Selection Sort Algorithm will not take into account the ‘already sorted’ elements and it will reorder them as all the comparisons would be made to confirm their sortedness.
Features of selection sort
- It is the second slowest sorting algorithm after bubble sort because it occupies memory space for a longer time. Therefore, it is not suitable for large data sets.
- Selection Sort Algorithm can be applied on linked list data structure as well.
- It is preferably used when the cost of performing writing operations to memory is taken into consideration like in the case of flash memory.
Thanks for reading!
If you found this article useful please support us by commenting “nice article” and don’t forget to share it with your friends and enemies!
Happy Coding!
Introduction to Searching Algorithms: Linear Search Algorithm
Bubble Sort Algorithm In Data Structures & Algorithms using Python
Merge Sort Algorithm in Python
Sorting Algorithms and Searching Algorithms in Python
Shutdown Computer with Voice in Python
