What Is Selection Sort Algorithm? Explained With Code Examples

11 mins read

Sorting is a fundamental operation in computer science, and one of the simplest sorting techniques is the Selection Sort algorithm. It follows a straightforward approach: repeatedly finding the smallest (or largest) element from an unsorted section and swapping it with the first unsorted element. While not the most efficient sorting method for large datasets, its simplicity makes it a great choice for learning how sorting works at a basic level.

In this article, we will explore the working of the Selection Sort algorithm, its time complexity, implementation in different programming languages, and key advantages and limitations.

Understanding The Selection Sort Algorithm

Selection Sort is a simple and intuitive sorting algorithm that works by repeatedly finding the smallest (or largest) element from the unsorted part of the array and swapping it with the first unsorted element. This process continues until the entire array is sorted.

How Selection Sort Works

1. Start with the first element and assume it is the smallest.
2. Scan the rest of the array to find the actual smallest element.
3. Swap the smallest element found with the first element.
4. Move to the next position and repeat the process for the remaining unsorted part of the array.
5. Continue until the array is fully sorted.

Real-Life Analogy

Imagine you are organizing books on a shelf in ascending order of size. You start by picking the smallest book (shortest in height) and placing it in the first position. Then, you find the next smallest and place it in the second position. You continue this process until all books are in order. This is exactly how Selection Sort works with different data structures!

Algorithmic Approach To Selection Sort

Selection Sort follows a straightforward approach to sorting an array. Let's first look at the pseudo-code, followed by an explanation of its key steps.

Pseudo-code For Selection Sort

SelectionSort(arr, n):
    for i from 0 to n-2:    // Loop over each element except the last
        min_index = i        // Assume the first element of the unsorted part is the smallest
        for j from i+1 to n-1:  // Find the minimum in the unsorted part
            if arr[j] < arr[min_index]:
                min_index = j
        Swap arr[i] and arr[min_index]  // Place the smallest element at its correct position

Key Steps In The Working Of The Algorithm

1. Initialize Outer Loop (i from 0 to n-2)

• The loop runs from the first element to the second-last element since the last element will already be sorted after all iterations.
• We assume the first element of the unsorted section (arr[i]) is the minimum.

2. Find the Minimum Element in the Remaining Array

• A second loop (j from i+1 to n-1) scans the unsorted part of the array.
• If an element smaller than arr[min_index] is found, update min_index to store its index.

3. Swap the Found Minimum Element with the First Unsorted Element

• After finding the smallest element in the unsorted part, swap it with arr[i] to place it in its correct position.

4. Repeat the Process Until the Entire Array is Sorted

• The outer loop progresses, shrinking the unsorted part, until the whole array is sorted.

Implementation Of Selection Sort Algorithm

Below is the C++ implementation of the Selection Sort algorithm.

Code Example: 

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_index = i; // Assume first unsorted element is the smallest

        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_index]) {
                min_index = j; // Update the index of the minimum element
            }
        }

        // Swap the found minimum element with the first element of the unsorted part
        swap(arr[i], arr[min_index]);
    }
}

// Function to print the array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {29, 10, 14, 37, 13};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    selectionSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Output: 

Original array: 29 10 14 37 13
Sorted array: 10 13 14 29 37

Explanation:

In the above code example-

1. We start by including the necessary header file <iostream> to use input-output operations. The using namespace std; statement allows us to use standard library functions without prefixing them with std::.
2. The selectionSort() function sorts an array using the Selection Sort algorithm. It takes an array and its size as parameters.
3. In each iteration of the outer loop, we assume the first unsorted element is the smallest. We store its index in min_index.
4. The inner loop iterates through the remaining unsorted elements to find the actual smallest element in that part of the array. If a smaller element is found, we update min_index to its position.
5. After finding the minimum element in the unsorted part, we swap it with the first unsorted element, ensuring that the sorted portion of the array expands with each iteration.
6. The printArray() function is a helper function that prints all elements of the array separated by spaces, followed by a newline.
7. In main(), we define an array {29, 10, 14, 37, 13} and calculate its size using sizeof(arr) / sizeof(arr[0]).
8. We print the original array before sorting using the printArray() function.
9. We call selectionSort() to sort the array in ascending order.
10. After sorting, we print the updated array to show the sorted result.
11. The program returns 0, indicating successful execution.

Complexity Analysis Of Selection Sort

The table below summarizes the time and space complexity of the Selection Sort algorithm in different scenarios.

Comparison Of Selection Sort With Other Sorting Algorithms

The table below compares Selection Sort with other common sorting algorithms based on key parameters like time complexity, space complexity, stability, and adaptiveness.

Key Takeaways:

• Selection Sort is inefficient for large datasets due to its O(n²) time complexity.
• Merge Sort, Quick Sort, and Heap Sort are more efficient with O(n log n) time complexity.
• Bubble Sort and Insertion Sort are adaptive, meaning they perform better on nearly sorted data.
• Stable Sorting Algorithms (like Merge Sort, Bubble Sort, and Counting Sort) maintain the order of equal elements.

Advantages And Disadvantages Of Selection Sort

Let's explore the strengths and weaknesses of Selection Sort.

Advantages Of Selection Sort:

