Selection Sort Algorithm

Selection sort is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of an array and placing it at the beginning of the sorted part of the array. The algorithm maintains two subarrays in the given array:

• The sorted subarray is initially empty.
• The unsorted subarray is initially the entire input array.

The selection sort algorithm starts by finding the smallest element in the unsorted subarray and swapping it with the first element of the unsorted subarray. Then, it moves the boundary between the sorted and unsorted subarrays one element to the right and repeats the process until the entire array is sorted.

The time complexity of the selection sort algorithm is O(n^2) in both best and worst cases, where n is the number of elements in the array. It is not suitable for large data sets as its performance degrades quickly due to its nested loop structure. However, it has the advantage of requiring only a small amount of additional memory space to perform the sorting operation, making it useful in situations where memory is limited.

How Selection Sort works

The algorithm of Selection Sort can be described as follows:

1. Set the first element of the array as the minimum value.
2. For each element i in the array from i=0 to n-1, where n is the size of the array: a. Set the current element i as the minimum index. b. For each element j in the array from j=i+1 to n-1: i. If the value at the jth index is less than the value at the minimum index, then set the minimum index to j. c. Swap the value at the ith index with the value at the minimum index.
   
3. Continue this process until the entire array is sorted.

In essence, the selection sort algorithm iterates through the array, selecting the smallest element and swapping it with the element at the ith position. This continues until the array is sorted in ascending order.

In selection sort, first, we search for a minimum number, then put it on the first index. 
Then in the second iteration, we search for the second minimum and put it on the second index. 
Thus we do the same for every index.
Let an array is 4, 2, 3, 5, 1 and it is a zero-based indexed
For the first iteration, 4, 2, 3, 5, 1
Find the minimum number from the 0th index to the 4th index inclusive. 
For the minimum number on the 4th index, swap the 4th number with the 0th number.
After the first iteration array looks like   1, 2, 3, 5, 4
For the second iteration, 1, 2, 3, 5, 4 
Find the minimum number from 1st to 4th position. Then swap it with 1st element. 
After 2nd iteration array looks like 1, 2, 3, 5, 4
For the 3rd iteration 1, 2, 3, 5, 4
The minimum number is in 2nd index, 
After 3rd iteration, 1, 2, 3, 5, 4
For 4th (final in this case) iteration 1, 2, 3, 5, 4
The minimum number is in the 4th index, swap the 3rd number with the 4th number. After 4th iteration, the array is sorted and looks like 1, 2, 3, 4, 5

Here, the Time complexity of finding the minimum element is O(n). And we will do it n times.
So, the time complexity is O(n2).

Selection Sort using C

