Algorithms — Selection Sort

Summary

The Selection Sort Algorithm is an efficient sorting algorithm that repeatedly selects the smallest (or largest) element of an array and moves it to another array.

This algorithm consists of two subarrays throughout the process, the unsorted subarray, which decreases in size with every pass, and the sorted subarray, which increases in size with every pass. With every pass, the smallest element from the unsorted subarray is moved to the beginning of the sorted subarray.

Complexity

The Time Complexity of this algorithm is Quadratic Time, O(n²), which correlates with the squared number of the input size.

A time complexity like this usually means there are nested loops involved, which the Selection Sort Algorithm certainly has. It must iterate through the unsorted subarray until it determines the smallest element, then moves that item to the sorted subarray. The process then repeats itself until the unsorted subarray is empty.

Example

First, let’s walk through the steps of this algorithm.

1. Initialize with minimum element set to 0 (minIndex)
2. Iterate through the unsorted subarray to find the smallest element
3. While iterating, if any element is smaller than minIndex, swap the two elements
4. Then, increment minIndex to point to the next element
5. Repeat until the array is sorted

Let’s take a look at the Selection Sort Algorithm in action. Here is an example in Java:

public class SelectionSort {

    void sort(int arr[]){

        // Iterate through the unsorted list
        for (int i = 0; i < arr.length-1; i++) {

            // Find the minimum element in unsorted array
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

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

    void printArray(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+ " ");
            System.out.println();
        }
    }

    public static void main(String[] args) {
        SelectionSort ex = new SelectionSort();
        int arr[] = {43, 45, 1, 23, 29, 36, 14, 18, 41};
        ex.sort(arr);
        System.out.println("Sorted Array");
        ex.printArray(arr);
    }

}

Conclusion

The Selection Sort Algorithm repeately takes the smallest element from the unsorted subarray, and moves it to the beginning of the sorted subarray. This algorithm is efficient when working with smaller data sets, with a time complexity of O(n²) (Quadratic Time). Overall, the Selection Sort algorithm is a strong, fundamental algorithm that develops understanding of nested loops and swapping elements in arrays. It is an essential stepping stone in becoming a Software Engineer, and I hope you learned something new. Keep learning, and happy coding!