algorithm-analyzer

A tool to analyze various sorting algorithms, graphs or binary trees. The repository contains implementations for algorithms that where taught by Prof. Dr. rer. nat. Karsten Weicker in the Sommersemester 2021 at the Htwk Leipzig.

This is a community project with the aim to exchange experiences among students. It is also designed to better understand the algorithms and how they work.

Contributing

Everyone is welcome to contribute, please read the contribution guideline if you want to know how this works.

Usage

Requirements

JDK 16 or newer
Maven 3.8.x or newer

Setup

mvn clean install

Run

mvn exec:java

Build

Compile to run directly in the terminal:

mvn compile

Package compiled source code into an executable jar file:

mvn package

Outputs to target/algorithm-analyzer-x.x.x.jar

Test

mvn test

Formatting Code

/bin/sh bin/format.sh

Calls google-code-formatter locally.

Sorting Algorithms

Bubblesort

final Integer[] array = {15, 48, 22, 34, 27, 35, 14};

final Algorithm<Event, BubbleSort.Data<Integer>> a = new BubbleSort<Integer>();
final EventConsumer<Event> ec = new GeneralEventConsumer();

a.run(ec, new BubbleSort.Data<>(array));

ec.visitEvents(new LogEventVisitor());

Insertionsort

final Integer[] array = {15, 48, 22, 34, 27, 35, 14};

final Algorithm<Event, InsertionSort.Data<Integer>> a = new InsertionSort<Integer>();
final EventConsumer<Event> ec = new GeneralEventConsumer();

a.run(ec, new InsertionSort.Data<>(array));

ec.visitEvents(new LogEventVisitor());

Quicksort

final Integer[] array = {20, 54, 28, 31, 5, 24, 39, 14, 1, 15};

final Algorithm<Event, Quicksort.Data<Integer>> a = new Quicksort<Integer>();
final EventConsumer<Event> ec = new GeneralEventConsumer();

a.run(ec, new Quicksort.Data<>(array));

ec.visitEvents(new LogEventVisitor());

Shellsort

final Integer[] array = {6, 5, 4, 3, 2, 1};

final Algorithm<Event, Shellsort.Data<Integer>> a = new Shellsort<Integer>();
final EventConsumer<Event> ec = new GeneralEventConsumer();

a.run(ec, new Shellsort.Data<>(array));

ec.visitEvents(new LogEventVisitor());

Selectionsort

final Integer[] array = {64, 25, 12, 22, 11};

final Algorithm<Event, Selectionsort.Data<Integer>> a = new Selectionsort<Integer>();
final EventConsumer<Event> ec = new GeneralEventConsumer();

a.run(ec, new Selectionsort.Data<>(array));

ec.visitEvents(new LogEventVisitor());

Heapsort

final Integer[] array = {20, 54, 28, 31, 5, 24, 39, 14, 1, 15};

final Algorithm<Event, HeapSort.Data<Integer>> a = new HeapSort<Integer>();
final EventConsumer<Event> ec = new GeneralEventConsumer();

a.run(ec, new HeapSort.Data<>(array));

ec.visitEvents(new LogEventVisitor());

Countingsort

final Integer[] array = {2, 4, 2, 1, 1, 4, 2, 1, 4, 2};

final Algorithm<Event, Countingsort.Data<Integer>> a = new Countingsort<Integer>();
final EventConsumer<Event> ec = new GeneralEventConsumer();

a.run(ec, new Countingsort.Data<>(array));

ec.visitEvents(new LogEventVisitor());

Radixsort

See: Countingsort

// Todo...

Data Structures

Binary Search

final Integer[] array = {21, 25, 32, 33, 26, 40, 52, 53, 57, 60, 65, 66, 67, 78};
final Integer searchedValue = 60;

final Algorithm<Event, BinarySearch.Data<Integer>> a = new BinarySearch<>();
final EventConsumer<Event> ec = new GeneralEventConsumer();

