Selection sort

Selection sort is an in-place comparison sort that works by dividing the input list into two parts: a sorted sublist of items that are built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

Initially, the sorted portion is empty and the unsorted portion is the entire input list. The algorithm repeatedly selects the smallest element from the unsorted portion of the list and appends it to the sorted portion until there are no more elements remaining in the unsorted portion.

Here is some example pseudocode for the selection sort algorithm:

for i = 0 to n-2:
    # Find the minimum element in the unsorted portion of the list
    min_index = i
    for j = i+1 to n-1:
        if list[j] < list[min_index]:
            min_index = j
    # Swap the minimum element with the first element of the unsorted portion
    list[i], list[min_index] = list[min_index], list[i]

Selection sort has a time complexity of O(n^2), which makes it inefficient for large lists. However, it is simple to implement and requires minimal additional space.

Steps to Sort Array

To perform selection sort on the list [64, 25, 12, 22, 11], you can follow these steps:

1. Begin with the entire list as the unsorted portion and an empty sorted portion. The unsorted portion is [64, 25, 12, 22, 11] and the sorted portion is [].
2. Find the minimum element in the unsorted portion of the list. The minimum element is 11.
3. Append the minimum element to the sorted portion and remove it from the unsorted portion. The sorted portion is now [11] and the unsorted portion is [64, 25, 12, 22].
4. Find the minimum element in the unsorted portion of the list. The minimum element is 12.
5. Append the minimum element to the sorted portion and remove it from the unsorted portion. The sorted portion is now [11, 12] and the unsorted portion is [64, 25, 22].
6. Find the minimum element in the unsorted portion of the list. The minimum element is 22.
7. Append the minimum element to the sorted portion and remove it from the unsorted portion. The sorted portion is now [11, 12, 22] and the unsorted portion is [64, 25].
8. Find the minimum element in the unsorted portion of the list. The minimum element is 25.
9. Append the minimum element to the sorted portion and remove it from the unsorted portion. The sorted portion is now [11, 12, 22, 25] and the unsorted portion is [64].
10. Find the minimum element in the unsorted portion of the list. The minimum element is 64.
11. Append the minimum element to the sorted portion and remove it from the unsorted portion. The sorted portion is now [11, 12, 22, 25, 64] and the unsorted portion is [].
12. There are no more elements remaining in the unsorted portion, so the sorting is complete. The final sorted list is [11, 12, 22, 25, 64].

Selection Sort in Different language

C++

#include <algorithm>
#include <iostream>
#include <vector>

void selectionSort(std::vector<int> &list) {
    for (int i = 0; i < list.size() - 1; i++) {
        // Find the minimum element in the unsorted portion of the list
        int minIndex = i;
        for (int j = i + 1; j < list.size(); j++) {
            if (list[j] < list[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the minimum element with the first element of the unsorted portion
        std::swap(list[i], list[minIndex]);
    }
}

int main() {
    std::vector<int> list = {64, 25, 12, 22, 11};
    selectionSort(list);
    for (int n : list) {
        std::cout << n << " ";
    }
    std::cout << std::endl;
    return 0;
}

Java

import java.util.Arrays;

public class SelectionSort {
    public static void selectionSort(int[] list) {
        for (int i = 0; i < list.length - 1; i++) {
            // Find the minimum element in the unsorted portion of the list
            int minIndex = i;
            for (int j = i + 1; j < list.length; j++) {
                if (list[j] < list[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap the minimum element with the first element of the unsorted portion
            int temp = list[i];
            list[i] = list[minIndex];
            list[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        int[] list = {64, 25, 12, 22, 11};
        selectionSort(list);
        System.out.println(Arrays.toString(list)); // [11, 12, 22, 25, 64]
    }
}

JavaScript

function selectionSort(list) {
    for (let i = 0; i < list.length - 1; i++) {
        // Find the minimum element in the unsorted portion of the list
        let minIndex = i;
        for (let j = i + 1; j < list.length; j++) {
            if (list[j] < list[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the minimum element with the first element of the unsorted portion
        [list[i], list[minIndex]] = [list[minIndex], list[i]];
    }
    return list;
}

const sortedList = selectionSort([5, 2, 4, 6, 1, 3]);
console.log(sortedList); // [1, 2, 3, 4, 5, 6]

PHP

<?php

function selectionSort(array &$list) {
    for ($i = 0; $i < count($list) - 1; $i++) {
        // Find the minimum element in the unsorted portion of the list
        $minIndex = $i;
        for ($j = $i + 1; $j < count($list); $j++) {
            if ($list[$j] < $list[$minIndex]) {
                $minIndex = $j;
            }
        }
        // Swap the minimum element with the first element of the unsorted portion
        $temp = $list[$i];
        $list[$i] = $list[$minIndex];
        $list[$minIndex] = $temp;
    }
}

$list = [64, 25, 12, 22, 11];
selectionSort($list);
print_r($list); // Array ( [0] => 11 [1] => 12 [2] => 22 [3] => 25 [4] => 64 )

Python

def selection_sort(list):
    for i in range(len(list) - 1):
        # Find the minimum element in the unsorted portion of the list
        min_index = i
        for j in range(i + 1, len(list)):
            if list[j] < list[min_index]:
                min_index = j
        # Swap the minimum element with the first element of the unsorted portion
        list[i], list[min_index] = list[min_index], list[i]
    return list

sorted_list = selection_sort([5, 2, 4, 6, 1, 3])
print(sorted_list) # [1, 2, 3, 4, 5, 6]

Read More Sorting Algorithms

Bubble Sort Algorithm

Insertion sort: a Sorting Algorithm

List of Sorting Algorithms

To Read Jokes Visit Here