Selection Sort in C++

Sorting is a fundamental operation in computer science that arranges a collection of elements in a specific order. One of the simplest sorting algorithms is selection sort, which is easy to understand and implement.

Selection Sort

Selection sort is an in-place comparison-based sorting algorithm. It works by dividing the input into two subarrays: the sorted subarray and the unsorted subarray. The sorted subarray is built gradually by repeatedly finding the minimum element from the unsorted subarray and placing it at the beginning. The algorithm maintains a boundary between the sorted and unsorted portions until the entire array is sorted.

Selection Sort Steps

1. Start with an unsorted list of elements.
2. Find the smallest element in the list.
3. Swap the smallest element with the first element in the list.
4. Consider the remaining unsorted portion of the list (excluding the first element).
5. Find the smallest element in the unsorted portion.
6. Swap the smallest element with the second element in the list.
7. Continue this process, selecting the smallest element from the remaining unsorted
8. portion and swapping it with the next element in the list, until the entire list is sorted.
9. The list is now sorted in ascending order.

Selection Sort C++ Implementation

#include <iostream>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;

        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }

        // Swapping the minimum element with the first unsorted element
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

// Main method
int main() {
    int arr[] = {64, 25, 12, 22, 11,27,11,8,9,34,4,56,2,7,12,67,34};
    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);

    std::cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;

    return 0;
}

In the above code, we start with the outer loop that iterates through each element of the array from the beginning. Inside the outer loop, we initialize minIndex to the current element’s index. The inner loop then finds the minimum element in the unsorted subarray by comparing each element with the current minimum.

After finding the minimum element, we swap it with the first unsorted element. This ensures that the minimum element is placed at the correct position in the sorted subarray. We repeat this process until the entire array is sorted.

Advantages and Disadvantages of Selection Sort

Advantages of Selection Sort

• Simplicity: The algorithm is straightforward to understand and implement.
• In-place Sorting: Selection sort performs sorting in-place, which means it doesn’t require additional memory.

Disadvantages of Selection Sort

• Time Complexity: The time complexity of selection sort is O(n^2), making it inefficient for large datasets.
• Lack of Adaptability: Selection sort doesn’t adapt to the input data’s initial order, making it perform the same number of comparisons regardless of the input’s order.

Time Complexity of Selection Sort

Selection sort follows a simple approach of repeatedly selecting the smallest (or largest) element and placing it in its correct position. Let’s analyze the time complexity of selection sort in different scenarios.

Best Case

In the best-case scenario, the input array is already sorted. However, selection sort does not have any mechanism to detect the sorted nature of the array. It will still perform the same number of comparisons and swaps as in the average and worst cases. Therefore, the best-case time complexity of selection sort remains unchanged.

Average Case Time

In the average-case scenario, selection sort exhibits a time complexity of O(n^2), where ‘n’ represents the number of elements in the input array. This quadratic time complexity arises from the nested loops employed by selection sort. The outer loop iterates ‘n’ times, and for each iteration, the inner loop iterates ‘n – 1’ times in the worst case. Thus, the overall time complexity is determined by the product of these two loop iterations, resulting in O(n^2).

Worst Case Time Complexity

The worst-case time complexity of selection sort is also O(n^2). This occurs when the input array is in reverse order or contains elements in a descending order. In such cases, selection sort requires the maximum number of comparisons and swaps. The outer loop iterates ‘n’ times, and the inner loop iterates ‘n – 1’ times during each iteration of the outer loop. Therefore, the overall time complexity remains quadratic.

Although selection sort has a time complexity of O(n^2), it is worth noting that it can be efficient for small input sizes or when the number of elements is relatively limited. However, for larger datasets, more efficient sorting algorithms such as merge sort or quicksort are generally preferred.

Conclusion

Selection sort is a simple and intuitive sorting algorithm that offers a clear understanding of its time complexity. The time complexity of selection sort is O(n^2) in both the average and worst cases, indicating its quadratic growth rate with increasing input size. While selection sort may not be the most efficient algorithm for larger datasets, it serves as a valuable learning tool for understanding sorting principles and can be suitable for small-scale sorting tasks.

By comprehending the time complexity of selection sort, we can make informed decisions when choosing sorting algorithms based on the size and nature of the input data. It is crucial to consider the trade-offs between simplicity and efficiency in various scenarios to optimize the sorting process effectively.

• Quick Sort in C++
• Quick Sort in Java
• Quick Sort in JavaScript