#include <stdio.h>
int main() {
    int arr[5]={4, 2, 3, 5, 1};
    for(int i=0;i<5-1;i++)
    {
        int mnidx=i;
        for(int j=i+1;j<5;j++)
        {
            if(arr[mnidx]>arr[j]) mnidx=j;
        }
        int tmp=arr[i];
        arr[i]=arr[mnidx];
        arr[mnidx]=tmp;
    }
    for(int i=0;i<5;i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

This is a C program that uses a selection sort algorithm to sort an array of five integers. The program starts by declaring an integer array named arr with five elements and initializing it with integer values. Then, it uses a nested for-loop structure to implement the selection sort algorithm.

The outer loop runs from i = 0 to i = 5-1, which means it runs for four iterations. This loop is responsible for selecting the smallest element in the remaining unsorted part of the array and placing it in the correct position in the sorted part of the array.

The inner loop runs from j = i+1 to j = 5, which means it runs for (5-i-1) iterations in each iteration of the outer loop. This loop is responsible for finding the index of the smallest element in the remaining unsorted part of the array.

Inside the inner loop, there is an if statement that checks if the value at the current minimum index (mnidx) is greater than the value at the current index (j). If this condition is true, then the current index j becomes the new minimum index mnidx.

Once the minimum index is found, the program swaps the element at the minimum index with the element at the current position i in the outer loop.

Finally, the program prints the sorted array using a for loop that iterates over all the elements of the array and uses the printf function to print each element on the console.

Selection Sort using C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[5]={4, 2, 3, 5, 1};
    for(int i=0;i<5-1;i++)
    {
        int minIndex=i;
        for(int j=i+1;j<5;j++)
        {
            if(arr[minIndex]>arr[j]) minIndex=j;
        }
        swap(arr[minIndex], arr[i]);
    }
    for(int i=0;i<5;i++)
    {
        cout<<arr[i]<<" ";
    }
    return 0;
}

This is a C++ program that sorts an array of integers using the selection sort algorithm. The array is initialized with 5 integers in random order. The outer loop iterates over the array indices from 0 to n-2, where n is the length of the array. For each index i, the inner loop finds the index j of the smallest element in the subarray from i+1 to n-1. This is done by initializing the minIndex variable to i, and then comparing the element at minIndex with each element in the subarray.

If an element is found that is smaller than the current minimum, minIndex is updated to the index of that element. After the inner loop finishes, the element at minIndex is swapped with the element at index i using the swap function from the STL. Finally, the sorted array is printed to the console using a for loop.

Selection Sort using Python

arr=[4, 2, 3, 5, 1]
for i in range(len(arr)):
    minIndex=i;
    for j in range(i+1, len(arr)):
        if(arr[minIndex]>arr[j]):
            minIndex=j
    arr[minIndex], arr[i]=arr[i], arr[minIndex]
print(arr)

This is a Python program that implements the selection sort algorithm to sort an array of integers. The array is initialized with 5 integers in random order. The outer loop iterates over the indices of the array using the range function. For each index i, the inner loop finds the index j of the smallest element in the subarray from i+1 to the end of the array.

This is done by initializing minIndex to i, and then comparing the element at minIndex with each element in the subarray. If an element is found that is smaller than the current minimum, minIndex is updated to the index of that element. After the inner loop finishes, the element at minIndex is swapped with the element at index i using tuple unpacking. Finally, the sorted array is printed to the console using the print statement.

Selection Sort using Java

import java.util.*;
class Sort{
    public static void main(String[] args) {
        int[] arr={4, 2, 3, 5, 1};
        for(int i=0;i<5;i++)
        {
            int minIndex=i;
            for(int j=i+1;j<5;j++)
            {
                if(arr[j]<arr[minIndex])
                {
                    minIndex=j;
                }
            }
            int tmp=arr[i];
            arr[i]=arr[minIndex];
            arr[minIndex]=tmp;
        }
        System.out.println(Arrays.toString(arr));
    }
}

This is a Java program that demonstrates the selection sort algorithm to sort an array of integers in ascending order. The array is initialized with 5 integers in random order. The outer loop iterates over the indices of the array, starting from 0 and ending at n-1, where n is the length of the array. For each index i, the inner loop finds the index j of the smallest element in the subarray from i+1 to the end of the array.

In the inner loop, the variable minIndex is initialized to i, and then each element in the subarray is compared with the element at minIndex. If an element smaller than the current minimum is found, minIndex is updated to the index of that element. After the inner loop completes, the element at minIndex is swapped with the element at index i using a temporary variable.

Then, the sorted array is printed to the console using the Arrays.toString method from the Java standard library. This program is an example of how the selection sort algorithm can be implemented in Java to efficiently sort an array of integers in ascending order.

Selection Sort using Javascript

var arr=[4, 2, 3, 5, 1];
for(var i=0;i<5;i++)
{
    var minIndex=i;
    for(var j=i+1;j<5;j++){
        if(arr[j]<arr[minIndex])
        {
            minIndex=j;
        }
    }
    [arr[i], arr[minIndex]]=[arr[minIndex], arr[i]];
}
console.log(arr)

This JavaScript code snippet shows an implementation of the selection sort algorithm to sort an array of numbers in ascending order. The array to be sorted is initialized as arr=[4, 2, 3, 5, 1]. The outer loop iterates through each element in the array, selecting the smallest element and swapping it with the current element if necessary until the entire array is sorted.

Within the outer loop, the variable minIndex is set to the current index of the outer loop, and the inner loop iterates through the remaining elements of the array to find the index of the smallest element. If an element smaller than the current minimum is found, minIndex is updated to the index of the new minimum element.

After the inner loop has been completed, the current element of the outer loop and the smallest element found in the inner loop are swapped using array destructuring. This process continues until the entire array is sorted.

Finally, the sorted array is printed to the console using console.log(arr).