Java Interview Question: How to Implement Selection Sort in Java?

Introduction:

Sorting is an important operation in computer science that arranges data in a specific order. There are various sorting algorithms, and one popular algorithm is Selection Sort. It is a simple and intuitive algorithm that sorts an array by repeatedly finding the minimum element and swapping it with the current element.

Problem Statement:

Given an unsorted array, how can we implement Selection Sort in Java to sort the elements in ascending order?

Use Case:

Let’s consider a use case scenario where we have an array of integers [5, 2, 8, 3, 1] that needs to be sorted in ascending order using the Selection Sort algorithm.

Solution:

To implement Selection Sort in Java, we can follow the following steps:

1. Find the minimum element in the unsorted part of the array.
2. Swap the minimum element with the current element.
3. Repeat steps 1 and 2 until the entire array is sorted.

Here is a Java implementation of the Selection Sort algorithm:

public class SelectionSort {
  public static void selectionSort(int[] arr) {
    int n = arr.length;

    // One by one move the boundary of unsorted subarray
    for (int i = 0; i < n-1; i++) {
      // Find the minimum element in unsorted array
      int minIndex = i;
      for (int j = i+1; j < n; j++) {
        if (arr[j] < arr[minIndex]) {
          minIndex = j;
        }
      }

      // Swap the found minimum element with the first element
      int temp = arr[minIndex];
      arr[minIndex] = arr[i];
      arr[i] = temp;
    }
  }

  public static void main(String[] args) {
    int[] arr = {5, 2, 8, 3, 1};
    selectionSort(arr);
    System.out.println("Sorted array:");
    for (int num : arr) {
      System.out.print(num + " ");
    }
  }
}

Explanation:

In the above implementation, we start by assuming the first element of the unsorted array as the minimum element. We then iterate through the rest of the unsorted array to find the minimum element. If a smaller element is found, we update the index of the minimum element. Finally, we swap the minimum element with the current element.

By repeating these steps for the entire array, we gradually sort the array in ascending order.

Complexity Analysis:

The time complexity of the Selection Sort algorithm is O(n^2), where n is the number of elements in the array. This is because we have nested loops, where the outer loop runs n-1 times and the inner loop runs n-i times (where i is the current iteration of the outer loop).

The space complexity of the algorithm is O(1) because it does not require any additional space, apart from the input array.

Conclusion:

In this article, we have discussed how to implement the Selection Sort algorithm in Java. We have also provided a code example and explained the working principle of Selection Sort.

Selection Sort may not be the most efficient sorting algorithm for large datasets, but it is a good algorithm to understand and implement as a beginner. It can be a common question in Java interviews, and understanding its logic and implementation will help you in coding interviews and improve your overall knowledge of sorting algorithms.