Selection sort

Introduction:

In the realm of computer science and programming, sorting algorithms play a crucial role in organizing data efficiently. One such algorithm is selection sort. This article will delve into the inner workings of selection sort, exploring its simplicity, time complexity, and performance advantages in certain scenarios.
What is Selection Sort?
Selection sort is an in-place comparison sorting algorithm that operates by dividing the input list into two parts: the sorted portion on the left and the unsorted portion on the right. The algorithm repeatedly selects the smallest element from the unsorted portion and swaps it with the leftmost element of the unsorted portion. This process continues until the entire list is sorted.

Understanding the Algorithm:

To better grasp the inner workings of selection sort, let’s walk through a simple example using the following unsorted list: [4, 2, 8, 1, 5].

Initialization: Consider the entire list as unsorted initially.
Finding the Minimum: Search for the smallest element in the unsorted portion (in this case, 1 is the smallest).
Swapping: Swap the smallest element with the leftmost element of the unsorted portion (swap 1 with 4).
Result: [1, 2, 8, 4, 5]
Repeat: Move the boundary of the sorted and unsorted portions one element to the right.
Finding the Minimum: Search for the smallest element in the new unsorted portion (in this case, 2 is the smallest).
Swapping: Swap the smallest element with the leftmost element of the unsorted portion (swap 2 with 2, no change).
Result: [1, 2, 8, 4, 5]
Repeat: Move the boundary of the sorted and unsorted portions one element to the right.
Finding the Minimum: Search for the smallest element in the new unsorted portion (in this case, 4 is the smallest).
Swapping: Swap the smallest element with the leftmost element of the unsorted portion (swap 4 with 8).
Result: [1, 2, 4, 8, 5]
Repeat: Move the boundary of the sorted and unsorted portions one element to the right.
Finding the Minimum: Search for the smallest element in the new unsorted portion (in this case, 5 is the smallest).
Swapping: Swap the smallest element with the leftmost element of the unsorted portion (swap 5 with 8).
Result: [1, 2, 4, 5, 8]
Repeat: Move the boundary of the sorted and unsorted portions one element to the right.
Final Result: The list is now fully sorted: [1, 2, 4, 5, 8].

Time Complexity and Performance:

Selection sort has a time complexity of O(n2), where n represents the number of elements in the input list. This makes it less efficient than other sorting algorithms, such as merge sort or quicksort, which have time complexities of O(n log n) in average cases.
However, selection sort outperforms more complex algorithms in certain scenarios, particularly when auxiliary memory is limited. Due to its in-place nature, selection sort does not require additional memory space beyond the input list itself. This makes it advantageous in situations where memory constraints are a concern.

selection sort

Is an in-place comparison sorting algorithm. It has an O(n2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity and has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

Links

Code Examples

C#
public void SelectionSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

JavaScript
function selectionSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
}

Python
def selection_sort(arr):
    n = len(arr)
    for iUser input: