Selection Sort in Java

Selection sort is an algorithm used to sort an array of items. It is a comparison-based sorting algorithm, which works by repeatedly finding the smallest element from the unsorted part of the array and placing it at the beginning of the array. Selection sort is an in-place sorting algorithm, meaning it does not require any extra space to perform the sorting operation. This makes it a very efficient sorting algorithm and has a time complexity of O(n2).

Overview of Selection Sort

Selection sort is an algorithm for sorting an array of items. It works by repeatedly finding the smallest element from the unsorted part of the array and placing it at the beginning of the array. This process is repeated until all the elements in the array are sorted. Selection sort is an in-place sorting algorithm, meaning it does not require any extra space to perform the sorting operation.

How Selection Sort Works

Selection sort works by repeatedly finding the smallest element from the unsorted part of the array and placing it at the beginning of the array. This is done by comparing the elements of the array one by one and keeping track of the smallest element. Once the smallest element is found, it is swapped with the first element in the array. This process is repeated until all the elements in the array are sorted.

The following is a step-by-step example of how selection sort works:

1. Start with an unsorted array of elements.
2. Find the smallest element in the array and swap it with the first element.
3. Find the second smallest element in the array and swap it with the second element.
4. Continue this process until all the elements in the array have been sorted.

Java Code for Selection Sort

The following is a Java code example for selection sort:

public static void selectionSort(int[] array) {
    
    // Iterate through the array
    for (int i = 0; i < array.length - 1; i++) {
        // Find the index of the smallest element
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the smallest element with the first element
        int temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}

Time Complexity of Selection Sort

The time complexity of selection sort is O(n2). This is because the algorithm needs to compare each element in the array with all the other elements in the array.

The average time complexity for access, search, insertion and deletion operations in selection sort is also O(n2).

Space Complexity of Selection Sort

The space complexity of selection sort is O(1). This is because the algorithm does not require any extra space to perform the sorting operation.

Conclusion

In conclusion, selection sort is an in-place sorting algorithm which has a time complexity of O(n2) and a space complexity of O(1). It works by repeatedly finding the smallest element from the unsorted part of the array and placing it at the beginning of the array.

Exercises

public static void selectionSort(int[] array) {
    
    // Iterate through the array
    for (int i = 0; i < array.length - 1; i++) {
        // Find the index of the smallest element
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the smallest element with the first element
        int temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}

public static void selectionSort(String[] array) {
    
    // Iterate through the array
    for (int i = 0; i < array.length - 1; i++) {
        // Find the index of the smallest element
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[j].compareTo(array[minIndex]) < 0) {
                minIndex = j;
            }
        }
        // Swap the smallest element with the first element
        String temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}

public static void selectionSort(double[] array) {
    
    // Iterate through the array
    for (int i = 0; i < array.length - 1; i++) {
        // Find the index of the smallest element
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the smallest element with the first element
        double temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}

public static <T extends Comparable<T>> void selectionSort(T[] array) {
    
    // Iterate through the array
    for (int i = 0; i < array.length - 1; i++) {
        // Find the index of the smallest element
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[j].compareTo(array[minIndex]) < 0) {
                minIndex = j;
            }
        }
        // Swap the smallest element with the first element
        T temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}

public static void selectionSort(char[] array) {
    
    // Iterate through the array
    for (int i = 0; i < array.length - 1; i++) {
        // Find the index of the smallest element
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the smallest element with the first element
        char temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}