public class SelectionSortableListOfInts {
    
    private class Node {  // quick and dirty nodes for list of ints (not generic)
        int num;
        Node next;
    }
    
    Node head;
    
    public void fillWithRandomInts(int count, int max) {  // for quick construction during testing later
        for (int i = 0; i < count; i++) {
            Node n = new Node();
            n.num = (int) (max*Math.random()) + 1;  // assigns to num a random int from 1 to max
            n.next = head;
            head = n;
        }
    }
    
    public String toString() { // for debugging later
        if (head == null) {
            return "empty list";
        }
        String s = "";
        for (Node n = head; n != null; n = n.next) {
            s += n.num + "->";
        }
        return s;
    }
    
    private void exch(Node n, Node m) {  //swaps items inside nodes n and m (not pointers)
        int tmp = n.num;
        n.num = m.num;
        m.num = tmp;
    }
    
    public void selectionSort() {  // i.e., repeatedly traverse list to find min, 
                                   // and then swap it with head
        for (Node n = head; n != null; n = n.next) {
            Node minNode = n;
            for (Node m = n.next; m != null; m = m.next) {
                if (m.num < minNode.num) {
                    minNode = m;
                }
            }
            exch(n,minNode); 
            System.out.println(this); // see state of array after each exchange
        }
    }
    
    public void sort() {  // public facing, to hide implementation and kick off recursion
        head = selectionSortR(head);
    }
    
    private Node selectionSortR(Node h) { // sort sublist "headed" by h
        if (h == null) return null; // base case
        Node minNode = h;
        for (Node n = h.next; n != null; n = n.next) {
            if (n.num < minNode.num) {
                minNode = n;
            }
        }
        exch(h,minNode);
        h.next = selectionSortR(h.next);
        return h;
    }
    
    public static void main(String[] args) {  // for testing
        SelectionSortableListOfInts list = new SelectionSortableListOfInts();
        list.fillWithRandomInts(25,10);
        System.out.println(list);
        list.sort();
        System.out.println(list);
    }
}