Selection Sort in Java

By
Shivam Gupta
-
33
Selection Sort in Java
Advertisement

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.
Code – Selection Sort
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:

Java Program – Selection Sort
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:

Output – Selection Sort
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:

CaseTime ComplexitySpace Complexity
BestO(n^2)O(1)
AverageO(n^2)O(1)
WorstO(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:

RELATED ARTICLESMORE FROM AUTHOR