Skip to content

Commit 58cf08f

Browse files
NarekDWDebasish Biswas
NarekDW
and
Debasish Biswas
authored
Modify Insertion sort implementation to classical one + add function insertion-sentinel sort. (#3622)
* bug fix for CircularBuffer + refactoring + add unit tests * change Insertion sort to classical implementation + add isSorted function to SortUtils + add SortUtilsRandomGenerator for generating random values and arrays * little fix Co-authored-by: Debasish Biswas <debasishbsws.abc@gmail.com>
1 parent c8ecd23 commit 58cf08f

File tree

6 files changed

+304
-21
lines changed

6 files changed

+304
-21
lines changed

‎src/main/java/com/thealgorithms/sorts/InsertionSort.java

Lines changed: 64 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -1,45 +1,88 @@
11
package com.thealgorithms.sorts;
22

3-
import static com.thealgorithms.sorts.SortUtils.less;
4-
import static com.thealgorithms.sorts.SortUtils.print;
3+
import java.util.function.Function;
4+
5+
import static com.thealgorithms.sorts.SortUtils.*;
56

67
class InsertionSort implements SortAlgorithm {
78

89
/**
910
* Generic insertion sort algorithm in increasing order.
1011
*
1112
* @param array the array to be sorted.
12-
* @param <T> the class of array.
13+
* @param <T> the class of array.
1314
* @return sorted array.
1415
*/
1516
@Override
1617
public <T extends Comparable<T>> T[] sort(T[] array) {
17-
for (int i = 1; i < array.length; i++) {
18-
T insertValue = array[i];
19-
int j;
20-
for (j = i - 1; j >= 0 && less(insertValue, array[j]); j--) {
21-
array[j + 1] = array[j];
22-
}
23-
if (j != i - 1) {
24-
array[j + 1] = insertValue;
18+
for (int i = 1; i < array.length; i++)
19+
for (int j = i; j > 0 && less(array[j], array[j - 1]); j--)
20+
swap(array, j, j - 1);
21+
return array;
22+
}
23+
24+
/**
25+
* Sentinel sort is a function which on the first step finds the minimal element in the provided
26+
* array and puts it to the zero position, such a trick gives us an ability to avoid redundant
27+
* comparisons like `j > 0` and swaps (we can move elements on position right, until we find
28+
* the right position for the chosen element) on further step.
29+
*
30+
* @param array the array to be sorted
31+
* @param <T> Generic type which extends Comparable interface.
32+
* @return sorted array
33+
*/
34+
public <T extends Comparable<T>> T[] sentinelSort(T[] array) {
35+
int minElemIndex = 0;
36+
int n = array.length;
37+
if (n < 1)
38+
return array;
39+
40+
// put the smallest element to the 0 position as a sentinel, which will allow us to avoid
41+
// redundant comparisons like `j > 0` further
42+
for (int i = 1; i < n; i++)
43+
if (less(array[i], array[minElemIndex]))
44+
minElemIndex = i;
45+
swap(array, 0, minElemIndex);
46+
47+
for (int i = 2; i < n; i++) {
48+
int j = i;
49+
T currentValue = array[i];
50+
while (less(currentValue, array[j - 1])) {
51+
array[j] = array[j - 1];
52+
j--;
2553
}
54+
55+
array[j] = currentValue;
2656
}
57+
2758
return array;
2859
}
2960

3061
/**
3162
* Driver Code
3263
*/
3364
public static void main(String[] args) {
34-
Integer[] integers = { 4, 23, 6, 78, 1, 54, 231, 9, 12 };
35-
InsertionSort sort = new InsertionSort();
36-
sort.sort(integers);
37-
print(integers);
38-
/* [1, 4, 6, 9, 12, 23, 54, 78, 231] */
39-
40-
String[] strings = { "c", "a", "e", "b", "d" };
41-
sort.sort(strings);
42-
print(strings);
43-
/* [a, b, c, d, e] */
65+
int size = 100_000;
66+
Double[] randomArray = SortUtilsRandomGenerator.generateArray(size);
67+
Double[] copyRandomArray = new Double[size];
68+
System.arraycopy(randomArray, 0, copyRandomArray, 0, size);
69+
70+
InsertionSort insertionSort = new InsertionSort();
71+
double insertionTime = measureApproxExecTime(insertionSort::sort, randomArray);
72+
System.out.printf("Original insertion time: %5.2f sec.\n", insertionTime);
73+
74+
double insertionSentinelTime = measureApproxExecTime(insertionSort::sentinelSort, copyRandomArray);
75+
System.out.printf("Sentinel insertion time: %5.2f sec.\n", insertionSentinelTime);
76+
77+
// ~ 1.5 time sentinel sort is faster, then classical Insertion sort implementation.
78+
System.out.printf("Sentinel insertion is %f3.2 time faster than Original insertion sort\n",
79+
insertionTime / insertionSentinelTime);
80+
}
81+
82+
private static double measureApproxExecTime(Function<Double[], Double[]> sortAlgorithm, Double[] randomArray) {
83+
long start = System.currentTimeMillis();
84+
sortAlgorithm.apply(randomArray);
85+
long end = System.currentTimeMillis();
86+
return (end - start) / 1000.0;
4487
}
4588
}

‎src/main/java/com/thealgorithms/sorts/SortUtils.java

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -99,4 +99,17 @@ static <T extends Comparable<T>> void flip(T[] array, int left, int right) {
9999
swap(array, left++, right--);
100100
}
101101
}
102+
103+
/**
104+
* Function to check if the array is sorted. By default, it will check if the array is sorted in ASC order.
105+
*
106+
* @param array - an array which to check is it sorted or not.
107+
* @return true - if array sorted in ASC order, false otherwise.
108+
*/
109+
static <T extends Comparable<T>> boolean isSorted(T[] array) {
110+
for (int i = 1; i < array.length; i++)
111+
if (less(array[i], array[i - 1]))
112+
return false;
113+
return true;
114+
}
102115
}

‎src/main/java/com/thealgorithms/sorts/SortUtilsRandomGenerator.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package com.thealgorithms.sorts;
2+
3+
import java.util.Random;
4+
5+
public class SortUtilsRandomGenerator {
6+
7+
private static final Random random;
8+
private static final long seed;
9+
10+
static {
11+
seed = System.currentTimeMillis();
12+
random = new Random(seed);
13+
}
14+
15+
16+
/**
17+
* Function to generate array of double values, with predefined size.
18+
*
19+
* @param size result array size
20+
* @return array of Double values, randomly generated, each element is between [0, 1)
21+
*/
22+
public static Double[] generateArray(int size) {
23+
Double[] arr = new Double[size];
24+
for (int i = 0; i < size; i++)
25+
arr[i] = generateDouble();
26+
return arr;
27+
}
28+
29+
/**
30+
* Function to generate Double value.
31+
*
32+
* @return Double value [0, 1)
33+
*/
34+
public static Double generateDouble() {
35+
return random.nextDouble();
36+
}
37+
38+
}

‎src/test/java/com/thealgorithms/sorts/InsertionSortTest.java

Lines changed: 114 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,114 @@
1+
package com.thealgorithms.sorts;
2+
3+
import org.junit.jupiter.api.BeforeEach;
4+
import org.junit.jupiter.api.Test;
5+
6+
import java.util.function.Function;
7+
8+
import static org.junit.jupiter.api.Assertions.*;
9+
10+
class InsertionSortTest {
11+
private InsertionSort insertionSort;
12+
13+
@BeforeEach
14+
void setUp() {
15+
insertionSort = new InsertionSort();
16+
}
17+
18+
@Test
19+
void insertionSortSortEmptyArrayShouldPass() {
20+
testEmptyArray(insertionSort::sort);
21+
testEmptyArray(insertionSort::sentinelSort);
22+
}
23+
24+
private void testEmptyArray(Function<Integer[], Integer[]> sortAlgorithm) {
25+
Integer[] array = {};
26+
Integer[] sorted = sortAlgorithm.apply(array);
27+
Integer[] expected = {};
28+
assertArrayEquals(expected, sorted);
29+
assertTrue(SortUtils.isSorted(sorted));
30+
}
31+
32+
@Test
33+
void insertionSortClassicalSortSingleValueArrayShouldPass() {
34+
testSingleValue(insertionSort::sort);
35+
testSingleValue(insertionSort::sentinelSort);
36+
}
37+
38+
private void testSingleValue(Function<Integer[], Integer[]> sortAlgorithm) {
39+
Integer[] array = {7};
40+
Integer[] sorted = sortAlgorithm.apply(array);
41+
Integer[] expected = {7};
42+
assertArrayEquals(expected, sorted);
43+
assertTrue(SortUtils.isSorted(sorted));
44+
}
45+
46+
@Test
47+
void insertionSortClassicalWithIntegerArrayShouldPass() {
48+
testIntegerArray(insertionSort::sort);
49+
testIntegerArray(insertionSort::sentinelSort);
50+
}
51+
52+
private void testIntegerArray(Function<Integer[], Integer[]> sortAlgorithm) {
53+
Integer[] array = {49, 4, 36, 9, 144, 1};
54+
Integer[] sorted = sortAlgorithm.apply(array);
55+
Integer[] expected = {1, 4, 9, 36, 49, 144};
56+
assertArrayEquals(expected, sorted);
57+
assertTrue(SortUtils.isSorted(sorted));
58+
}
59+
60+
@Test
61+
void insertionSortClassicalForArrayWithNegativeValuesShouldPass() {
62+
testWithNegativeValues(insertionSort::sort);
63+
testWithNegativeValues(insertionSort::sentinelSort);
64+
}
65+
66+
private void testWithNegativeValues(Function<Integer[], Integer[]> sortAlgorithm) {
67+
Integer[] array = {49, -36, -144, -49, 1, 9};
68+
Integer[] sorted = sortAlgorithm.apply(array);
69+
Integer[] expected = {-144, -49, -36, 1, 9, 49};
70+
assertArrayEquals(expected, sorted);
71+
assertTrue(SortUtils.isSorted(sorted));
72+
}
73+
74+
@Test
75+
void insertionSortClassicalForArrayWithDuplicateValuesShouldPass() {
76+
testWithDuplicates(insertionSort::sort);
77+
testWithDuplicates(insertionSort::sentinelSort);
78+
}
79+
80+
private void testWithDuplicates(Function<Integer[], Integer[]> sortAlgorithm) {
81+
Integer[] array = {36, 1, 49, 1, 4, 9};
82+
Integer[] sorted = sortAlgorithm.apply(array);
83+
Integer[] expected = {1, 1, 4, 9, 36, 49};
84+
assertArrayEquals(expected, sorted);
85+
assertTrue(SortUtils.isSorted(sorted));
86+
}
87+
88+
@Test
89+
void insertionSortClassicalWithStringArrayShouldPass() {
90+
testWithStringArray(insertionSort::sort);
91+
testWithStringArray(insertionSort::sentinelSort);
92+
}
93+
94+
private void testWithStringArray(Function<String[], String[]> sortAlgorithm) {
95+
String[] array = {"c", "a", "e", "b", "d"};
96+
String[] sorted = sortAlgorithm.apply(array);
97+
String[] expected = {"a", "b", "c", "d", "e"};
98+
assertArrayEquals(expected, sorted);
99+
assertTrue(SortUtils.isSorted(sorted));
100+
}
101+
102+
@Test
103+
void insertionSortClassicalWithRandomArrayPass() {
104+
testWithRandomArray(insertionSort::sort);
105+
testWithRandomArray(insertionSort::sentinelSort);
106+
}
107+
108+
private void testWithRandomArray(Function<Double[], Double[]> sortAlgorithm) {
109+
int randomSize = (int) (SortUtilsRandomGenerator.generateDouble() * 10_000);
110+
Double[] array = SortUtilsRandomGenerator.generateArray(randomSize);
111+
Double[] sorted = sortAlgorithm.apply(array);
112+
assertTrue(SortUtils.isSorted(sorted));
113+
}
114+
}

‎src/test/java/com/thealgorithms/sorts/SortUtilsRandomGeneratorTest.java

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package com.thealgorithms.sorts;
2+
3+
import org.junit.jupiter.api.RepeatedTest;
4+
import org.junit.jupiter.api.Test;
5+
6+
import static org.assertj.core.api.Assertions.assertThat;
7+
8+
class SortUtilsRandomGeneratorTest {
9+
10+
@RepeatedTest(1000)
11+
void generateArray() {
12+
int size = 1_000;
13+
Double[] doubles = SortUtilsRandomGenerator.generateArray(size);
14+
assertThat(doubles).hasSize(size);
15+
assertThat(doubles).doesNotContainNull();
16+
}
17+
18+
@Test
19+
void generateArrayEmpty() {
20+
int size = 0;
21+
Double[] doubles = SortUtilsRandomGenerator.generateArray(size);
22+
assertThat(doubles).hasSize(size);
23+
}
24+
25+
@RepeatedTest(1000)
26+
void generateDouble() {
27+
Double randomDouble = SortUtilsRandomGenerator.generateDouble();
28+
assertThat(randomDouble).isBetween(0.0, 1.0);
29+
assertThat(randomDouble).isNotEqualTo(1.0);
30+
}
31+
}

‎src/test/java/com/thealgorithms/sorts/SortUtilsTest.java

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package com.thealgorithms.sorts;
2+
3+
import org.junit.jupiter.api.Test;
4+
5+
import static org.junit.jupiter.api.Assertions.*;
6+
7+
class SortUtilsTest {
8+
9+
@Test
10+
void isSortedEmptyArray() {
11+
Double[] emptyArray = {};
12+
assertTrue(SortUtils.isSorted(emptyArray));
13+
}
14+
15+
@Test
16+
void isSortedWithSingleElement() {
17+
Double[] singleElementArray = {1.0};
18+
assertTrue(SortUtils.isSorted(singleElementArray));
19+
}
20+
21+
@Test
22+
void isSortedTrue() {
23+
Integer[] array = {1, 1, 2, 3, 5, 8, 11};
24+
assertTrue(SortUtils.isSorted(array));
25+
26+
Integer[] identicalArray = {1, 1, 1, 1, 1};
27+
assertTrue(SortUtils.isSorted(identicalArray));
28+
29+
Double[] doubles = {-15.123, -15.111, 0.0, 0.12, 0.15};
30+
assertTrue(SortUtils.isSorted(doubles));
31+
}
32+
33+
@Test
34+
void isSortedFalse() {
35+
Double[] array = {1.0, 3.0, -0.15};
36+
assertFalse(SortUtils.isSorted(array));
37+
38+
Integer[] array2 = {14, 15, 16, 1};
39+
assertFalse(SortUtils.isSorted(array2));
40+
41+
Integer[] array3 = {5, 4, 3, 2, 1};
42+
assertFalse(SortUtils.isSorted(array3));
43+
}
44+
}

0 commit comments

Comments
 (0)