Implementation of Selection Sort Algorithm in Java

Selection sort is a simple sorting algorithm that works by repeatedly picking the smallest element from a list and moving it to the beginning of unsorted portion of the list. In this article, we’ll explore how to implement this algorithm in Java. We’ll start with a simple implementation and then look at some practical variations, like sorting in descending order and sorting custom objects.

Prerequisites:

Basic Selection Sort Implementation

Let’s begin with a basic version of the selection sort algorithm. This code will sort an array of numbers in ascending order. We’ll go through each step, so it’s easy to follow, even if you’re just starting out with Java.

public class SelectionSort {
  public static void selectionSort(int[] arr) {
    // `arr`: This is the array you want to sort
    int n = arr.length;
    // `n`: This variable stores the number of items in the array

    // We go through each item in the array, except the last one
    // The outer loop iterates from the first element (`0`) to the second-to-last element (`n - 2`).
    for (int i = 0; i < n - 1; i++) {
      // Let's say the current item is the smallest
      // `min_index`: This will hold the index of the smallest item we find
      int minIndex = i;

      // Now, check the rest of the array to find a smaller item
      // The inner loop iterates through the unsorted portion of the array,
      // starting from the element next to the current one (`i + 1`) to the last element (`n - 1`).
      for (int j = i + 1; j < n; j++) {
        // If we find a smaller item
        if (arr[j] < arr[minIndex]) {
          // Update the index of the smallest item
          minIndex = j;
        }
      }

      // If the smallest item is not the current item, swap them
      if (minIndex != i) {
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
      }
    }
    // Now the array is sorted!
  }

  // Utility method to print array
  public static void printArray(int[] arr) {
    for (int num : arr) {
      System.out.print(num + " ");
    }
    System.out.println();
  }

  public static void main(String[] args) {
    // Let's create an array
    int[] arr = {64, 25, 12, 22, 11};
    System.out.print("Original array: ");
    printArray(arr);

    // Sort the array using selection sort
    selectionSort(arr);

    // Print the sorted array
    System.out.print("Sorted array: ");
    printArray(arr);
  }
}

Let’s break down this code step by step:

  1. Outer Loop: The outer loop for (int i = 0; i < n - 1; i++) goes through each element in the array, except the last one. In each iteration, we assume that the current element at index i is the smallest in the unsorted part of the array. We stop at n - 2 because the last element will automatically be in its correct position after the n - 1 element is sorted.
  2. Inner Loop: The inner loop for (int j = i + 1; j < n; j++) checks the rest of the array to find a smaller element. If it finds one (if (arr[j] < arr[minIndex])), it updates the index of the smallest element (minIndex = j).
  3. Swapping: After the inner loop, we check if the smallest element is not the current element (if (minIndex != i)). If they are different, we swap the current element with the smallest element. This puts the smallest element in its correct position.

Sorting in Descending Order

What if we want to sort the array in descending order (from largest to smallest)? We just need to make a small change in the comparison within the inner loop. Here’s how:

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

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

      for (int j = i + 1; j < n; j++) {
        // If we find a larger item
        if (arr[j] > arr[maxIndex]) { // Note the change here: `>` instead of `<`
          // Update the index of the largest item
          maxIndex = j;
        }
      }

      if (maxIndex != i) {
        int temp = arr[i];
        arr[i] = arr[maxIndex];
        arr[maxIndex] = temp;
      }
    }
  }

  // Utility method to print array
  public static void printArray(int[] arr) {
    for (int num : arr) {
      System.out.print(num + " ");
    }
    System.out.println();
  }

  public static void main(String[] args) {
    // Let's create an array
    int[] arr = {64, 25, 12, 22, 11};
    System.out.print("Original array: ");
    printArray(arr);

    // Sort the array in descending order using selection sort
    selectionSortDescending(arr);

    // Print the sorted array
    System.out.print("Sorted array (descending): ");
    printArray(arr);
  }
}

The only difference is in the if condition inside the inner loop: if (arr[j] > arr[maxIndex]). This change makes the function find the largest element instead of the smallest.

Sorting Custom Objects

Selection sort isn’t just for numbers; it can also sort custom objects. Suppose you have an array of objects, each representing a person with a name and an age. You can sort this array based on either the name or the age. Let’s see how to do it.

import java.util.Comparator;

public class SelectionSortCustom {

  static class Person {
    String name;
    int age;

    public Person(String name, int age) {
      this.name = name;
      this.age = age;
    }

    public String getName() {
      return name;
    }

    public int getAge() {
      return age;
    }

    @Override
    public String toString() {
      return "Person{" +
          "name='" + name + '\'' +
          ", age=" + age +
          '}';
    }
  }

  public static void selectionSortCustom(Person[] arr, Comparator<Person> comparator) {
    int n = arr.length;

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

      for (int j = i + 1; j < n; j++) {
        // Use the comparator to compare
        if (comparator.compare(arr[j], arr[minIndex]) < 0) {
          minIndex = j;
        }
      }

      if (minIndex != i) {
        Person temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
      }
    }
  }

  // Utility method to print Person array
  public static void printPersonArray(Person[] arr) {
    for (Person person : arr) {
      System.out.println(person);
    }
  }


  public static void main(String[] args) {
    // Let's create an array of Person objects
    Person[] people = {
        new Person("Alice", 30),
        new Person("Bob", 25),
        new Person("Charlie", 35)
    };

    // Sort by age
    System.out.println("Sorted by age:");
    selectionSortCustom(people, Comparator.comparingInt(Person::getAge));
    printPersonArray(people);

    // Sort by name
    System.out.println("\nSorted by name:");
    selectionSortCustom(people, Comparator.comparing(Person::getName));
    printPersonArray(people);
  }
}

In this example, the selectionSortCustom function takes an additional Comparator<Person> argument. This Comparator tells the sort function how to compare the objects.

  • Sorting by Age: When sorting by age, Comparator.comparingInt(Person::getAge) tells the function to use the age value of each Person object for comparison.
  • Sorting by Name: Similarly, when sorting by name, Comparator.comparing(Person::getName) tells the function to use the name value for comparison.

This approach makes selection sort very flexible, allowing you to sort arrays of any type of objects based on any criteria you define. Just pass the appropriate Comparator.

What’s Next?

Now that you’ve learned how to implement selection sort in Java, you can explore further: