Skip to content

Commit eb90d11

Browse files
author
Sorin Zamfir
committed
Merge branch 'master' of github.com:eugenp/tutorials into feature/BAEL-3451_bash_functions
2 parents 9f2a168 + 0a369c4 commit eb90d11

125 files changed

Lines changed: 2052 additions & 252 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎algorithms-miscellaneous-5/src/main/java/com/baeldung/algorithms/minheapmerge/HeapNode.java‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
package com.baeldung.algorithms.minheapmerge;
2+
3+
public class HeapNode {
4+
5+
int element;
6+
int arrayIndex;
7+
int nextElementIndex = 1;
8+
9+
public HeapNode(int element, int arrayIndex) {
10+
this.element = element;
11+
this.arrayIndex = arrayIndex;
12+
}
13+
}

‎algorithms-miscellaneous-5/src/main/java/com/baeldung/algorithms/minheapmerge/MinHeap.java‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
package com.baeldung.algorithms.minheapmerge;
2+
3+
public class MinHeap {
4+
5+
HeapNode[] heapNodes;
6+
7+
public MinHeap(HeapNode heapNodes[]) {
8+
this.heapNodes = heapNodes;
9+
heapifyFromLastLeafsParent();
10+
}
11+
12+
void heapifyFromLastLeafsParent() {
13+
int lastLeafsParentIndex = getParentNodeIndex(heapNodes.length);
14+
while (lastLeafsParentIndex >= 0) {
15+
heapify(lastLeafsParentIndex);
16+
lastLeafsParentIndex--;
17+
}
18+
}
19+
20+
void heapify(int index) {
21+
int leftNodeIndex = getLeftNodeIndex(index);
22+
int rightNodeIndex = getRightNodeIndex(index);
23+
int smallestElementIndex = index;
24+
if (leftNodeIndex < heapNodes.length && heapNodes[leftNodeIndex].element < heapNodes[index].element) {
25+
smallestElementIndex = leftNodeIndex;
26+
}
27+
if (rightNodeIndex < heapNodes.length && heapNodes[rightNodeIndex].element < heapNodes[smallestElementIndex].element) {
28+
smallestElementIndex = rightNodeIndex;
29+
}
30+
if (smallestElementIndex != index) {
31+
swap(index, smallestElementIndex);
32+
heapify(smallestElementIndex);
33+
}
34+
}
35+
36+
int getParentNodeIndex(int index) {
37+
return (index - 1) / 2;
38+
}
39+
40+
int getLeftNodeIndex(int index) {
41+
return (2 * index + 1);
42+
}
43+
44+
int getRightNodeIndex(int index) {
45+
return (2 * index + 2);
46+
}
47+
48+
HeapNode getRootNode() {
49+
return heapNodes[0];
50+
}
51+
52+
void heapifyFromRoot() {
53+
heapify(0);
54+
}
55+
56+
void swap(int i, int j) {
57+
HeapNode temp = heapNodes[i];
58+
heapNodes[i] = heapNodes[j];
59+
heapNodes[j] = temp;
60+
}
61+
62+
static int[] merge(int[][] array) {
63+
HeapNode[] heapNodes = new HeapNode[array.length];
64+
int resultingArraySize = 0;
65+
66+
for (int i = 0; i < array.length; i++) {
67+
HeapNode node = new HeapNode(array[i][0], i);
68+
heapNodes[i] = node;
69+
resultingArraySize += array[i].length;
70+
}
71+
72+
MinHeap minHeap = new MinHeap(heapNodes);
73+
int[] resultingArray = new int[resultingArraySize];
74+
75+
for (int i = 0; i < resultingArraySize; i++) {
76+
HeapNode root = minHeap.getRootNode();
77+
resultingArray[i] = root.element;
78+
79+
if (root.nextElementIndex < array[root.arrayIndex].length) {
80+
root.element = array[root.arrayIndex][root.nextElementIndex++];
81+
} else {
82+
root.element = Integer.MAX_VALUE;
83+
}
84+
minHeap.heapifyFromRoot();
85+
}
86+
return resultingArray;
87+
}
88+
}

‎algorithms-miscellaneous-5/src/test/java/com/baeldung/algorithms/minheapmerge/MinHeapUnitTest.java‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package com.baeldung.algorithms.minheapmerge;
2+
3+
import static org.hamcrest.CoreMatchers.equalTo;
4+
import static org.hamcrest.CoreMatchers.is;
5+
import static org.junit.Assert.assertThat;
6+
7+
import org.junit.Test;
8+
9+
public class MinHeapUnitTest {
10+
11+
private final int[][] inputArray = { { 0, 6 }, { 1, 5, 10, 100 }, { 2, 4, 200, 650 } };
12+
private final int[] expectedArray = { 0, 1, 2, 4, 5, 6, 10, 100, 200, 650 };
13+
14+
@Test
15+
public void givenSortedArrays_whenMerged_thenShouldReturnASingleSortedarray() {
16+
int[] resultArray = MinHeap.merge(inputArray);
17+
18+
assertThat(resultArray.length, is(equalTo(10)));
19+
assertThat(resultArray, is(equalTo(expectedArray)));
20+
}
21+
22+
}

‎algorithms-sorting-2/.gitignore‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
/target/
2+
.settings/
3+
.classpath
4+
.project

‎algorithms-sorting-2/pom.xml‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
<project xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://maven.apache.org/POM/4.0.0"
2+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
3+
<modelVersion>4.0.0</modelVersion>
4+
<artifactId>algorithms-sorting-2</artifactId>
5+
<version>0.0.1-SNAPSHOT</version>
6+
<name>algorithms-sorting-2</name>
7+
8+
<parent>
9+
<groupId>com.baeldung</groupId>
10+
<artifactId>parent-modules</artifactId>
11+
<version>1.0.0-SNAPSHOT</version>
12+
</parent>
13+
14+
<dependencies>
15+
<dependency>
16+
<groupId>org.apache.commons</groupId>
17+
<artifactId>commons-math3</artifactId>
18+
<version>${commons-math3.version}</version>
19+
</dependency>
20+
<dependency>
21+
<groupId>commons-codec</groupId>
22+
<artifactId>commons-codec</artifactId>
23+
<version>${commons-codec.version}</version>
24+
</dependency>
25+
<dependency>
26+
<groupId>org.projectlombok</groupId>
27+
<artifactId>lombok</artifactId>
28+
<version>${lombok.version}</version>
29+
<scope>provided</scope>
30+
</dependency>
31+
<dependency>
32+
<groupId>org.junit.jupiter</groupId>
33+
<artifactId>junit-jupiter-api</artifactId>
34+
<version>${junit-jupiter-api.version}</version>
35+
<scope>test</scope>
36+
</dependency>
37+
<dependency>
38+
<groupId>org.assertj</groupId>
39+
<artifactId>assertj-core</artifactId>
40+
<version>${org.assertj.core.version}</version>
41+
<scope>test</scope>
42+
</dependency>
43+
</dependencies>
44+
45+
<build>
46+
<pluginManagement>
47+
<plugins>
48+
<plugin>
49+
<groupId>org.codehaus.mojo</groupId>
50+
<artifactId>exec-maven-plugin</artifactId>
51+
<version>${exec-maven-plugin.version}</version>
52+
</plugin>
53+
</plugins>
54+
</pluginManagement>
55+
</build>
56+
57+
<properties>
58+
<commons-math3.version>3.6.1</commons-math3.version>
59+
<org.assertj.core.version>3.9.0</org.assertj.core.version>
60+
<commons-codec.version>1.11</commons-codec.version>
61+
<junit-jupiter-api.version>5.3.1</junit-jupiter-api.version>
62+
</properties>
63+
64+
</project>

‎algorithms-sorting-2/src/main/java/com/baeldung/algorithms/quicksort/BentleyMcIlroyPartioning.java‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
package com.baeldung.algorithms.quicksort;
2+
3+
import static com.baeldung.algorithms.quicksort.SortingUtils.swap;
4+
5+
public class BentleyMcIlroyPartioning {
6+
7+
public static Partition partition(int input[], int begin, int end) {
8+
int left = begin, right = end;
9+
int leftEqualKeysCount = 0, rightEqualKeysCount = 0;
10+
11+
int partitioningValue = input[end];
12+
13+
while (true) {
14+
while (input[left] < partitioningValue)
15+
left++;
16+
17+
while (input[right] > partitioningValue) {
18+
if (right == begin)
19+
break;
20+
right--;
21+
}
22+
23+
if (left == right && input[left] == partitioningValue) {
24+
swap(input, begin + leftEqualKeysCount, left);
25+
leftEqualKeysCount++;
26+
left++;
27+
}
28+
29+
if (left >= right) {
30+
break;
31+
}
32+
33+
swap(input, left, right);
34+
35+
if (input[left] == partitioningValue) {
36+
swap(input, begin + leftEqualKeysCount, left);
37+
leftEqualKeysCount++;
38+
}
39+
40+
if (input[right] == partitioningValue) {
41+
swap(input, right, end - rightEqualKeysCount);
42+
rightEqualKeysCount++;
43+
}
44+
left++; right--;
45+
}
46+
right = left - 1;
47+
for (int k = begin; k < begin + leftEqualKeysCount; k++, right--) {
48+
if (right >= begin + leftEqualKeysCount)
49+
swap(input, k, right);
50+
}
51+
for (int k = end; k > end - rightEqualKeysCount; k--, left++) {
52+
if (left <= end - rightEqualKeysCount)
53+
swap(input, left, k);
54+
}
55+
return new Partition(right + 1, left - 1);
56+
}
57+
58+
public static void quicksort(int input[], int begin, int end) {
59+
if (end <= begin)
60+
return;
61+
Partition middlePartition = partition(input, begin, end);
62+
quicksort(input, begin, middlePartition.getLeft() - 1);
63+
quicksort(input, middlePartition.getRight() + 1, end);
64+
}
65+
66+
}

