O(n^2) Sorting Benchmarks

zpackage sort;

public class SelectionSort<T extends Comparable<T>> {

    // 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;
        }
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

zpackage sort;

public class SelectionSort<T extends Comparable<T>> {

// 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;

}

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<T extends Comparable<T>> {
    
    private class Node<T extends Comparable<T>> {
        T data;
        Node<T> next;
 
        public Node(T data){
            this.data = data;
        }
 
        public Node(T data, Node<T> next){
            this(data);
            this.next = next;
        }
 
        public String toString(){
            return "" + data;
        }
    }
 
    private Node<T> head;
    private int count;
 
    public LinkedList(){
        head = null;
        count = 0;
    }
 
    public LinkedList(T d){
        head = new Node<T>(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<T>(d, head);
        count++;
    }

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

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<T extends Comparable<T>> {

private class Node<T extends Comparable<T>> {

T data;

Node<T> next;

public Node(T data){

this.data = data;

}

public Node(T data, Node<T> next){

this(data);

this.next = next;

}

public String toString(){

return "" + data;

}

private Node<T> head;

private int count;

public LinkedList(){

head = null;

count = 0;

}

public LinkedList(T d){

head = new Node<T>(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<T>(d, head);

count++;

}

public void insertionSort(){

Node<T> 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<T>(d, head);

else {

Node<T> curr = head;

for ( ; curr.next != null && (d.compareTo(curr.next.data) > 0) ; curr = curr.next);

curr.next = new Node<T>(d, curr.next);

}

count++;

}

@Override

public String toString(){

String retVal = "Linked List with " + count + " nodes: ";

for (Node<T> temp = head ; temp != null ; temp = temp.next){

retVal += temp + " ";

}

return retVal;

}

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<Integer> 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();
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

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<Integer> 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();

}

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<Integer> 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();
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

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<Integer> 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();

}

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

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

Hi There!

SelectionSort.java

LinkedList.java [InsertionSort version]

SelectionSortBench.java

InsertionSortBench.java

Benchmark Results