Selection Sort Algorithm

Selection Sort is a simple comparison-based sorting algorithm that works by repeatedly selecting the smallest (or largest, depending on sorting order) element from the unsorted portion of the list and moving it to the sorted portion. It has a time complexity of O(n²) in all cases.

How the Selection Sort Algorithm Works

1. Divide the list into two parts: A sorted section (initially empty) and an unsorted section.
2. Find the minimum element in the unsorted section.
3. Swap it with the first element of the unsorted section, effectively growing the sorted section by one element.
4. Repeat the remaining unsorted section until the entire list is sorted.

Step-by-Step Example

There is an example array;

[29, 10, 14, 37, 13]

Step 1

• Find the smallest element in [29, 10, 14, 37, 13], which is 10.
• Swap 10 with 29.
• Array after the swap:
  [10, 29, 14, 37, 13]

Step 2

• Find the smallest element in [29, 14, 37, 13], which is 13.
• Swap 13 with 29.
• Array after the swap:
  [10, 13, 14, 37, 29]

Step 3

• Find the smallest element in [14, 37, 29], which is 14 (already in place).
• No swap needed.
• Array remains:
  [10, 13, 14, 37, 29]

Step 4

• Find the smallest element in [37, 29], which is 29.
• Swap 29 with 37.
• Array after the swap:
  [10, 13, 14, 29, 37]
• Now, the array is fully sorted.

When to Use Selection Sort Algorithm?

✅ Simple to implement
✅ Works well for small datasets
✅ Uses minimal memory (in-place sorting)
❌ Inefficient for large datasets due to O(n²) complexity. Other algorithms like Quick Sort, Merge Sort, or Heap Sort are preferred in real-world applications.

Usage Areas of Selection Sort

Although Selection Sort is not the most efficient sorting algorithm for large datasets due to its O(n²) time complexity, it has some specific use cases where its properties make it useful.

Below are some areas where Selection Sort can be applied.

Small Data Sets & Simple Applications

• Embedded Systems & Low-Memory Devices: Since Selection Sort requires only constant O(1) extra space, it is useful in memory-constrained environments.
• Sorting Small Arrays: For very small datasets (e.g., fewer than 10 elements), its simplicity can make it a good choice over more complex algorithms.
• Educational Purposes: It is commonly taught in computer science courses as an introduction to sorting algorithms due to its simple logic.

Cases Where Swaps Are Costly

• Selection Sort performs fewer swaps than other sorting algorithms like Bubble Sort. This makes it useful when swapping elements is an expensive operation (e.g., in flash memory where write operations are costly).
• Example: Sorting a list stored in an EEPROM (Electrically Erasable Programmable Read-Only Memory), where reducing writes can extend the lifespan of the memory.

When Stability Is Not a Concern

• Selection Sort is not a stable sort, meaning equal elements may change their order.
• If stability is not an issue (e.g., sorting numbers, not objects with additional properties), it can be used in non-critical applications.

Hybrid Sorting Approaches

• In some sorting algorithms (e.g., Timsort, IntroSort), smaller subarrays are sorted using simpler algorithms like Selection Sort or Insertion Sort.
• Example: Switching to Selection Sort for very small partitions in QuickSort or MergeSort.

Sorting Linked Lists in Special Cases

• Selection Sort can be applied to linked lists where swapping involves only pointer manipulation rather than expensive memory shifts.
• However, Merge Sort is usually preferred for sorting linked lists because it has a better time complexity O(nlogn).

Organizing Data in Specific Applications

• Sports Tournaments: Selection Sort can be used to rank players based on their scores if the number of players is small.
• Basic Scheduling Systems: For simple job scheduling tasks where order does not change dynamically.

Selection Sort Algorithm in Programming Languages

Python Selection Sort Algorithm

def selection_sort(arr):
    n = len(arr)
    
    for i in range(n - 1):  # Iterate through the array
        min_index = i  # Assume the first element is the smallest
        
        for j in range(i + 1, n):  # Find the smallest element in the remaining array
            if arr[j] < arr[min_index]:
                min_index = j  # Update min_index if a smaller element is found
        
        # Swap the found minimum element with the first element of the unsorted part
        arr[i], arr[min_index] = arr[min_index], arr[i]
    
    return arr  # Return the sorted array

# Example Usage
arr = [29, 10, 14, 37, 13]
sorted_arr = selection_sort(arr)
print("Sorted Array:", sorted_arr)

JavaScript Selection Sort Algorithm

function selectionSort(arr) {
    let n = arr.length;
    
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i; // Assume the first element is the smallest

        for (let j = i + 1; j < n; j++) { 
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // Update minIndex if a smaller element is found
            }
        }

        // Swap the found minimum element with the first element of the unsorted part
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }

    return arr; // Return the sorted array
}

// Example Usage
let arr = [29, 10, 14, 37, 13];
let sortedArr = selectionSort(arr);
console.log("Sorted Array:", sortedArr);