Card 05/ 11
Selection Sort in Python, Java and TypeScript
Selection sort, printing its comparisons and swaps on sorted and reversed input.
Selection sort is two nested loops and one swap in each language: the inner loop finds the index of the smallest unsorted item, and the swap moves it to the front of the unsorted part. The listings count comparisons and swaps on 1 to 7 already sorted and on 7 to 1 reversed, the two inputs furthest apart, to show which count depends on the input and which does not.
Selection sort on sorted and reversed input, in each language
def selection_sort(items: list[int]) -> tuple[int, int]:
comparisons = swaps = 0
n = len(items)
for i in range(n - 1):
smallest = i
for j in range(i + 1, n):
comparisons += 1
if items[j] < items[smallest]:
smallest = j
if smallest != i:
items[i], items[smallest] = items[smallest], items[i]
swaps += 1
return comparisons, swaps
for numbers in ([1, 2, 3, 4, 5, 6, 7], [7, 6, 5, 4, 3, 2, 1]):
before = " ".join(map(str, numbers))
comparisons, swaps = selection_sort(numbers)
after = " ".join(map(str, numbers))
print(f"{before} -> {after}: {comparisons} comparisons, {swaps} swaps")1 2 3 4 5 6 7 -> 1 2 3 4 5 6 7: 21 comparisons, 0 swaps
7 6 5 4 3 2 1 -> 1 2 3 4 5 6 7: 21 comparisons, 3 swapsimport java.util.Arrays;
import java.util.stream.Collectors;
public class SelectionSortCode {
record Counts(int comparisons, int swaps) {}
static Counts selectionSort(int[] items) {
int comparisons = 0;
int swaps = 0;
int n = items.length;
for (int i = 0; i < n - 1; i++) {
int smallest = i;
for (int j = i + 1; j < n; j++) {
comparisons++;
if (items[j] < items[smallest]) {
smallest = j;
}
}
if (smallest != i) {
int held = items[i];
items[i] = items[smallest];
items[smallest] = held;
swaps++;
}
}
return new Counts(comparisons, swaps);
}
static String joined(int[] items) {
return Arrays.stream(items).mapToObj(String::valueOf).collect(Collectors.joining(" "));
}
public static void main(String[] args) {
int[][] inputs = {{1, 2, 3, 4, 5, 6, 7}, {7, 6, 5, 4, 3, 2, 1}};
for (int[] numbers : inputs) {
String before = joined(numbers);
Counts counts = selectionSort(numbers);
System.out.println(before + " -> " + joined(numbers) + ": "
+ counts.comparisons() + " comparisons, " + counts.swaps() + " swaps");
}
}
}1 2 3 4 5 6 7 -> 1 2 3 4 5 6 7: 21 comparisons, 0 swaps
7 6 5 4 3 2 1 -> 1 2 3 4 5 6 7: 21 comparisons, 3 swapsinterface Counts {
comparisons: number;
swaps: number;
}
function selectionSort(items: number[]): Counts {
let comparisons = 0;
let swaps = 0;
const n = items.length;
for (let i = 0; i < n - 1; i++) {
let smallest = i;
for (let j = i + 1; j < n; j++) {
comparisons++;
if (items[j] < items[smallest]) {
smallest = j;
}
}
if (smallest !== i) {
[items[i], items[smallest]] = [items[smallest], items[i]];
swaps++;
}
}
return { comparisons, swaps };
}
const inputs: number[][] = [[1, 2, 3, 4, 5, 6, 7], [7, 6, 5, 4, 3, 2, 1]];
for (const numbers of inputs) {
const before = numbers.join(" ");
const { comparisons, swaps } = selectionSort(numbers);
console.log(`${before} -> ${numbers.join(" ")}: ${comparisons} comparisons, ${swaps} swaps`);
}1 2 3 4 5 6 7 -> 1 2 3 4 5 6 7: 21 comparisons, 0 swaps
7 6 5 4 3 2 1 -> 1 2 3 4 5 6 7: 21 comparisons, 3 swapsAll three printed 21 comparisons on both inputs, n(n − 1)/2 for seven items: the inner loop always runs from i + 1 to the end, and nothing in it can cut that short. Only the swaps changed. Sorted input needs none, because the test smallest != i skips a swap of an item with itself. Reversed input needs three: the first pass swaps 7 and 1, which places both, the next two passes do the same for 6 and 2 and for 5 and 3, and 4 is left in the middle, already in place. The comparison is a strict less-than, so among equal minimums the scan keeps the first one it met.
No standard library sorts with selection sort; Python's sorted, Java's Arrays.sort and TypeScript's sort are all O(n log n). The cost lies in the scan, which reads every unsorted item to find one minimum. Heapsort, a later topic, keeps the unsorted part in a heap instead, so the next item to place comes out in O(log n) and the whole sort in O(n log n).
← → move through sections and cards