‎algorithms-sorting-2/src/main/java/com/baeldung/algorithms/quicksort/DutchNationalFlagPartioning.java‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package com.baeldung.algorithms.quicksort;
2+
3+
import static com.baeldung.algorithms.quicksort.SortingUtils.compare;
4+
import static com.baeldung.algorithms.quicksort.SortingUtils.swap;
5+
6+
public class DutchNationalFlagPartioning {
7+
8+
public static Partition partition(int[] a, int begin, int end) {
9+
int lt = begin, current = begin, gt = end;
10+
int partitioningValue = a[begin];
11+
12+
while (current <= gt) {
13+
int compareCurrent = compare(a[current], partitioningValue);
14+
switch (compareCurrent) {
15+
case -1:
16+
swap(a, current++, lt++);
17+
break;
18+
case 0:
19+
current++;
20+
break;
21+
case 1:
22+
swap(a, current, gt--);
23+
break;
24+
}
25+
}
26+
return new Partition(lt, gt);
27+
}
28+
29+
public static void quicksort(int[] input, int begin, int end) {
30+
if (end <= begin)
31+
return;
32+
33+
Partition middlePartition = partition(input, begin, end);
34+
35+
quicksort(input, begin, middlePartition.getLeft() - 1);
36+
quicksort(input, middlePartition.getRight() + 1, end);
37+
}
38+
}

‎algorithms-sorting-2/src/main/java/com/baeldung/algorithms/quicksort/Partition.java‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package com.baeldung.algorithms.quicksort;
2+
3+
public class Partition {
4+
private int left;
5+
private int right;
6+
7+
public Partition(int left, int right) {
8+
super();
9+
this.left = left;
10+
this.right = right;
11+
}
12+
13+
public int getLeft() {
14+
return left;
15+
}
16+
17+
public void setLeft(int left) {
18+
this.left = left;
19+
}
20+
21+
public int getRight() {
22+
return right;
23+
}
24+
25+
public void setRight(int right) {
26+
this.right = right;
27+
}
28+
29+
}

‎algorithms-sorting-2/src/main/java/com/baeldung/algorithms/quicksort/SortingUtils.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.baeldung.algorithms.quicksort;
2+
3+
public class SortingUtils {
4+
5+
public static void swap(int[] array, int position1, int position2) {
6+
if (position1 != position2) {
7+
int temp = array[position1];
8+
array[position1] = array[position2];
9+
array[position2] = temp;
10+
}
11+
}
12+
13+
public static int compare(int num1, int num2) {
14+
if (num1 > num2)
15+
return 1;
16+
else if (num1 < num2)
17+
return -1;
18+
else
19+
return 0;
20+
}
21+
22+
public static void printArray(int[] array) {
23+
if (array == null) {
24+
return;
25+
}
26+
for (int e : array) {
27+
System.out.print(e + " ");
28+
}
29+
System.out.println();
30+
}
31+
32+
}

‎algorithms-sorting-2/src/main/resources/logback.xml‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<configuration>
3+
<appender name="STDOUT" class="ch.qos.logback.core.ConsoleAppender">
4+
<encoder>
5+
<pattern>%d{HH:mm:ss.SSS} [%thread] %-5level %logger{36} - %msg%n
6+
</pattern>
7+
</encoder>
8+
</appender>
9+
10+
<root level="INFO">
11+
<appender-ref ref="STDOUT"/>
12+
</root>
13+
</configuration>

0 commit comments

Comments
 (0)