O(n^2) Sorting Benchmarks

SelectionSort.java

zpackage sort;

public class SelectionSort> {

    // 1. Find the minimum value in the unsorted subarray
    // 2. Swap the found value with the value at the first
    //    position in the unsorted subarray
    // 3. Continue until the unsorted subarray is empty

    public void selectionSort(T[] arr){
        for (int i = 0; i < arr.length; i++){

            // Find the minimum value in the unsorted subarray
            // i ----> end
            int minIndex = i;
            for (int j = i; j < arr.length; j++){
                //if (arr[minIndex] > arr[j])
                if (arr[minIndex].compareTo(arr[j]) > 0)
                    minIndex = j;
            }

            T temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

LinkedList.java [InsertionSort version]

package sort;

import java.util.Random;
import java.util.stream.Collectors;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class LinkedList> {
    
    private class Node> {
        T data;
        Node next;
 
        public Node(T data){
            this.data = data;
        }
 
        public Node(T data, Node next){
            this(data);
            this.next = next;
        }
 
        public String toString(){
            return "" + data;
        }
    }
 
    private Node head;
    private int count;
 
    public LinkedList(){
        head = null;
        count = 0;
    }
 
    public LinkedList(T d){
        head = new Node(d);
        count = 1;
    }
 
    public int length() {
        return count;
    }
 
    public boolean isEmpty(){
        return head == null;
    }

    public void clear(){
        head = null;
        count = 0;
    }

    public void prepend(T d){
        head = new Node(d, head);
        count++;
    }

    public void insertionSort(){
        Node tempHead = head;
        head = null;
        count = 0;
        while ( tempHead != null) {
            sortedInsert(tempHead.data);
            tempHead = tempHead.next;
        }
    }

    private void sortedInsert(T d){
        if (head == null || d.compareTo(head.data) < 0)
            head = new Node(d, head);
        else {
            Node curr = head;
            for ( ; curr.next != null && (d.compareTo(curr.next.data) > 0) ; curr = curr.next);
            curr.next = new Node(d, curr.next);
        }
        count++;
    }
    
    @Override
    public String toString(){
        String retVal = "Linked List with " + count + " nodes: ";
 
        for (Node temp = head ; temp != null ; temp = temp.next){
            retVal += temp + " ";
        }
 
        return retVal;
    }
}

SelectionSortBench.java

package bench;

import sort.SelectionSort;
import java.util.concurrent.TimeUnit;
import java.util.Random;
import java.util.Arrays;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Level;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

public class SelectionSortBench {

    @State(Scope.Thread)
    public static class ThreadState{
        SelectionSort ss;
        Integer[] data;

        private int count = 80000;

        @Setup(Level.Invocation)
        public void prepare(){
            ss = new SelectionSort<>();
            data = new Random().ints().limit(count).boxed().toArray(Integer[]::new);        
        }
    }

    @Benchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    @Warmup(iterations = 3, time = 20)
    @Measurement(iterations = 3, time = 20)
    public void selectionAvgTime(ThreadState ts) {
        ts.ss.selectionSort(ts.data);
    }
    
    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(SelectionSortBench.class.getSimpleName())
                .forks(1)
                .build();

        new Runner(opt).run();
    }
}

InsertionSortBench.java

package bench;

import sort.LinkedList;
import java.util.concurrent.TimeUnit;
import java.util.Random;
import java.util.Arrays;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Level;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

public class InsertionSortBench {

    @State(Scope.Thread)
    public static class ThreadState{
        LinkedList ll;
        Integer[] data;

        private int count = 80000;

        @Setup(Level.Invocation)
        public void prepare(){
            ll = new LinkedList<>();
            data = new Random().ints().limit(count).boxed().toArray(Integer[]::new);
            for(Integer r : data)
                ll.prepend(r);
        }
    }

    @Benchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    @Warmup(iterations = 3, time = 20)
    @Measurement(iterations = 3, time = 20)
    public void insertionAvgTime(ThreadState ts) {
        ts.ll.insertionSort();
    }
    
    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(InsertionSortBench.class.getSimpleName())
                .forks(1)
                .build();

        new Runner(opt).run();
    }
}

Benchmark Results

10000

Benchmark                            Mode  Cnt    Score   Error  Units
InsertionSortBench.insertionAvgTime  avgt   15  154.535 ± 2.224  ms/op
SelectionSortBench.selectionAvgTime  avgt   15   58.493 ± 1.061  ms/op

20000

Benchmark                            Mode  Cnt    Score   Error  Units
InsertionSortBench.insertionAvgTime  avgt   15  930.232 ± 6.840  ms/op
SelectionSortBench.selectionAvgTime  avgt   15  257.823 ± 7.800  ms/op

40000

Benchmark                            Mode  Cnt     Score    Error  Units
InsertionSortBench.insertionAvgTime  avgt   15  4623.420 ± 96.844  ms/op
SelectionSortBench.selectionAvgTime  avgt   15  1231.270 ±  9.148  ms/op

80000

Benchmark                            Mode  Cnt      Score      Error  Units
InsertionSortBench.insertionAvgTime  avgt   15  20183.213 ±  229.960  ms/op
SelectionSortBench.selectionAvgTime  avgt   15   7504.977 ± 1015.729  ms/op