a.run(ec, new BinarySearch.Data<Integer>(array, searchedValue));

ec.visitEvents(new LogEventVisitor());

AVL Tree

AVLTree<Integer> t = new AVLTree<Integer>(Comparator.naturalOrder());
EventConsumer<Event> ec = new GeneralEventConsumer();
t.onEvent(ec);

t.insert(4);
t.insert(2);
t.insert(5);
t.insert(1);
t.insert(3);
t.insert(6);
t.insert(10);
t.insert(15);
t.remove(2);
t.insert(13);
t.remove(3);

ec.visitEvents(new LogEventVisitor());

Skiplist

// Todo ...

Graph Algorithms

Deepsearch (Tiefensuche)

int size = 4;
String[] nodeNames = {"A", "B", "C", "D"};
WeightFreeGraph<Integer> graph = new AdjacentMatrixGraph(size);

graph.setEdge(1, 0);
graph.setEdge(0, 3);
graph.setEdge(0, 2);
graph.setEdge(2, 1);
graph.setEdge(2, 3);
graph.setEdge(3, 1);
graph.setEdge(3, 2);

final Algorithm<Event, Deepsearch.Data> a = new Deepsearch();
final EventConsumer<Event> ec = new GeneralEventConsumer();

a.run(ec, new Deepsearch.Data(graph, nodeNames));

ec.visitEvents(new LogEventVisitor());

Breath-First Search (Breitensuche)

String start = "v1";
Collection<Edge<String, Integer>> edges = Set.of(
    Edge.of("v1", "v2", 7),
    Edge.of("v1", "v3", 4),
    Edge.of("v1", "v4", 2),
    Edge.of("v2", "v3", 3),
    Edge.of("v2", "v5", 3),
    Edge.of("v3", "v4", 1),
    Edge.of("v3", "v5", 5),
    Edge.of("v4", "v5", 8)
);
Graph<String, Integer> graph = new LinkedGraph<>(edges);
for (Edge<String, Integer> e : edges) {
    graph.setEdge(e.to(), e.from(), e.weight());
}

final Algorithm<Event, BreathFirst.Data> a = new BreathFirst();
final EventConsumer<Event> ec = new GeneralEventConsumer();

a.run(ec, new BreathFirst.Data<String>(graph, start));

ec.visitEvents(new LogEventVisitor());

Dijkstra

Graph<Character, Integer> costs = new LinkedGraph<>(Set.of(
    Edge.of('A', 'B', 100),
    Edge.of('A', 'C', 50),
    Edge.of('B', 'C', 100),
    Edge.of('B', 'D', 100),
    Edge.of('B', 'E', 250),
    Edge.of('C', 'E', 250),
    Edge.of('D', 'E', 50)
));

final Algorithm<Event, Dijkstra.Data<Character>> a = new Dijkstra<>();
final EventConsumer<Event> ec = new GeneralEventConsumer();

a.run(ec, new Dijkstra.Data<Character>(costs, 'A'));

ec.visitEvents(new LogEventVisitor());

Floyd–Warshall Algorithm

Graph<Character, Integer> costs = new LinkedGraph<>(Set.of(
    Edge.of('v', 'x', 2),
    Edge.of('w', 'v', 10),
    Edge.of('w', 'x', 5),
    Edge.of('x', 'v', 3),
    Edge.of('x', 'y', 2),
    Edge.of('y', 'v', 10),
    Edge.of('y', 'w', 1)
));

Algorithm<Event, FloydWarshall.Data<Character>> alg = new FloydWarshall<>();
final EventConsumer<Event> ec = new GeneralEventConsumer();
alg.run(ec, new FloydWarshall.Data<>(costs));

ec.visitEvents(new LogEventVisitor());

Traveling Salesman (Rundreise)

