Selection Sort

Selection Sort is a simple comparison-based sorting algorithm. It works by dividing the input list into two parts: the sorted part and the unsorted part. Initially, the sorted part is empty, and the unsorted part contains all the elements. The algorithm repeatedly selects the smallest element from the unsorted part and moves it to the sorted part.

Steps of Selection Sort

1. Find the minimum element in the unsorted part.
2. Swap the minimum element with the first element of the unsorted part.
3. Increment the boundary of the sorted part.
4. Repeat steps 1-3 until the entire array is sorted.

Time Complexity

The time complexity of Selection Sort is O(n^2) in all cases, where n is the number of elements in the array. This is because the algorithm involves two nested loops, resulting in quadratic time complexity. Selection Sort is not efficient for large data sets.

Example

Let's see an implementation of Selection Sort in Java:

1${code}

xxxxxxxxxx

}

public class SelectionSort {

​

    public static void selectionSort(int[] arr) {

        int n = arr.length;

        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;

                }

            }

            int temp = arr[minIndex];

            arr[minIndex] = arr[i];

            arr[i] = temp;

        }

    }

​

    public static 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) {

        int[] arr = {64, 25, 12, 22, 11};

        System.out.println("Array before sorting:");

        printArray(arr);

        selectionSort(arr);