Sorting: Selection Sort in Python (O(n^2) Time Complexity)

In this video lesson we will learn what sorting is, when it should be used and we will code our first sorting algorithm - Selection Sort:

Problem - Selection Sort:

Given an array of integers nums, sort it in ascending order using Selection Sort

Example 1:

Input: nums = [3, 1, 3, 2, 5, 4]
Output: [1, 2, 3, 3, 4, 5]

Note:

Your algorithm should run in O(n^2) time and use O(1) extra space.

Understanding the Problem

The core challenge of this problem is to sort an array of integers using the Selection Sort algorithm. Selection Sort is a simple comparison-based sorting algorithm. It divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list.

Selection Sort is significant in educational contexts because it helps to understand the basic principles of sorting algorithms. However, it is not used in practice for large datasets due to its O(n^2) time complexity.

Approach

To solve this problem, we can follow these steps:

Iterate over the array to find the minimum element in the unsorted part of the array.
Swap the found minimum element with the first element of the unsorted part.
Move the boundary between the sorted and unsorted parts one element to the right.
Repeat the process until the entire array is sorted.

Let's discuss a naive approach and then move to the optimized solution:

Naive Approach

The naive approach is to use nested loops to find the minimum element and swap it with the first element of the unsorted part. This approach is straightforward but not optimal for large datasets due to its O(n^2) time complexity.

Optimized Approach

Selection Sort itself is not highly optimized, but we can ensure that our implementation is efficient by minimizing unnecessary swaps and comparisons.

Algorithm

Here is a step-by-step breakdown of the Selection Sort algorithm:

Start with the first element of the array.
Find the minimum element in the unsorted part of the array.
Swap the minimum element with the first element of the unsorted part.
Move the boundary between the sorted and unsorted parts one element to the right.
Repeat the process until the entire array is sorted.

Code Implementation

def selection_sort(nums):
    # Traverse through all array elements
    for i in range(len(nums)):
        # Find the minimum element in remaining unsorted array
        min_idx = i
        for j in range(i+1, len(nums)):
            if nums[min_idx] > nums[j]:
                min_idx = j
        
        # Swap the found minimum element with the first element
        nums[i], nums[min_idx] = nums[min_idx], nums[i]

    return nums

# Example usage
nums = [3, 1, 3, 2, 5, 4]
sorted_nums = selection_sort(nums)
print(sorted_nums)  # Output: [1, 2, 3, 3, 4, 5]

Complexity Analysis

The time complexity of Selection Sort is O(n^2) because of the nested loops. The space complexity is O(1) as it only requires a constant amount of extra space.

Edge Cases

Some potential edge cases include:

An empty array: The algorithm should handle this gracefully and return an empty array.
An array with one element: The algorithm should return the array as is.
An array with all identical elements: The algorithm should return the array as is.

Examples:

print(selection_sort([]))  # Output: []
print(selection_sort([1]))  # Output: [1]
print(selection_sort([2, 2, 2]))  # Output: [2, 2, 2]

Testing

To test the solution comprehensively, we should include a variety of test cases:

Simple cases with small arrays.
Edge cases like empty arrays and arrays with one element.
Arrays with duplicate elements.
Arrays that are already sorted.
Arrays sorted in reverse order.

Example test cases:

assert selection_sort([3, 1, 3, 2, 5, 4]) == [1, 2, 3, 3, 4, 5]
assert selection_sort([]) == []
assert selection_sort([1]) == [1]
assert selection_sort([2, 2, 2]) == [2, 2, 2]
assert selection_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]

Thinking and Problem-Solving Tips

When approaching sorting problems, it's important to understand the properties and limitations of different sorting algorithms. Practice by implementing various sorting algorithms and analyzing their time and space complexities. This will help you choose the right algorithm for different scenarios.

Conclusion

Selection Sort is a simple and intuitive sorting algorithm that is useful for educational purposes. While it is not suitable for large datasets due to its O(n^2) time complexity, understanding its mechanics provides a foundation for learning more advanced sorting algorithms.

Additional Resources

For further reading and practice, consider the following resources: