Search code, repositories, users, issues, pull requests...

var quickMergeCharacter = new GenericQuickSort<Character>();
var quickMergeStudent = new GenericQuickSort<Student>();

Pivotselectie

Om op een goede en uitbreidbare manier een pivotselectie te implementeren heb ik zelf gekozen om een strategy pattern toe te passen. Hierbij kunnen ook toekomstige manier voor pivots makkelijk worden toegevoegd.
De volgende 3 pivot's zijn geimplementeerd

Random
Middle
Median Of Three

var quickMergeStudent = new GenericQuickSort<Student>();
quickMergeStudent.sort(this.studentArray, new MiddlePivot<>());
quickMergeStudent.sort(this.studentArray, new RandomPivot<>());
quickMergeStudent.sort(this.studentArray, new MedianOfThreePivot<>());

Geautomatiseerd testen op bekende input

Testen Resultaat van testen in : travis-ci.com en/of travis-ci.org

Kortste paden

Datastructuren

Voor het maken van de graaf heb ik ook gekozen om generics te gebruiken. Zodat er de mogelijk bestaat om ook grafen te maken van andere objecten. Dat had als impact dat ik geen 2d linkedlist kon gebruiken als adjacency list. De reden hiervoor is dat ik de waarde van de vertex niet kon gebruiken als key. Dit gaat met een primitieve of niet-primitieve integer wel. Uiteindelijk heb ik er voor gekozen om een hashmap te implementeren. Dit geeft de mogelijkheid dat je met een object de juiste vertex kan oproepen, waarin dat een linkedlist staat met edges naar andere vertices.

Een adjacency list heeft standaard de voorkeur ten opzichte van een adjecency matrix. Dit omdat het efficiënter omgaat met graaf met een lage dichtheid. Is de dichtheid hoger ( wanneer de aantal edges dicht aan het aantal vertices tot de macht 2 ligt) dan is de matrix weer efficiënter.

	Adjacency list	Adjacency matrix
Store graph	O(\|V\|+\|E\|)	O(\|V\|^2)
Add vertex	O(1)	O(\|V\|^2)
Add edge	O(1)	O(1)
Remove vertex	O(\|E\|)	O(\|V\|^2)
Remove edge	O(\|V\|)	O(1)
Are vertices x and y adjacent (assuming that their storage positions are known)?	O(\|V\|)	O(1)
Remarks	Slow to remove vertices and edges, because it needs to find all vertices or edges	Slow to add or remove vertices, because matrix must be resized/copied

|V| = Vertices |E| = Edges Bron

Een strategy pattern is gebruikt om het Dijkstra algoritme te implementeren. Hierdoor kunnen er makkelijker verschillende shortest path algoritmes toegevoegd worden.

De graaf is zowel directed als undirected te gebruiken, en weighted en unweighted. Dit is te doen om in de constructor de GraphDirection en GraphWeight mee te geven.

Graph<Character> route01 = new Graph<>(GraphDirection.DIRECTED, GraphWeight.WEIGHTED);

Bij default is de graaf unweighted en undirected.

Graph<Character> route01 = new Graph<>();
route01.addVertex(this.graphCharacterArray);
route01.addEdge('a', 'b');
route01.addEdge('c', 'b');
route01.addEdge('a', 'c');

Ongewogen

Graph<Character> route05 =
    new Graph<>(GraphDirection.DIRECTED, GraphWeight.UNWEIGHTED);
route05.addVertex(this.graphCharacterArray);
route05.addEdge('a', 'b');
route05.addEdge('c', 'b');
route05.addEdge('a', 'c');
route05.addEdge('c', 'd');
route05.addEdge('d', 'e');
route05.addEdge('e', 'a');
logger.info("Graph 05: shortestpath {}", route05.searchShortestPath('a', 'e'));
// Graph 05: shortestpath Path{path=a --> c --> d --> e --> , weight=4.0}

Gewogen

Graph<Character> route04 =
    new Graph<>(GraphDirection.UNDIRECTED, GraphWeight.WEIGHTED);
route04.addVertex(this.graphCharacterArray);
route04.addEdge('a', 'b', 8);
route04.addEdge('c', 'b', 3);
route04.addEdge('a', 'c', 6);
route04.addEdge('c', 'd', 4);
route04.addEdge('d', 'e', 7);
route04.addEdge('e', 'a', 2);
logger.info("Graph 04: shortestpath {}", route04.searchShortestPath('a', 'e'));
// Graph 04: shortestpath Path{path=a --> e --> , weight=2.2}

Geautomatiseerd testen op bekende input

Testen Resultaat van testen in : travis-ci.com en/of travis-ci.org

Binaire zoekboom

insert

BinarySearchTree<Integer> binarySearchTree01 = new BinarySearchTree<>();
binarySearchTree01.insert(10);
binarySearchTree01.insert(15);
binarySearchTree01.insert(11);
binarySearchTree01.insert(8);
binarySearchTree01.insert(2);
binarySearchTree01.insert(1);
// or
binarySearchTree01.insert(3, 2, 4, 2, 77, 3, 213423, 34, 223, 443, -33);

find

BinarySearchTree<Integer> binarySearchTree01 = new BinarySearchTree<>();
binarySearchTree01.insert(3, 2, 4, 2, 77, 3, 213423, 34, 223, 443, -33);
Integer node = binarySearchTree01.search(2);

findMin en findMax

BinarySearchTree<Integer> binarySearchTree01 = new BinarySearchTree<>();
binarySearchTree01.insert(3, 2, 4, 2, 77, 3, 213423, 34, 223, 443, -33);
Integer node1 = binarySearchTree01.findMax();
Integer node2 = binarySearchTree01.findMin();

remove

BinarySearchTree<Integer> binarySearchTree01 = new BinarySearchTree<>();
binarySearchTree01.insert(3, 2, 4, 2, 77, 3, 213423, 34, 223, 443, -33);
binarySearchTree01.remove(213423);