Skip to content

Commit c7665cd

Browse files
tapankavasthisjmillington
tapankavasthi
authored and
sjmillington
committed
BAEL-3484: Partitioning and Sorting an Array With Many Repeated Entries (eugenp#8369)
1 parent 521473e commit c7665cd

10 files changed

Lines changed: 279 additions & 0 deletions

File tree

‎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>

‎algorithms-sorting-2/src/test/java/com/baeldung/algorithms/quicksort/BentleyMcilroyPartitioningUnitTest.java‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
package com.baeldung.algorithms.quicksort;
2+
3+
import org.junit.Assert;
4+
import org.junit.Test;
5+
6+
public class BentleyMcilroyPartitioningUnitTest {
7+
8+
@Test
9+
public void given_IntegerArray_whenSortedWithBentleyMcilroyPartitioning_thenGetSortedArray() {
10+
int[] actual = {3, 2, 2, 2, 3, 7, 7, 3, 2, 2, 7, 3, 3};
11+
int[] expected = {2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 7, 7, 7};
12+
BentleyMcIlroyPartioning.quicksort(actual, 0, actual.length - 1);
13+
Assert.assertArrayEquals(expected, actual);
14+
}
15+
16+
}

‎algorithms-sorting-2/src/test/java/com/baeldung/algorithms/quicksort/DNFThreeWayQuickSortUnitTest.java‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package com.baeldung.algorithms.quicksort;
2+
3+
import org.junit.Assert;
4+
import org.junit.Test;
5+
6+
public class DNFThreeWayQuickSortUnitTest {
7+
8+
@Test
9+
public void givenIntegerArray_whenSortedWithThreeWayQuickSort_thenGetSortedArray() {
10+
int[] actual = {3, 5, 5, 5, 3, 7, 7, 3, 5, 5, 7, 3, 3};
11+
int[] expected = {3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 7, 7, 7};
12+
DutchNationalFlagPartioning.quicksort(actual, 0, actual.length - 1);
13+
Assert.assertArrayEquals(expected, actual);
14+
}
15+
}

‎pom.xml‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -341,6 +341,7 @@
341341
<module>algorithms-miscellaneous-4</module>
342342
<module>algorithms-miscellaneous-5</module>
343343
<module>algorithms-sorting</module>
344+
<module>algorithms-sorting-2</module>
344345
<module>algorithms-searching</module>
345346
<module>animal-sniffer-mvn-plugin</module>
346347
<module>annotations</module>
@@ -985,6 +986,7 @@
985986
<module>algorithms-miscellaneous-4</module>
986987
<module>algorithms-miscellaneous-5</module>
987988
<module>algorithms-sorting</module>
989+
<module>algorithms-sorting-2</module>
988990
<module>algorithms-searching</module>
989991
<module>animal-sniffer-mvn-plugin</module>
990992
<module>annotations</module>

0 commit comments

Comments
 (0)