1. Simple and Easy to Implement: The algorithm is straightforward and does not require complex logic.
2. In-Place Sorting Algorithm: It requires only O(1) extra space, meaning it does not need additional memory beyond the input array.
3. Performs Well on Small Datasets: For small arrays, Selection Sort can be a viable option due to its simplicity.
4. Works Well When Memory Writes Are Costly: Since it performs at most (n-1) swaps, it minimizes writes compared to Bubble Sort or Insertion Sort, making it useful in scenarios like Flash memory where write operations are expensive.

Disadvantages Of Selection Sort:

1. Time Complexity is Always O(n²): Regardless of whether the input is sorted or not, Selection Sort always performs O(n²) comparisons, making it inefficient for large datasets.
2. Not a Stable Sort: If there are equal elements, their relative order might change due to swapping, which can cause issues in some applications.
3. Not Adaptive: Selection Sort does not take advantage of already sorted or partially sorted data, unlike Insertion Sort, which performs O(n) in the best case.
4. Slower Compared to Other Sorting Algorithms: Sorting algorithms like Merge Sort, Quick Sort, and Heap Sort perform much better on large datasets with an average time complexity of O(n log n).

Application Of Selection Sort

Some of the common applications of the selection sort algorithm are:

1. Small datasets – Since Selection Sort has a time complexity of O(n²), it is best suited for small datasets where its simplicity outweighs efficiency concerns.
2. Embedded systems – Due to its minimal memory requirements and in-place sorting nature, Selection Sort is useful in memory-constrained environments like microcontrollers.
3. Teaching sorting concepts – Selection Sort is often used in educational settings to introduce sorting algorithms due to its simple logic and step-by-step element swapping.
4. Sorting linked lists – Although Selection Sort is not the best choice for arrays, it works well with linked lists since swapping nodes requires only pointer adjustments, avoiding unnecessary data movement.
5. Selecting top k elements – When we only need the smallest or largest k elements, Selection Sort can be useful since it finds the smallest elements in each iteration.
6. Stable environments – In cases where data movement cost is minimal and simplicity is preferred over speed, Selection Sort is a viable option.

Conclusion

Selection Sort is a simple yet inefficient sorting algorithm that works by repeatedly selecting the smallest element and placing it in its correct position. While it is easy to understand and implement, its O(n²) time complexity makes it impractical for large datasets. It is not adaptive, meaning it does not benefit from partially sorted data, and it is also not stable, which can impact sorting when dealing with duplicate values.

Despite its limitations, Selection Sort is useful in scenarios where memory writes are expensive, as it performs fewer swaps compared to other quadratic-time algorithms like Bubble Sort. However, for larger datasets, more efficient sorting algorithms like Merge Sort, Quick Sort, or Heap Sort should be preferred.

Frequently Asked Questions

Q. Why is Selection Sort called "Selection" Sort?

Selection Sort gets its name from the way it selects the smallest (or largest) element from the unsorted part of the array and places it in its correct position in each iteration. The process involves repeatedly selecting the minimum element and moving it to the correct position, hence the name Selection Sort.

Q. What is the worst-case time complexity of Selection Sort?

The worst-case time complexity of Selection Sort is O(n²). This happens when the array is sorted in the reverse order because the algorithm still performs (n-1) + (n-2) + ... + 1 comparisons, which sums up to O(n²). Even if the array is already sorted, Selection Sort does not take advantage of it and continues to perform all comparisons.

Q. Is Selection Sort a stable sorting algorithm? Why or why not?

No, Selection Sort is not a stable sorting algorithm. A sorting algorithm is considered stable if it preserves the relative order of equal elements in the sorted output.

For example, consider the following array of tuples where the second value represents an index:

(3, A)  (1, B)  (3, C)  (2, D)

Sorting this using Selection Sort might result in:

(1, B)  (2, D)  (3, C)  (3, A)  ❌ (Order of (3, A) and (3, C) changed)

Since Selection Sort swaps non-adjacent elements, it does not guarantee that equal elements remain in their original order, making it unstable.

Q. When is Selection Sort preferred over other sorting algorithms?

Selection Sort is preferred in the following cases:

• When memory writes are expensive: Since it performs at most n-1 swaps, it is useful for cases where minimizing write operations is crucial (e.g., Flash memory, EEPROM).
• For small datasets: Due to its simple implementation, it can be used for sorting small arrays where efficiency is not a major concern.
• When a stable sort is not required: If the relative order of duplicate elements does not matter, Selection Sort can be considered.

However, for large datasets, Merge Sort, Quick Sort, or Heap Sort are better choices due to their O(n log n) time complexity.

Q. How does Selection Sort compare to Bubble Sort and Insertion Sort?

• Insertion Sort is adaptive, meaning it performs well on nearly sorted arrays (O(n) in best case).
• Bubble Sort is stable, meaning it preserves the order of equal elements, while Selection Sort is not.
• Selection Sort is better than Bubble Sort in terms of fewer swaps, but it still has O(n²) comparisons.

For efficiency, Insertion Sort is preferable when dealing with small or nearly sorted datasets.

Suggested Reads: 

1. Difference Between Hashing And Encryption Decoded
2. 53 Frequently Asked Linked List Interview Questions With Answers 2024
3. Data Structure Interview Questions For 2024 [With Detailed Answers]
4. Tree Topology | Advantages & Disadvantages In Computer Network
5. Decoding Data Redundancy In DBMS| Causes, Advantages, Solutions