Selection sort

What's Selection Sort? 💡

Selection Sort is a simple comparison-based sorting (opens in a new tab) algorithm that works by repeatedly finding the minimum (or maximum) element from an unsorted portion of the array and moving it to the beginning (or end) of the sorted portion. It continues this process until the entire array is sorted. This algorithm is straightforward to understand and implement, making it a useful educational tool for teaching sorting concepts.

Time Complexity: ⏱️

The time complexity of Selection Sort is quadratic, which means it's not efficient for large datasets. It performs roughly n^2 comparisons and n swaps, regardless of the initial order of the elements

Space Complexity: ⚙️

The space complexity of Selection Sort is O(1), meaning it doesn't require additional memory allocation proportional to the input size. It sorts the array in place (opens in a new tab), making it memory-efficient.

Strengths and Weaknesses of Selection Sort 🤓

Strengths: ⚪️

• Simple to understand and implement.
• Memory-efficient (in-place sorting).
• Stable sorting preserves the order of equal elements.
• Suitable for small lists with low overhead.

Weaknesses: 🔴

• Highly inefficient for large datasets (quadratic time complexity).
• Lacks adaptivity to partially sorted input.
• Limited potential for parallel processing.

Code 🖋

const selectionSort = (arr) => {
    const len = arr.length;
 
    for (let i = 0; i < len - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex !== i) {
            // Swap arr[i] and arr[minIndex]
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
}
 
const numbers = [64, 25, 12, 22, 11];
selectionSort(numbers);
console.log(numbers); // Output: [11, 12, 22, 25, 64]

Conclusion 🗯️

Selection Sort is a straightforward sorting algorithm with a predictable time and space complexity. While it's not efficient for large datasets, it can be useful for educational purposes and for sorting small lists or arrays where simplicity and minimal memory usage are more important than sorting speed. However, in most practical scenarios, other sorting algorithms like Quick Sort or Merge Sort are preferred for their better performance characteristics.