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:

- Start with an unsorted array of elements.
- Find the smallest element in the array and swap it with the first element.
- Find the second smallest element in the array and swap it with the second element.
- 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

#### Write a Java program to sort an array of integers using 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;
}
}
```

#### Write a Java program to sort an array of strings using selection sort.

```
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;
}
}
```

#### Write a Java program to sort an array of doubles using selection sort.

```
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;
}
}
```

#### Write a Java program to sort an array of objects using selection sort.

```
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;
}
}
```

#### Write a Java program to sort an array of characters using selection sort.

```
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;
}
}
```