What is Selection Sort?

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:

Table-1

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

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.

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.

Table-4

After this swap, we have our output array as:  

Table-5

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

Algorithm of Selection Sort

The selection sort algorithm sorts an array by repeatedly selecting the smallest (or largest) element from the unsorted portion of the array and placing it at the correct position in the sorted portion.

1. Start with the first element: Consider the first element as the minimum (or maximum, for descending order).
2. Find the smallest/largest element in the remaining array:
   • Compare the current minimum/maximum with the other elements in the unsorted part of the array.
   • Update the minimum/maximum when a smaller/larger element is found.
3. Swap the smallest/largest element with the first element of the unsorted part:
   • Exchange the positions of the smallest/largest element with the element at the beginning of the unsorted portion.
4. Move to the next element in the array:
   • Repeat steps 1-3 for the next element, treating it as the beginning of the unsorted portion.
5. Continue until the entire array is sorted:
   • Repeat the process for all elements except the last one, as it will already be sorted.

Pseudocode of Selection Sort Algorithm

SELECTION_SORT(arr, n):
1. for i = 0 to n-2:
2.     min_index = i
3.     for j = i+1 to n-1:
4.         if arr[j] < arr[min_index]:
5.             min_index = j
6.     if min_index ≠ i:
7.         swap arr[i] with arr[min_index]
8. end for

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;
}

You can also try this code with Online C Compiler

Run Code

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 + " ");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

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] << " ";
    }
}

You can also try this code with Online C++ Compiler

Run Code

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#

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.

Selection Sort Time Complexity

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)

Selection Sort 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.

Advantages of the Selection Sort Algorithm

1. Simple and Easy to Implement: The algorithm is straightforward and easy to understand, making it a good choice for teaching sorting concepts.
2. In-Place Sorting: Selection Sort requires no additional memory for sorting, as it works in-place by swapping elements within the original array.
3. Good for Small Datasets: For small input sizes, Selection Sort is simple and can perform reasonably well.
4. Stable Space Complexity: With a space complexity of O(1), it is memory efficient compared to algorithms requiring extra storage.
5. Predictable Number of Comparisons: The algorithm always performs the same number of comparisons, regardless of the initial order of the elements. This consistency can be useful in certain scenarios.

Disadvantages of the Selection Sort Algorithm

1. Poor Time Complexity: The algorithm has a time complexity of O(n²), making it inefficient for large datasets.
2. Not Stable (By Default): Selection Sort is not inherently stable, meaning equal elements may not retain their original order unless modifications are made.
3. Inefficient for Nearly Sorted Data: Unlike some other algorithms (e.g., Insertion Sort), Selection Sort does not take advantage of an already partially sorted array.
4. High Number of Comparisons: Even if the array is sorted, the algorithm performs O(n²) comparisons, as it does not break early or adapt to sorted input.
5. Swapping Overhead: Frequent swapping operations, even for large datasets, can be computationally expensive and cause unnecessary wear on memory if elements are being moved in physical storage.

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.

What is the time complexity of selection sort?

The time complexity of Selection Sort is O(n²) for all cases (best, average, worst), as it always performs n(n−1)/2 comparisons.

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 Code360 to practice a wide range of questions to help you master your skills.

Keep Learning, Keep Growing!