Selection Sort: A Simple and Effective Sorting Algorithm

Sorting algorithms are crucial in computer science, and Selection Sort is a straightforward yet effective method to arrange elements in order. This article will explore how Selection Sort works, provide a detailed implementation, and discuss its time and space complexity.

How Selection Sort Works

Selection Sort is a comparison-based sorting algorithm that improves upon Bubble Sort by reducing the number of swaps. It repeatedly finds the minimum element from the unsorted portion of the list and moves it to the beginning.

Key Concepts

1. Finding Minimum: Selection Sort identifies the smallest element from the unsorted portion of the array.
2. Swapping: After finding the minimum, it swaps it with the first unsorted element.
3. Sorted Portion: The sorted portion of the array grows with each iteration.

For a visual representation of Selection Sort and its process, check out this video.

Implementation

Here’s a TypeScript implementation of Selection Sort:

export const selectionSort = (array: number[]): number[] => {
  for (let j = 0; j < array.length; j++) {
    let minIndex = j;
    for (let i = j + 1; i < array.length; i++) {
      if (array[i] < array[minIndex]) {
        minIndex = i;
      }
    }
    // Swap only if a new minimum was found
    if (minIndex !== j) {
      [array[j], array[minIndex]] = [array[minIndex], array[j]];
    }
  }
  return array;
};

Disclaimer: Please note that the following implementation modifies the input array directly to sort the elements in place. If you need to retain the original array, consider creating a copy before applying the sort.

Explanation of the Implementation

1. Outer Loop: The outer loop iterates through each element, assuming it as the starting point of the unsorted portion.
2. Inner Loop: The inner loop searches for the smallest element in the remaining unsorted part of the array.
3. Swap: If a smaller element is found, it is swapped with the first unsorted element. This ensures that the smallest element is placed in its correct position.

Time and Space Complexity

Time Complexity

• Worst-case: O(n²) => This occurs regardless of the input because the algorithm always performs a nested loop comparison.
• Best-case: O(n²) => Unlike some other algorithms, Selection Sort’s time complexity does not improve with an already sorted array.
• Average-case: O(n²) => On average, the algorithm performs O(n²) comparisons.

Space Complexity

• Space Complexity: O(1) => Selection Sort is an in-place sorting algorithm, meaning it requires only a constant amount of additional memory space.

Further Reading

Explore more about other sorting algorithms with our detailed articles:

• Bubble Sort: Learn about this simple algorithm that repeatedly compares adjacent elements.
• Insertion Sort: Discover how this algorithm builds the final sorted array one item at a time.
• Quick Sort: Understand how Quick Sort uses a divide-and-conquer approach for efficient sorting.
• Merge Sort: Read about Merge Sort’s method of dividing the array and merging it into a sorted form.

Conclusion

Selection Sort is a great algorithm for understanding basic sorting principles and operations. While it’s not the most efficient for large datasets due to its O(n²) time complexity, it provides a clear approach to sorting by selecting and placing elements.

Whether you’re new to sorting algorithms or just brushing up on your knowledge, Selection Sort is a fundamental algorithm that showcases the importance of finding and positioning elements efficiently.