Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Algorithm for Selection Sort in C
3.
Working Of Selection Sort
4.
Implementation of Selection Sort
5.
Implementation Selection Sort in C
5.1.
C
6.
Implementation Selection Sort in Java
6.1.
Java
7.
Implementation Selection Sort in Python
7.1.
Python
8.
Implementation Selection Sort in C++
8.1.
C++
9.
Implementation Selection Sort in C#
9.1.
C#
10.
Selection Sort Complexity
10.1.
Time Complexity
10.2.
Space Complexity
11.
Selection Sort Applications
12.
Frequently Asked Questions
12.1.
Why is selection sort used?
12.2.
How to implement selection sort in C?
12.3.
What are the types of sorting in C?
12.4.
How many passes are there in selection sort?
13.
Conclusion
Last Updated: May 22, 2024
Medium

Selection Sort in C, C++, Java, Python & C#

Author Rinki Deka
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction 

Most programming languages have a built-in sort function, but we need to understand the sorting algorithms to understand the code effectively. The algorithm which we are going to explore in this blog is Selection Sort in C/C++/Python/Java

A selection sort algorithm sorts the elements by iterating over the entire array. It selects the smallest element from the unsorted array and swaps it with the element present at the first index.

It again finds the next smallest element from the unsorted array and swaps it with the element at the second index. This keeps going on until we achieve our resultant sorted array

Let’s understand the concept in different programming languages.  

Selection Sort in C, C++, Java, Python & C#

Selection Sort is an easy way for computers to sort a list of numbers. Suppose you have a deck of cards and want to arrange them from smallest to largest. With Selection Sort, the computer analyzes the cards individually, finding the smallest and putting them first. Then, it finds the next smallest card from the remaining ones and puts it in the second position. It keeps doing this until all the cards are in the correct order. It is like finding the smallest card each time and putting it in its proper place.

So to know how computers figure the smallest and the most significant number, let’s look at the pseudo-code.

function selectionSort(array, size)
    // Iterating over the entire array from 0 to size - 2(0 - Based Indexing) 
    for i = 0 to size - 2
        smallest = array[i]
        for j = i+1 to size - 1
            if array[j] < smallest
                smallest = array[j]
                smallest_index = j

        swap(array[i],array[smallest_index])

    return array

 

The pseudocode mentioned above conveys the working of how a code will run in the selection sort:

  • It sets the smallest number to be the first element in the unsorted section of the array. Initially, the whole array is unsorted i.e the first element of the array.
  • It looks through the entire unsorted section of the array and then finds the smallest number.
  • It will swap the value with the item at the beginning index i.e first element of the unsorted section, which increases the size of the sorted section by 1 and at the same time decreases the size of the unsorted section by 1.

Algorithm for Selection Sort in C

  • First, start with an unsorted array of elements.
  • Find the smallest element in the unsorted portion of the array.
  • Change the smallest element with the first element of the unsorted portion. It effectively moves it to the sorted part of the array.
  • Expand the sorted portion of the array by one element and reduce the unsorted portion by one element.
  • Repeat steps 2-4 until the entire array is sorted.
  • The array is now sorted in ascending order.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Working Of Selection Sort

Basic algorithms are a set of instructions, which you pass in computers to make a task happen. 

A selection sort algorithm will divide its input into sorted and unsorted subarrays. Initially, our array is unsorted and as we apply selection to sort the algorithm picks an element from the unsorted section and moves it to the sorted section.

Another vital thing to remember is that it keeps the smallest element sorted at the beginning of the output array.

Here we have an unsorted array of elements:

2

11

28

19

1

Table-1

We will search for the smallest number in the entire array and swap it with the element present at the first index.

2

11

28

19

1

Table-2

We will swap 2 with 1, and then our array becomes as follows. Now we will search for the next smallest element and swap it with 11.

1

11

28

19

2

Table-3

