Blog_Banner_Asset
    Homebreadcumb forward arrow iconBlogbreadcumb forward arrow iconArtificial Intelligencebreadcumb forward arrow iconSelection Sort Algorithm in Data Structure: Code, Function & Example

Selection Sort Algorithm in Data Structure: Code, Function & Example

Last updated:
2nd Aug, 2023
Views
Read Time
8 Mins
share image icon
In this article
Chevron in toc
View All
Selection Sort Algorithm in Data Structure: Code, Function & Example

What Is a Selection Sort Algorithm in Data Structure?

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!

Ads of upGrad blog

How Does the Selection Sort Algorithm Work?

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:

  • At first, the entire list is unsorted.
  • We pick the smallest element (10) in the unsorted part of the list and swap it with the first element (44).
  • The sorted half now has only one element (10), whereas the unsorted part has one less element.
  • Following Step 1, the following list: [10, 89, 52, 12, 29, 44, 80]

Step 2:

  • The minimum element from the remaining unsorted component (12) is found and exchanged with the unsorted part’s second element (89).
  • The sorted part now has two components (10, 12), and the unsorted half has one less element.
  • Following Step 2, the following list: [10, 12, 52, 89, 29, 44, 80]

Step 3:

  • The minimal element from the remaining unsorted component (29) is found and exchanged with the unsorted part’s third element (52).
  • The sorted part now has three elements (10, 12, 29), and the unsorted half has one less element.
  • Following Step 3, the following list: [10, 12, 29, 89, 52, 44, 80]

Step 4:

  • The minimum element from the remaining unsorted component (44) is found and exchanged with the unsorted part’s fourth element (89).
  • The sorted part now has four elements (10, 12, 29, 44), whereas the unsorted part has one less element.
  • Following Step 4, the following list: [10, 12, 29, 44, 52, 89, 80]

Step 5:

  • The minimum element from the remaining unsorted part (52) is found and exchanged with the unsorted part’s fifth element (52).
  • The sorted part now has five elements (10, 12, 29, 44, 52), whereas the unsorted part has one less element.
  • Following Step 5, the following list: [10, 12, 29, 44, 52, 89, 80]

Step 6:

  • The minimum element from the remaining unsorted part (80) is found and exchanged with the unsorted part’s sixth element (89).
  • The sorted half now has six elements (10, 12, 29, 44, 52, 89), whereas the unsorted part has one less element.
  • Following Step 6, the following list: [10, 12, 29, 44, 52, 80, 89]

Step 7:

  • The entire list has been sorted, as there are no more elements in the unsorted section.
  • [10, 12, 29, 44, 52, 80, 89] is the final sorted list.

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.

Algorithm and Pseudocode of a Selection Sort Algorithm

The following is the selection sort algorithm:

  • Begin with the smallest (or largest, depending on the sorting order) element.
  • In the unsorted segment, compare the minimum element to the following element.
  • If a smaller (or larger) element is discovered, the index of the minimum (or maximum) element is updated.
  • Continue comparing and updating the minimum (or maximum) element until the unsorted segment is finished.
  • Swap the identified minimum (or maximum) element with the unsorted part’s initial element.
  • Move the sorted part’s boundary one element to the right to expand it.
  • Steps 2-6 should be repeated until the full list is sorted.

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 Complexity of Selection Sort Algorithm

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:

  • One loop to select an array element one by one = O(N)
  • Another loop to compare that element to every other element in the array = O(N)
  • As a result, total complexity = O(N) * O(N) = O(N*N) = O(N2)

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.

Best Machine Learning and AI Courses Online

Applications of Selection Sort Algorithm

Despite its slightly dull performance in comparison to more efficient sorting algorithms, the selection sort algorithm has several useful applications as follows:

  • Bubble sort is routinely outperformed by selection sort.
  • When memory writes are expensive or constrained (for example, in embedded systems with limited resources), the swapping process of Selection Sort can be useful. It uses fewer swaps than other sorting algorithms, such as Bubble Sort.
  • Selection sort is preferable to insertion sort in terms of the number of writes ((n) swaps versus O(n2) swaps).
  • It almost always outnumbers the number of writes produced by cycle sort, despite the fact that cycle sort is theoretically best in terms of write count.
  • Selection Sort is parallelisable because each iteration of the outer loop can be done individually. This characteristic may be useful in some parallel computing scenarios.

