Common Algorithms
Selection Sort
Selection sort scans the unsorted portion of an array, selects the smallest value, and moves it into the next sorted position. It is easy to reason about and uses few swaps.
Basic Implementation
Basic.java
public class Basic {
static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
public static void main(String[] args) {
int[] numbers = {64, 25, 12, 22, 11};
System.out.println("Before: " + java.util.Arrays.toString(numbers));
selectionSort(numbers);
System.out.println("After: " + java.util.Arrays.toString(numbers));
}
}
Selection Sort
A sorting algorithm that repeatedly selects the minimum element from the unsorted portion and places it at the end of the sorted portion.
Tracing the Algorithm
Each pass finds one minimum value and grows the sorted prefix by one position.
Trace.java
public class Trace {
static void selectionSortTrace(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
System.out.println("Pass " + (i + 1) + ":");
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
System.out.printf(" Min in unsorted portion: %d at index %d%n",
arr[minIndex], minIndex);
if (minIndex != i) {
System.out.printf(" Swap positions %d and %d%n", i, minIndex);
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
} else {
System.out.println(" Already in position");
}
System.out.println(" Result: " + java.util.Arrays.toString(arr));
}
}
public static void main(String[] args) {
int[] numbers = ;
System.out.println("Initial: " + java.util.Arrays.toString(numbers));
System.out.println();
selectionSortTrace(numbers);
}
}
public class Trace {
static void selectionSortTrace(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
System.out.println("Pass " + (i + 1) + ":");
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
System.out.printf(" Min in unsorted portion: %d at index %d%n",
arr[minIndex], minIndex);
if (minIndex != i) {
System.out.printf(" Swap positions %d and %d%n", i, minIndex);
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
} else {
System.out.println(" Already in position");
}
System.out.println(" Result: " + java.util.Arrays.toString(arr));
}
}
public static void main(String[] args) {
int[] numbers = ;
System.out.println("Initial: " + java.util.Arrays.toString(numbers));
System.out.println();
selectionSortTrace(numbers);
}
}
public class Trace {
static void selectionSortTrace(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
System.out.println("Pass " + (i + 1) + ":");
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
System.out.printf(" Min in unsorted portion: %d at index %d%n",
arr[minIndex], minIndex);
if (minIndex != i) {
System.out.printf(" Swap positions %d and %d%n", i, minIndex);
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
} else {
System.out.println(" Already in position");
}
System.out.println(" Result: " + java.util.Arrays.toString(arr));
}
}
public static void main(String[] args) {
int[] numbers = ;
System.out.println("Initial: " + java.util.Arrays.toString(numbers));
System.out.println();
selectionSortTrace(numbers);
}
}
Finding Maximum Instead
Selection sort can work from the opposite end by selecting the maximum value.
FindMax.java
public class FindMax {
static void selectionSortMax(int[] arr) {
int n = arr.length;
for (int i = n - 1; i > 0; i--) {
int maxIndex = 0;
for (int j = 1; j <= i; j++) {
if (arr[j] > arr[maxIndex]) {
maxIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[maxIndex];
arr[maxIndex] = temp;
}
}
public static void main(String[] args) {
int[] numbers = {64, 25, 12, 22, 11};
System.out.println("Before: " + java.util.Arrays.toString(numbers));
selectionSortMax(numbers);
System.out.println("After: " + java.util.Arrays.toString(numbers));
}
}
Counting Operations
Selection sort performs a predictable number of comparisons and relatively few swaps.
Count.java
public class Count {
static class SortStats {
int comparisons;
int swaps;
SortStats(int comparisons, int swaps) {
this.comparisons = comparisons;
this.swaps = swaps;
}
}
static SortStats selectionSortCounted(int[] arr) {
int n = arr.length;
int comparisons = 0;
int swaps = 0;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
comparisons++;
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
swaps++;
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
return new SortStats(comparisons, swaps);
}
public static void main(String[] args) {
int[] sorted = {1, 2, 3, 4, 5};
int[] reversed = {5, 4, 3, 2, 1};
int[] random = {3, 1, 4, 2, 5};
var stats1 = selectionSortCounted(sorted.clone());
System.out.println("Already sorted: " + stats1.comparisons +
" comparisons, " + stats1.swaps + " swaps");
var stats2 = selectionSortCounted(reversed.clone());
System.out.println("Reverse sorted: " + stats2.comparisons +
" comparisons, " + stats2.swaps + " swaps");
var stats3 = selectionSortCounted(random.clone());
System.out.println("Random order: " + stats3.comparisons +
" comparisons, " + stats3.swaps + " swaps");
}
}
Comparison with Bubble Sort
Compare.java
public class Compare {
static int bubbleSortSwaps(int[] arr) {
int n = arr.length;
int swaps = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swaps++;
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return swaps;
}
static int selectionSortSwaps(int[] arr) {
int n = arr.length;
int swaps = 0;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
swaps++;
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
return swaps;
}
public static void main(String[] args) {
int[] reversed = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
int bubbleSwaps = bubbleSortSwaps(reversed.clone());
System.out.println("Bubble sort swaps: " + bubbleSwaps);
int selectionSwaps = selectionSortSwaps(reversed.clone());
System.out.println("Selection sort swaps: " + selectionSwaps);
System.out.println("\nSelection sort makes fewer swaps!");
}
}
Swap Efficiency
Selection sort usually performs fewer swaps than bubble sort, which matters when writes are expensive.
Custom Criteria
The same selection pattern works with strings and custom comparison rules.
Practical.java
public class Practical {
static void selectionSortByLength(String[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j].length() < arr[minIndex].length()) {
minIndex = j;
}
}
String temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
static void selectionSortAlphabetic(String[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j].compareTo(arr[minIndex]) < 0) {
minIndex = j;
}
}
String temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
public static void main(String[] args) {
String[] words1 = {"elephant", "cat", "dog", "butterfly", "ant"};
String[] words2 = {"zebra", "apple", "mango", "cherry", "banana"};
System.out.println("Sort by length:");
System.out.println("Before: " + java.util.Arrays.toString(words1));
selectionSortByLength(words1);
System.out.println("After: " + java.util.Arrays.toString(words1));
System.out.println("\nSort alphabetically:");
System.out.println("Before: " + java.util.Arrays.toString(words2));
selectionSortAlphabetic(words2);
System.out.println("After: " + java.util.Arrays.toString(words2));
}
}
Exercise: Practical.java
Implement selection sort that sorts in descending order