Selection Sort

Introduction to Selection Sort

Selection Sort is a comparison-based sorting algorithm. It operates by dividing the input list into a sorted and an unsorted region, repeatedly selecting the smallest (or largest) element from the unsorted region and moving it to the end of the sorted region.

The algorithm operates in-place and works by repeatedly selecting the minimum element from the unsorted portion and swapping it with the first unsorted element. This process continues until the entire list is sorted.

Selection Sort Demonstration

Time Complexity

The time complexity of selection sort is O(n²) in all cases—best, average, and worst. This is because selection sort always performs a linear scan to find the minimum element for each position in the array.

Despite its simplicity, the quadratic time complexity makes selection sort inefficient for large datasets compared to more advanced sorting algorithms such as quicksort and mergesort.

Space Complexity

Selection Sort is an in-place sorting algorithm, which means it requires a minimal amount of extra storage. The algorithm operates by selecting the minimum element and rearranging the elements within the same array.

Therefore the space complexity of Selection Sort is O(1), indicating that it uses a constant amount of additional memory regardless of the input size.

Python Example

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]  # Swap the elements

# Example usage
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array:", arr)

Pros and Cons of Selection Sort

Advantages

Selection Sort is easy to understand and implement, making it a great choice for teaching sorting concepts. It has a constant space complexity, requiring only a small amount of additional memory.

Disadvantages

The performance of Selection Sort is subpar for large datasets, with a time complexity of O(n²). Additionally, it is unstable, meaning that it does not preserve the relative order of equal elements.