WikiGalaxy
Selection Sort Algorithm
Understanding Selection Sort
Introduction:
Selection sort is a simple comparison-based sorting algorithm. It divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list.
How It Works:
The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element, and moving the sublist boundaries one element to the right.
Example 1: Sorting an Array of Integers
Code Explanation:
The following code demonstrates how to use the selection sort algorithm to sort an array of integers in ascending order.
public class SelectionSort {
public static void main(String[] args) {
int[] arr = {29, 10, 14, 37, 13};
selectionSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
Console Output:
10 13 14 29 37
Example 2: Sorting an Array of Strings
Code Explanation:
Here, we modify the selection sort to sort an array of strings alphabetically.
public class StringSelectionSort {
public static void main(String[] args) {
String[] arr = {"banana", "apple", "cherry", "date"};
selectionSort(arr);
for (String fruit : arr) {
System.out.print(fruit + " ");
}
}
public static void selectionSort(String[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j].compareTo(arr[minIndex]) < 0) {
minIndex = j;
}
}
String temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
Console Output:
apple banana cherry date
Example 3: Sorting an Array in Descending Order
Code Explanation:
This example demonstrates how to modify the selection sort algorithm to sort an array of integers in descending order.
public class DescendingSelectionSort {
public static void main(String[] args) {
int[] arr = {5, 3, 8, 6, 2};
selectionSortDescending(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
public static void selectionSortDescending(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int maxIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] > arr[maxIndex]) {
maxIndex = j;
}
}
int temp = arr[maxIndex];
arr[maxIndex] = arr[i];
arr[i] = temp;
}
}
}
Console Output:
8 6 5 3 2
Example 4: Sorting with a Comparator
Code Explanation:
In this example, we sort an array of integers using a custom comparator to determine the order of sorting.
import java.util.Comparator;
public class ComparatorSelectionSort {
public static void main(String[] args) {
Integer[] arr = {7, 2, 9, 4, 1};
selectionSort(arr, Comparator.reverseOrder());
for (int num : arr) {
System.out.print(num + " ");
}
}
public static void selectionSort(T[] arr, Comparator cmp) {
for (int i = 0; i < arr.length - 1; i++) {
int selectedIdx = i;
for (int j = i + 1; j < arr.length; j++) {
if (cmp.compare(arr[j], arr[selectedIdx]) < 0) {
selectedIdx = j;
}
}
T temp = arr[selectedIdx];
arr[selectedIdx] = arr[i];
arr[i] = temp;
}
}
}
Console Output:
9 7 4 2 1
Example 5: Sorting Objects by a Property
Code Explanation:
In this example, we sort an array of custom objects based on a specific property using the selection sort algorithm.
class Person {
String name;
int age;
Person(String name, int age) {
this.name = name;
this.age = age;
}
}
public class ObjectSelectionSort {
public static void main(String[] args) {
Person[] people = {
new Person("Alice", 30),
new Person("Bob", 25),
new Person("Charlie", 35)
};
selectionSort(people);
for (Person person : people) {
System.out.println(person.name + " " + person.age);
}
}
public static void selectionSort(Person[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j].age < arr[minIndex].age) {
minIndex = j;
}
}
Person temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
Console Output:
Bob 25\nAlice 30\nCharlie 35
