**Selection Sort in Java**

Sorting algorithms are the backbone of many computational tasks, and understanding them is pivotal for any programmer. In this comprehensive guide, we’ll dive into the intricacies of Selection Sort, a simple yet foundational sorting algorithm, implemented in Java.

**Introduction to Selection Sort:**

Selection Sort is a simple, in-place comparison-based sorting algorithm. The idea behind this algorithm is to divide the array into two regions: the sorted and the unsorted. The sorted region starts as an empty set, and the unsorted region encompasses the entire array. In each iteration, the algorithm finds the minimum (or maximum) element in the unsorted region and swaps it with the first element of the unsorted region. This process continues until the entire array is sorted.

**Steps:**

**Initialization:**

- The array is divided into two regions: sorted and unsorted.
- Initially, the sorted region is empty, and the unsorted region includes the entire array.

**Selection:**

- Find the minimum element in the unsorted region.
- Swap the minimum element with the first element of the unsorted region.

**Expansion of Sorted Region:**

- The sorted region now includes the previously found minimum element.
- The unsorted region is reduced by one element.

**Repeat:**

- Repeat steps 2 and 3 until the entire array is sorted.
- In each iteration, the sorted region grows, and the unsorted region shrinks.

```
public static void selectionSort(int[] array) {
int n = array.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
}
```

let’s break down the `selectionSort`

method:

`int n = array.length;:`

`int n = array.length;:`

- Gets the length of the input array, representing the number of elements in the array.

**Outer Loop – **`for (int i = 0; i < n - 1; i++) {`

:

`for (int i = 0; i < n - 1; i++) {`

:- Iterates through the array from the beginning to the second-to-last element. It represents the boundary between the sorted and unsorted regions.

`int minIndex = i;:`

`int minIndex = i;:`

- Initializes
`minIndex`

to the current index`i`

, assuming that the current element is the minimum in the unsorted region.

**Inner Loop – **`for (int j = i + 1; j < n; j++) {`

:

`for (int j = i + 1; j < n; j++) {`

:- Searches for the minimum element in the unsorted region, starting from the next element after
`i`

.

`if (array[j] < array[minIndex]) { minIndex = j; }:`

`if (array[j] < array[minIndex]) { minIndex = j; }:`

- If an element smaller than the current assumed minimum is found, updates
`minIndex`

to the index of that smaller element.

**Swapping Elements – **`int temp = array[minIndex]; array[minIndex] = array[i]; array[i] = temp;`

:

`int temp = array[minIndex]; array[minIndex] = array[i]; array[i] = temp;`

:- After finding the minimum element in the unsorted region, it is swapped with the first element in the unsorted region (
`array[i]`

). This step brings the smallest element to its correct position.

**Java Implementation:**

```
public class SelectionSort {
public static void selectionSort(int[] array) {
int n = array.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first element of the unsorted region
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
}
public static void printArray(int[] array) {
for (int value : array) {
System.out.print(value + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] exampleArray = {5, 2, 9, 1, 5};
System.out.println("Original Array:");
printArray(exampleArray);
// Applying Selection Sort
selectionSort(exampleArray);
System.out.println("\nArray after Selection Sort:");
printArray(exampleArray);
}
}
```

**Explanation:**

- The outer loop iterates through the array, marking the boundary between the sorted and unsorted regions.
- The inner loop finds the minimum element in the unsorted region.
- The minimum element is swapped with the first element of the unsorted region, expanding the sorted region.
- This process is repeated until the entire array is sorted.

**Example:**

Let’s illustrate the Selection Sort process with a simple example. Consider the array `[5, 2, 9, 1, 5]`

. The algorithm proceeds as follows:

**Pass 1:**`[1, 2, 9, 5, 5]`

(Swapped 1 with 5)**Pass 2:**`[1, 2, 9, 5, 5]`

(No swap as 2 is already minimum)**Pass 3:**`[1, 2, 5, 9, 5]`

(Swapped 5 with 9)**Pass 4:**`[1, 2, 5, 5, 9]`

(Swapped 5 with 9)

The array is now sorted, demonstrating the algorithm’s efficiency in bringing the smallest elements to their correct positions.

**Output:**

```
Original Array:
5 2 9 1 5
Array after Selection Sort:
1 2 5 5 9
```

**Complexity Analysis:**

Here’s the time and space complexity of Selection Sort:

Case | Time Complexity | Space Complexity |
---|---|---|

Best | O(n^2) | O(1) |

Average | O(n^2) | O(1) |

Worst | O(n^2) | O(1) |

**Key Points:**

- Selection Sort is not suitable for large datasets due to its quadratic time complexity.
- It has a space complexity of O(1) since it sorts the array in-place.
- The algorithm is straightforward and easy to understand, making it useful for educational purposes.

**Conclusion:**

Selection Sort, despite its simplicity, has its place in understanding sorting algorithms. Its straightforward implementation serves as a valuable introduction to the principles of sorting. As you delve deeper into programming, mastering Selection Sort provides a solid foundation for comprehending more complex sorting strategies.

In this guide, we’ve explored the intricacies of Selection Sort, providing a clear understanding of its implementation in Java. Whether you’re a novice programmer or a seasoned coder, embracing the simplicity of Selection Sort contributes to a well-rounded understanding of algorithmic principles.

**Latest Posts:**

- Merging Two Sorted Arrays in JavaTitle: Merging Two Sorted Arrays in Java Merging two sorted arrays into a single array is a common operation in… Read more: Merging Two Sorted Arrays in Java
- Frequency of Elements in an ArrayTitle: Frequency of Elements in an Array Using Java Counting the frequency of elements in an array is a fundamental… Read more: Frequency of Elements in an Array
- Calculate the sum of diagonals in a matrixTitle: Calculate the sum of diagonals in a matrix In this blog post, we’ll delve into the world of matrices… Read more: Calculate the sum of diagonals in a matrix
- Binary Search in JavaBinary search is a powerful algorithm used to efficiently find a target value in a sorted array. In this blog… Read more: Binary Search in Java
- Removing Duplicate Elements in Array using JavaRemoving Duplicate Elements in Array using Java Arrays are fundamental in Java, but duplicate elements can clutter your data. In… Read more: Removing Duplicate Elements in Array using Java
- Transpose a 2D Array in JavaTitle: Transpose a 2D Array in Java In Java, transposing a 2D array involves converting its rows into columns and… Read more: Transpose a 2D Array in Java