After swapping, we get the sequence of our array as {1,2,28,19,11}. Now we will search for the next smallest element and swap it with 28.

1

2

28

19

11

Table-4

After this swap, we have our output array as:  

1

2

11

19

28

Table-5

We have all the elements in sorted order, so no further swap is required, so this is our newly sorted array.

Implementation of Selection Sort

Sorting algorithms take the array elements as input data, perform specific operations on those arrays and deliver sorted arrays as output. So let us have a look at how the selection sort algorithm might look in different programming languages.

Implementation Selection Sort in C

  • C

C

#include <stdio.h>
int main()
{
int arr[100], num, x, y, pos, z;
printf("Enter number of elements to be sorted: \n");
scanf("%d", &num);
printf("Enter %d Numbers: \n", num);
for (x = 0; x < num; x++)
scanf("%d", &arr[x]);
for(x = 0; x < num - 1; x++)
{
pos=x;
for(y = x + 1; y < num; y++)
{
if(arr[pos] > arr[y])
pos=y;
}
if(pos != x)
{
z=arr[x];
arr[x]=arr[pos];
arr[pos]=z;
}
}
printf("Sorted Array:\n");
for(x = 0; x < num; x++)
printf(" %d ", arr[x]);
return 0;
}

 

Output

Enter number of elements to be sorted: 
5
Enter 5 Numbers: 
1
3
5
6
7
Sorted Array:
1  3  5  6  7 

Implementation Selection Sort in Java

  • Java

Java

public class selectionSort {
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int index = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[index]) {
index = j;
}
}
int smallNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallNumber;
}
}

public static void main(String a[]) {
int[] arr = {11,2,1,3,4,19,28};

selectionSort(arr);
for (int i: arr) {
System.out.print(i + " ");
}
}
}

 

Output

[1,2,3,4,11,19,28]

 

  • We will use two nested loops in this function, which keep on iterating the entire array until the smallest value is found.
     
  • In the first loop which represents the sorted section of the array, we have initialized variable i = 0, which keeps on incrementing its value till the final iteration.
     
  • Then a nested loop is defined with another variable j, which is equal to i+1 so that it contains the value next to the smallest value and finds the smallest value from the unsorted section of the array to place in the sorted section. Both the loops keep on iterating until the final sorted array is found.

Implementation Selection Sort in Python

  • Python

Python

def selectionSort(array, size):
for step in range(size):
minimum_idx = step

for i in range(step + 1, size):
if array[i] < array[minimum_idx]:
minimum_idx = i

(array[step], array[minimum_idx]) = (array[minimum_idx], array[step])

list = [11, 2, 28, 19, 7, 65]
size = len(list)
selectionSort(list, size)
print(list)

 

Output

[2, 7, 11, 19, 28, 65]

Implementation Selection Sort in C++

  • C++

C++

#include <iostream>
using namespace std;

void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}

void selectionSort(int array[], int size){
for (int step = 0; step < size - 1; step++){
int minimum_idx = step;
for (int i = step + 1; i < size; i++){
if (array[i] < array[minimum_idx])
minimum_idx = i;
}
swap(&array[minimum_idx], &array[step]);
}
}

// Driver code
int main(){
int data[] = {11, 1, 21, 28, 19, 6, 7};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
for (int i = 0; i < size; i++){
cout << data[i] << " ";
}
}

 

Output

[1,6,7,11,19,21,28]

 

There is a disadvantage in this sorting method, that even if we have a sorted array or a nearly sorted array, it will continue to run checking through all the elements in the array.

This is why the time complexity of selection sort in the worst case, best case, and the average case is the same – O(n²). This means that as the number of elements increases, running time increases at a quadratic rate. Even if we have sorted the array in the best case, we will have to go through the entire array to be sure. Therefore, the time complexity in each case is the same. 

Implementation Selection Sort in C#

  • C#

C#

