Section 13.4 Selection Sort
The selection sort algorithm is a simple sorting algorithm that repeatedly selects the smallest (or largest) element from an unsorted portion of the sequence and moves it to the sorted portion. It works by iteratively building the sorted portion of the sequence from the beginning, effectively dividing the sequence into two parts: the sorted part and the unsorted part.
The selection sort algorithm works as follows.
- Input: The algorithm takes an unsorted collection or array of elements as input.
- Initialization: Start with the first element of the sequence as the current "minimum" or "maximum" value, depending on whether you’re sorting in ascending or descending order.
- Search for Minimum/Maximum: Iterate through the unsorted portion of the sequence, comparing each element with the current minimum/maximum value.
- Update Minimum/Maximum: If you find an element that is smaller (or larger, depending on the sorting order) than the current minimum/maximum value, update the current minimum/maximum value to the new element.
- Swap: After completing the iteration through the unsorted portion, swap the current minimum/maximum value with the first element in the unsorted portion. This effectively moves the smallest (or largest) element to its correct position in the sorted portion of the sequence.
- Repeat: Repeat steps 2 to 5, incrementing the starting position of the unsorted portion by one element each time. This process continues until the entire sequence is sorted.
- Termination: Once all elements are placed in their correct positions, the sorting is complete, and the sequence is now sorted in ascending (or descending) order.
The selection sort algorithm has a time complexity of \(O(N^2)\text{,}\) where \(N\) is the number of elements in the sequence. This is because, in each iteration, the algorithm searches through the remaining unsorted portion to find the minimum/maximum element and then performs a swap. Selection sort is not very efficient for large sequences. There are more efficient sorting algorithms like merge sort which has better average and worst-case time complexities.
While selection sort is not commonly used for large-scale sorting tasks due to its inefficiency, it’s easy to understand and implement, making it suitable for small sequences where efficiency is not a critical concern.
In Listing 13.4.1, the
selectionSort(…) function takes an array (arr) as a parameter and sorts it using the selection sort algorithm. The main method demonstrates how to use the selection sort function on an array. The selection sort algorithm repeatedly finds the minimum element from the unsorted portion and swaps it with the current element, effectively building the sorted portion of the array.After sorting, the output will display the original array and the sorted array.
// SelectionSort.java
import java.util.Arrays;
public class SelectionSort {
// Selection sort function
static void selectionSort(int[] arr) {
int N = arr.length;
for (int i = 0; i < N - 1; i++) {
int minIndex = i;
// Find the index of the minimum element in the unsorted portion
for (int j = i + 1; j < N; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the minimum element with the current element
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
public static void main(String[] args) {
int[] arrayToSort = { 64, 25, 12, 22, 11 };
System.out.println("Original array: " + Arrays.toString(arrayToSort));
selectionSort(arrayToSort);
System.out.println("Sorted array: " + Arrays.toString(arrayToSort));
}
}
SelectionSort.javajavac SelectionSort.java java SelectionSort Original array: [64, 25, 12, 22, 11] Sorted array: [11, 12, 22, 25, 64]