Collection<Edge<Character, Integer>> edges = Set.of(
    Edge.of('A', 'B', 7),
    Edge.of('A', 'C', 5),
    Edge.of('A', 'D', 8),
    Edge.of('A', 'E', 12),
    Edge.of('B', 'C', 5),
    Edge.of('B', 'D', 9),
    Edge.of('B', 'E', 8),
    Edge.of('C', 'D', 4),
    Edge.of('C', 'E', 7),
    Edge.of('D', 'E', 9)
);

Graph<Character, Integer> graph = new LinkedGraph<>(edges);
for (Edge<Character, Integer> e : edges) {
    graph.setEdge(e.to(), e.from(), e.weight());
}

final Algorithm<Event, TravelingSalesman.Data<Character>> a = new TravelingSalesman<>();
final EventConsumer<Event> ec = new GeneralEventConsumer();

a.run(ec, new TravelingSalesman.Data<Character>(graph));

ec.visitEvents(new LogEventVisitor());

Hash Tables

Closed Hash Table

int startSize = 11;
EventConsumer<Event> ec = new GeneralEventConsumer();
ClosedHashTable.Hashing hashing = (int key, int p) -> {
    return key % p;
};
ClosedHashTable.Probing probing = (int key, int j, int p) -> {
    return (key % p) + j;
};
ClosedHashTable table = new ClosedHashTable(ec, startSize, hashing, probing);
table.resizeFactor = 3 / 2; // Resize by next prime to 3/2 of size.
table.resizeAtOccupation = 0.9; // Resize at 90% occupation.

table.insert(29);
table.insert(12);
table.insert(7);
table.insert(19);
table.insert(30);
table.insert(40);
table.insert(11);
table.remove(7);
table.insert(18);

ec.visitEvents(new LogEventVisitor());

Double Hash Table

int size = 11;
EventConsumer<Event> ec = new GeneralEventConsumer();
DoubleHashTable.Hashing hashing = (int key) -> {
    return key % 11;
};
DoubleHashTable.Hashing doubleHashing = (int key) -> {
    return (1 + (key % (11 - 1)));
};
DoubleHashTable table = new DoubleHashTable(ec, size, hashing, doubleHashing);

table.insert(29);
table.insert(12);
table.insert(7);
table.insert(19);
table.insert(30);
table.insert(40);
table.insert(11);

ec.visitEvents(new LogEventVisitor());

Brent Hash Table

int size = 11;
EventConsumer<Event> ec = new GeneralEventConsumer();
BrentHashTable.Hashing hashing =(int key) -> {
    return key % 11;
};
BrentHashTable.Hashing doubleHashing = (int key) -> {
    return (1 + (key % (11 - 1)));
};
BrentHashTable table = new BrentHashTable(ec, size, hashing, doubleHashing);

table.insert(29);
table.insert(12);
table.insert(7);
table.insert(19);
table.insert(30);
table.insert(40);
table.insert(11);

ec.visitEvents(new LogEventVisitor());

Coalesced Hash Table

int mod = 10;
int reserved = 2;
EventConsumer<Event> ec = new GeneralEventConsumer();
CoalescedHashTable table = new CoalescedHashTable(ec, mod, reserved);

table.insert(29);
table.insert(12);
table.insert(7);
table.insert(19);
table.insert(30);
table.insert(40);
table.insert(2);
table.insert(39);
table.insert(8);

ec.visitEvents(new LogEventVisitor());

Runtime

Algorithm	Best Case	Worst Case	Expected Case
Shellsort	O(n log n)	O(n²)	Depends on gap sequence
Selectionsort	O(n²)	O(n²)	O(n²)
dijkstra	O(n²)	O(n²)	O(n²)

Name		Name	Last commit message	Last commit date
Latest commit History 71 Commits
.github		.github
.settings		.settings
.vscode		.vscode
bin		bin
images		images
src		src
.DS_Store		.DS_Store
.classpath		.classpath
.gitignore		.gitignore
.project		.project
README.md		README.md
pom.xml		pom.xml

cbl/algorithm-analyzer

Folders and files

Latest commit

History

Repository files navigation