using System;
class Sort {
// Function for selection sort
static void selectionSort(int[] Array) {
int number = Array.Length;
int z;
for(int i=0; i<number; i++) {
int min = i;
for(int j=i+1; j<number; j++) {
if(Array[j] < Array[min])
{min = j;}
}
z = Array[min];
Array[min] = Array[i];
Array[i] = z;
}
}
// Function to print array
static void Printarr(int[] Array) {
int number = Array.Length;
for (int i=0; i<number; i++)
Console.Write(Array[i] + " ");
Console.Write("\n");
}
// Test the code
static void Main(string[] args) {
int[] MyArray = {78,89,25,16,14,75,23,34,17};
Console.Write("Original Array\n");
Printarr(MyArray);
selectionSort(MyArray);
Console.Write("\nSorted Array\n");
Printarr(MyArray);
}
}

 

Output

Original Array
78 89 25 16 14 75 23 34 17 
Sorted Array
14 16 17 23 25 34 75 78 89 

Selection Sort Complexity

Alright, let us look at the complexities of selection sort.

Time Complexity

Best CaseAverage CaseWorst Case
O(n2)O(n2)O(n2)

The algorithm iterates the unsorted subarray (N - 1) times, and the size of the unsorted subarray reduces by one after each iteration. Thus, the total number of comparisons is N * (N - 1)/2 = (N - 1) + (N - 2) + (N - 3) +........... + 1. As a result, the time complexity is quadratic.

It provides the same amount of comparisons for any given N-dimensional array, so the worst, best, and average cases are all equivalent.

Worst Case = Best Case = Average Case = O(n^2)

Space Complexity

O(1)

The selection sort algorithm doesn't use any extra space. Therefore, the space complexity is constant in the selection sort.

Selection Sort Applications

Now we will look at some applications of selection sort.

  • Small Data Sets: Selection sort can be used to sort small data sets where efficiency is not an issue. For example, if you have a small list of names or numbers that need to be sorted, selection sort can quickly return a sorted result.
     
  • Memory Writing: When memory writing is expensive, selection sort comes in useful. Its in-place sorting minimizes write operations, making it appropriate for costly memory writes.
     
  • Online Sorting: Selection sort is useful when data is constantly added to a list or array, and sorting is required after each insertion. It can quickly sort the new element into the already sorted segment of the list.
     
  • Simple Implementations: Compared to more complex sorting algorithms such as quicksort or mergesort, selection sort is comparatively simple to construct. It requires little code and can be easily implemented in programming languages that support basic array manipulation.
     
  • Checking all elements: Selection sort is applicable when all elements need to be checked, as it scans the entire list to find the minimum element, making it useful in such scenarios.

Frequently Asked Questions

Why is selection sort used?

Selection sort uses very little memory storage as it does not require any additional storage beyond the original array to store the sorted array. Also, it works efficiently when smaller arrays or data sets are taken into consideration.

How to implement selection sort in C?

To implement Selection Sort in C, go through the array, find the smallest element, switch it with the current position, and repeat for each element. Repeat N-1 times for an array of size N.

What are the types of sorting in C?

In C, common types of sorting algorithms include Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, and Heap Sort. These algorithms arrange elements in ascending or descending order based on predefined criteria.

How many passes are there in selection sort?

An unsorted array must have the smallest element moved to the front in order for the selection sort to work. There are N-1 passes in the selection sort, where N is the number of elements.

Conclusion

This blog thoroughly discussed how Selection Sort works in programming languages like C, C#, Python, Java, and C++.

Unlike Bubble sort, Selection Sort might not be used to that extent. But you need to understand this to help you build your foundations. Selection sort starts by solving the smallest element first by swapping it with the element present at the first index of the unsorted array. It keeps on making these iterations until we achieve a sorted array.

You can also use Coding Ninjas Studio to practice a wide range of questions to help you master your skills.

Keep Learning, Keep Growing!

Previous article
Binary Insertion Sort
Next article
Java Program for QuickSort
Live masterclass