Selection Sort Algorithm in Data Structure: Code, Function & Example
Updated on Aug 18, 2023 | 8 min read | 8.4k views
Share:
For working professionals
For fresh graduates
More
Updated on Aug 18, 2023 | 8 min read | 8.4k views
Share:
Table of Contents
The selection sort algorithm is a simple sorting technique for organising a list of components in ascending or descending order. It is a comparison-based sorting algorithm that compares list components to determine their relative rank.
The selection sort algorithm works by dividing the input list into two parts: the sorted component and the unsorted component. The sorted section is initially empty, and the unsorted part contains the complete list. The method identifies the smallest (or largest, depending on the sorting order) element from the unsorted section and pushes it to the end of the sorted part every time. This step is repeated until the full list has been sorted.
Selection Sort is inefficient for large lists, with an average and worst case time complexity of O(n2). This implies that the time required to sort the list grows quadratically as the number of elements increases. It does, however, have the virtue of being simple to grasp and simple to implement.
Before strengthening advanced algorithms with upGrad’s Executive PG Program in Machine Learning & AI from IIITB, let us take you through the basics of the selection sort algorithm!
The Selection Sort technique identifies the least (or greatest) element in the list’s unsorted section and places it at the end of the sorted section. This process is repeated until the full list has been sorted. The following is a detailed explanation of how the selection sort algorithm works:
Consider using Selection Sort to sort a collection of numbers in ascending order:
Input: [44, 89, 52, 12, 29, 10, 80]
Step 1:
Step 2:
Step 3:
Step 4:
Step 5:
Step 6:
Step 7:
Here’s a detailed description of selection sort in python:
def selection_sort(array):
m = len(array)
for i in range(m - 1):
# Assume the current index (i) has the minimum value
min_index = i
# Find the minimum element in the remaining unsorted part
for j in range(i + 1, m):
if array[j] < array[min_index]:
min_index = j
# Swap the found minimum element with the first element of the unsorted part
array[i], array[min_index] = array[min_index], array[i]
selection sort example usage:
my_list = [68, 34, 28, 19, 22, 10, 50]
selection_sort(my_list)
print(my_list)
Output: [10, 19, 22, 28, 34, 50, 68]
Enroll for the Machine Learning Course from the World’s top Universities. Earn Masters, Executive PGP, or Advanced Certificate Programs to fast-track your career.
The following is the selection sort algorithm:
The pseudocode of a Selection Sort Algorithm is as follows:
function selection_sort(array):
m = length(array)
for i = 0 to m-2:
# Assume the current index (i) has the minimum value
min_index = i
# Find the minimum element in the remaining unsorted part
for j = i + 1 to m-1:
if array[j] < array[min_index]:
min_index = j
# Swap the found minimum element with the first element of the unsorted part
swap(array[i], array[min_index])
selection sort example usage:
my_list = [69, 49, 25, 19, 20, 11, 28]
selection_sort(my_list)
print(my_list)
Output: [11, 19, 20, 25, 28, 49, 69]
Check out upGrad’s free courses on AI.
The selection sort algorithm’s complexity can be measured in terms of time and space complexity:
Time Complexity: Selection Sort has an O(N2) time complexity due to the two nested loops:
Space Complexity: Since the selection sort algorithm sorts in place, no additional memory is required for temporary data structures. As a result, Selection Sort’s space complexity is O(1), showing that the space needed by the method is constant and does not depend on the input list’s size.
Despite its slightly dull performance in comparison to more efficient sorting algorithms, the selection sort algorithm has several useful applications as follows:
The following is the selection sort program:
#include <stdio.h>
void selection_sort(int array[], int k) {
for (int l = 0; l < k - 1; l++) {
int min_index = l;
for (int m = l + 1; m < k; m++) {
if (array[m] < array[min_index]) {
min_index = m;
}
}
int temp = array[l];
array[l] = array[min_index];
array[min_index] = temp;
}
}
int main() {
int my_list[] = {46, 74, 52, 32, 21, 13, 80};
int k = sizeof(my_list) / sizeof(my_list[0]);
selection_sort(my_list, k);
printf("Sorted list: ");
for (int l = 0; l < k; l++) {
printf("%d ", my_list[l]);
}
printf("\n");
return 0;
}
In the given selection sort code, we first implement the selection_sort function, which accepts as input an integer array of size k. The selection sort algorithm is used to sort the array in ascending order.
The main function creates a test array called my_list, sorts it using the selection_sort function, and then prints the sorted list.
When you execute the programme, it will produce the following output:
Sorted list: 13 21 32 46 52 74 80
The selection sort algorithm is a simple and intuitive sorting strategy that may be used in educational settings and scenarios with limited resources. Although its O(n2) time complexity makes it unsuitable for huge datasets, its basic code implementation makes it useful for teaching sorting ideas. While not appropriate for high-performance applications, Selection Sort is useful when partial sorting or parallelisation is required.
Strengthening yourself with the right courses and a collection of well-equipped equipment is set to benefit your profession in the long term. upGrad’s Executive Post Graduate Programme in Software Development – Specialisation in Full Stack Development is one such course to prepare for the growing tech world. If you want to be a full-stack developer, this programme will help you develop your front-end and back-end programming skills.
Get Free Consultation
By submitting, I accept the T&C and
Privacy Policy
Top Resources