Selection Sort in Java

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;:

• 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++) {:

• 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;:

• 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++) {:

• Searches for the minimum element in the unsorted region, starting from the next element after i.

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;:

• 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:

1. Pass 1: [1, 2, 9, 5, 5] (Swapped 1 with 5)
2. Pass 2: [1, 2, 9, 5, 5] (No swap as 2 is already minimum)
3. Pass 3: [1, 2, 5, 9, 5] (Swapped 5 with 9)
4. 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:

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:

• Find Longest Subarray with Sum Divisible by K
  Title: Find Longest Subarray with Sum Divisible by K In this guide, you’ll learn how to find the longest subarray… Read more: Find Longest Subarray with Sum Divisible by K
• Find Longest Subarray with Equal Zeros and Ones
  Title: Find Longest Subarray with Equal Zeros and Ones In this guide, you’ll learn how to find the length of… Read more: Find Longest Subarray with Equal Zeros and Ones
• Find All Subarrays with a Given Sum
  Title: Find All Subarrays with a Given Sum Given an array of integers and a target sum, the task is… Read more: Find All Subarrays with a Given Sum
• Find All Subarrays with Zero Sum
  Title: Find All Subarrays with Zero Sum In this guide, you’ll learn how to find every contiguous subarray of an… Read more: Find All Subarrays with Zero Sum
• Find Minimum Sum Subarray
  Title: Find Minimum Sum Subarray In this guide, you’ll learn how to find the minimum sum subarray in an array… Read more: Find Minimum Sum Subarray
• Find Maximum Sum Subarray using Kadane’s Algorithm
  Title: Find Maximum Sum Subarray using Kadane’s Algorithm Finding the contiguous subarray with the largest sum is one of the… Read more: Find Maximum Sum Subarray using Kadane’s Algorithm