Sorting: Selection Sort in C++ (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 because it is easy to understand and implement. However, it is not suitable for large datasets as its average and worst-case time complexity is quite high (O(n^2)).

Approach

To solve this problem, we can follow these steps:

Start with the first element of the array and assume it is the minimum.
Compare this minimum with the second element. If the second element is smaller, update the minimum.
Continue this process for the entire array. At the end of the first pass, swap the minimum element found with the first element of the array.
Repeat the process for the next position in the array until the entire array is sorted.

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

Naive Approach

The naive approach involves iterating through the array and finding the minimum element in each pass, then swapping it with the first unsorted element. 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 it is simple and works well for small datasets. The optimized approach for Selection Sort involves reducing the number of swaps by only swapping when necessary.

Algorithm

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

Initialize the sorted sublist as empty and the unsorted sublist as the entire array.
Find the minimum element in the unsorted sublist.
Swap the minimum element with the first element of the unsorted sublist.
Move the boundary of the sorted sublist one element to the right.
Repeat until the entire array is sorted.

Code Implementation

#include <iostream>
#include <vector>
using namespace std;

// Function to perform Selection Sort
void selectionSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n - 1; ++i) {
        // Find the minimum element in the unsorted part
        int minIndex = i;
        for (int j = i + 1; j < n; ++j) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the found minimum element with the first element
        swap(nums[i], nums[minIndex]);
    }
}

int main() {
    vector<int> nums = {3, 1, 3, 2, 5, 4};
    selectionSort(nums);
    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}

Complexity Analysis

The time complexity of Selection Sort is O(n^2) because of the two nested loops: one for iterating through the array and the other for finding the minimum element. 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 without errors.
An array with one element: The array is already sorted, so no changes should be made.
An array with all identical elements: The algorithm should recognize that no swaps are needed.

Testing

To test the solution comprehensively, consider the following test cases:

Simple cases with small arrays.
Edge cases like empty arrays and single-element arrays.
Arrays with duplicate elements.
Arrays that are already sorted.

Thinking and Problem-Solving Tips

When approaching sorting problems, it is essential to understand the properties and limitations of different sorting algorithms. Practice by implementing various sorting algorithms and analyzing their performance on different datasets. This will help you develop a deeper understanding of their strengths and weaknesses.

Conclusion

Selection Sort is a simple and intuitive sorting algorithm that is easy to implement. While it is not suitable for large datasets due to its O(n^2) time complexity, it is a good starting point for learning about sorting algorithms. Understanding Selection Sort provides a foundation for exploring more advanced sorting techniques.

Additional Resources

For further reading and practice problems related to sorting algorithms, consider the following resources: