Selection Sort Algorithm

Selection Sort is a fundamental sorting algorithm in computer science that arranges an array by repeatedly finding the minimum element from the unsorted section and placing it at the beginning. This tutorial aims to clarify the algorithm's working principle and provide practical code examples for implementing it.

Understanding Selection Sort Algorithm

Selection Sort is an in-place comparison-driven sorting algorithm that divides an input list into a sorted sublist and an unsorted sublist. At each iteration, it selects the smallest (or largest) element from the unsorted portion and swaps it with the first element of the unsorted section. This process does not involve comparing the selected smallest (or largest) element with those in the sorted section; instead, comparisons are made only within the unsorted part to identify the minimum (or maximum) element.

How Selection Sort Works

Consider you have an unsorted array: [29, 10, 37, 14, 13], and you want to sort it in ascending order utilizing the Selection Sort algorithm. Unlike Bubble Sort, which iterates through the list to swap adjacent elements, Selection Sort improves efficiency by minimizing swaps.

Implementation Examples

C++ Example

Implementing Selection Sort in C++ is straightforward. The following code snippet demonstrates this process:

Example:

#include <iostream>
using namespace std;

// Function to perform selection sort on an array
void selectionSort(int arr[], int n) {
    // Loop through each element of the array except the last one
    for (int i = 0; i < n-1; i++) {
        // Assume the first unsorted element is the minimum
        int minIndex = i;
        
        // Compare this element with the rest of the unsorted portion of the array to find the true minimum
        for (int j = i+1; j < n; j++) {
            // If a smaller element is found, update minIndex with the new minimum element's index
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

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

int main() {
    // Initialize array with unsorted elements
    int arr[] = {29, 10, 37, 14, 13};
    // Calculate number of elements in the array
    int n = sizeof(arr)/sizeof(arr[0]);
    
    // Call selectionSort function to sort the array
    selectionSort(arr, n);
    
    // Print the sorted array
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

Output:

Sorted array: 10 13 14 29 37

Here is a C++ code snippet for implementing the Selection Sorting Algorithm by taking user input:

Example:

#include <iostream>
using namespace std;

// Function to perform selection sort on an array
void selectionSort(int arr[], int n) {
    // Loop through each element of the array except the last one
    for (int i = 0; i < n-1; i++) {
        // Assume the first unsorted element is the minimum
        int minIndex = i;
        
        // Compare this element with the rest of the unsorted portion of the array to find the true minimum
        for (int j = i+1; j < n; j++) {
            // If a smaller element is found, update minIndex with the new minimum element's index
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

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

int main() {
    int arr[100], n;

    // Input the number of elements
    cout << "Enter the number of elements: ";
    cin >> n;

    // Input the elements
    cout << "\nEnter " << n << " elements:\n";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // Sorting the array using Selection Sort
    selectionSort(arr, n);

    // Output the sorted array
    cout << "\nSorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

Output:

Enter the number of elements: 5

Enter 5 elements:
29
10
37
14
13

Sorted array: 10 13 14 29 37

Python Example

In Python, the Selection Sort algorithm can be implemented as follows:

Example:

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

# Example usage
arr = [29, 10, 37, 14, 13]
selectionSort(arr)
print("Sorted array is:", arr)

Output:

Sorted array is: [10, 13, 14, 29, 37]

Java Example

Here's the Java code for implementing the Selection Sort algorithm:

Example:

public class SelectionSort {
    void selectionSort(int arr[]) {
        int n = arr.length;
        // One by one move boundary of unsorted subarray
        for (int i = 0; i < n-1; i++) {
            // Find the minimum element in unsorted array
            int minIndex = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

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

    public static void main(String args[]) {
        SelectionSort ob = new SelectionSort();
        int arr[] = {29, 10, 37, 14, 13};
        ob.selectionSort(arr);
        System.out.println("Sorted array is: ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Output:

Sorted array is: 10 13 14 29 37

Time Complexity

The time complexity of the Selection Sort algorithm is O(n^2) in both the best-case and worst-case scenarios. Like Bubble Sort, this quadratic complexity means that the time it takes to sort a list of elements increases significantly with the square of the number of elements. This behavior makes the Selection Sort inefficient for sorting large datasets compared to more advanced sorting algorithms that offer better time complexity.

Conclusion

Selection Sort is a simple yet effective sorting algorithm that is an excellent starting point for understanding how sorting works. Although it may not be the most efficient for large data sets, it's a great way to learn sorting algorithms because of its simplicity and clarity. This algorithm helps to understand fundamental concepts such as iteration and swapping, which are essential for many computer science algorithms.