Example of Selection Sort Algorithm 

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:

Ads of upGrad blog

Sorted list: 13 21 32 46 52 74 80

Trending Machine Learning Skills

Conclusion

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. 

Frequently Asked Questions

Profile

Rohan Vats

Blog Author
Software Engineering Manager @ upGrad. Passionate about building large scale web apps with delightful experiences. In pursuit of transforming engineers into leaders.
Get Free Consultation

Select Coursecaret down icon
Selectcaret down icon
By clicking 'Submit' you Agree to  
UpGrad's Terms & Conditions

Our Popular Machine Learning Course

Frequently Asked Questions (FAQs)

1How does selection sort work in the context of data structures?

Selection sort is a straightforward sorting algorithm that selects the smallest element in the unsorted half of the array and swaps it with the first unsorted member. This is repeated until the array has been sorted.

2How can I write a selection sort program in a programming language like Python?

In Python, you can create a selection sort programme by writing a function that accepts an array as input and sorts it in place.

3What are the key steps involved in the selection sort algorithm?

The following are the key steps in the selection sort algorithm: Determine the smallest (or greatest) element. Replace the discovered element with the first unsorted element. In the unsorted section, look for the actual minimum (or maximum) element. Repeat the procedure until the array has been sorted.

4Why do we use a selection sort algorithm?

Selection sort is used for the following purposes: Simplicity in implementation and comprehension. Sorting in place with minimal extra memory. Small datasets where reasonable performance is required. It performs best with partially sorted arrays.

Explore Free Courses

Suggested Blogs

Bagging vs Boosting in Machine Learning: Difference Between Bagging and Boosting
88107
Owing to the proliferation of Machine learning applications and an increase in computing power, data scientists have inherently implemented algorithms
Read More

by Pavan Vadapalli

12 Feb 2024

6 Types of Regression Models in Machine Learning You Should Know About
272024
Introduction Linear regression and logistic regression are two types of regression analysis techniques that are used to solve the regression problem
Read More

by Pavan Vadapalli

12 Feb 2024

Production System in Artificial Intelligence and its Characteristics
75943
The AI market has witnessed rapid growth on the international level, and it is predicted to show a CAGR of 37.3% from 2023 to 2030. The production sys
Read More

by Pavan Vadapalli

11 Feb 2024

Natural Language Processing (NLP) Projects &amp; Topics For Beginners [2023]
105000
What are Natural Language Processing Projects? NLP project ideas advanced encompass various applications and research areas that leverage computation
Read More

by Pavan Vadapalli

04 Feb 2024

Sentiment Analysis Projects &#038; Topics For Beginners [2024]
37586
Are you studying sentiment analysis and want to test your knowledge? If you are, then you’ve come to the right place. In this article, we’re discussin
Read More

by Pavan Vadapalli

04 Feb 2024

Top 8 Exciting AWS Projects &#038; Ideas For Beginners [2023]
95287
AWS Projects & Topics Looking for AWS project ideas? Then you’ve come to the right place because, in this article, we’ve shared multiple AWS proj
Read More

by Pavan Vadapalli

04 Feb 2024

AWS Salary in India in 2023 [For Freshers &#038; Experienced]
903417
Summary: In this article, you will learn about AWS Salary in India For Freshers & Experienced. AWS Salary in India INR 6,07,000 per annum AW
Read More

by Pavan Vadapalli

28 Jan 2024

Image Segmentation Techniques [Step By Step Implementation]
61301
What do you see first when you look at your selfie? Your face, right? You can spot your face because your brain is capable of identifying your face an
Read More

by Pavan Vadapalli

28 Jan 2024

Data Preprocessing in Machine Learning: 7 Easy Steps To Follow
146531
Summary: In this article, you will learn about data preprocessing in Machine Learning: 7 easy steps to follow. Acquire the dataset Import all the cr
Read More

by Kechit Goyal

28 Jan 2024

Schedule 1:1 free counsellingTalk to Career Expert
icon
footer sticky close icon