Skip to content

refactor: cleanup ShellSort #5302

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
siriak merged 2 commits into from
Jul 26, 2024
Merged

refactor: cleanup ShellSort #5302

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
df2e79f
refactor: ShellSort refactoring, improving test according to general …
Jul 25, 2024
0d17676
checkstyle: remove redundant line
Jul 25, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
69 changes: 46 additions & 23 deletions src/main/java/com/thealgorithms/sorts/ShellSort.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -11,36 +11,59 @@ public class ShellSort implements SortAlgorithm {
*/
@Override
public <T extends Comparable<T>> T[] sort(T[] array) {
int length = array.length;
int gap = 1;

/* Calculate gap for optimization purpose */
while (gap < length / 3) {
gap = 3 * gap + 1;
if (array.length == 0) {
return array;
}

for (; gap > 0; gap /= 3) {
for (int i = gap; i < length; i++) {
int j;
T temp = array[i];
for (j = i; j >= gap && SortUtils.less(temp, array[j - gap]); j -= gap) {
array[j] = array[j - gap];
}
array[j] = temp;
}
int gap = calculateInitialGap(array.length);

while (gap > 0) {
performGapInsertionSort(array, gap);
gap = calculateNextGap(gap);
}

return array;
}

/* Driver Code */
public static void main(String[] args) {
Integer[] toSort = {4, 23, 6, 78, 1, 54, 231, 9, 12};
/**
* Calculates the initial gap value using the Knuth sequence.
*
* @param length the length of the array.
* @return the initial gap value.
*/
private int calculateInitialGap(final int length) {
int gap = 1;
while (gap < length / 3) {
gap = 3 * gap + 1;
}
return gap;
}

/**
* Calculates the next gap value.
*
* @param currentGap the current gap value.
* @return the next gap value.
*/
private int calculateNextGap(final int currentGap) {
return currentGap / 3;
}

ShellSort sort = new ShellSort();
sort.sort(toSort);
for (int i = 0; i < toSort.length - 1; ++i) {
assert toSort[i] <= toSort[i + 1];
/**
* Performs an insertion sort for the specified gap value.
*
* @param array the array to be sorted.
* @param gap the current gap value.
* @param <T> the type of elements in the array.
*/
private <T extends Comparable<T>> void performGapInsertionSort(final T[] array, final int gap) {
for (int i = gap; i < array.length; i++) {
T temp = array[i];
int j;
for (j = i; j >= gap && SortUtils.less(temp, array[j - gap]); j -= gap) {
array[j] = array[j - gap];
}
array[j] = temp;
}
SortUtils.print(toSort);
}
}
66 changes: 4 additions & 62 deletions src/test/java/com/thealgorithms/sorts/ShellSortTest.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,66 +1,8 @@
package com.thealgorithms.sorts;

import static org.junit.jupiter.api.Assertions.assertArrayEquals;

import org.junit.jupiter.api.Test;

public class ShellSortTest {

private ShellSort shellSort = new ShellSort();

@Test
public void shellSortEmptyArray() {
Integer[] inputArray = {};
Integer[] outputArray = shellSort.sort(inputArray);
Integer[] expectedOutput = {};
assertArrayEquals(outputArray, expectedOutput);
}

@Test
public void shellSortSingleIntegerArray() {
Integer[] inputArray = {4};
Integer[] outputArray = shellSort.sort(inputArray);
Integer[] expectedOutput = {4};
assertArrayEquals(outputArray, expectedOutput);
}

@Test
public void shellSortSingleStringArray() {
String[] inputArray = {"s"};
String[] outputArray = shellSort.sort(inputArray);
String[] expectedOutput = {"s"};
assertArrayEquals(outputArray, expectedOutput);
}

@Test
public void shellSortNonDuplicateIntegerArray() {
Integer[] inputArray = {6, -1, 99, 27, -15, 23, -36};
Integer[] outputArray = shellSort.sort(inputArray);
Integer[] expectedOutput = {-36, -15, -1, 6, 23, 27, 99};
assertArrayEquals(outputArray, expectedOutput);
}

@Test
public void shellSortDuplicateIntegerArray() {
Integer[] inputArray = {6, -1, 27, -15, 23, 27, -36, 23};
Integer[] outputArray = shellSort.sort(inputArray);
Integer[] expectedOutput = {-36, -15, -1, 6, 23, 23, 27, 27};
assertArrayEquals(outputArray, expectedOutput);
}

@Test
public void shellSortNonDuplicateStringArray() {
String[] inputArray = {"s", "b", "k", "a", "d", "c", "h"};
String[] outputArray = shellSort.sort(inputArray);
String[] expectedOutput = {"a", "b", "c", "d", "h", "k", "s"};
assertArrayEquals(outputArray, expectedOutput);
}

@Test
public void shellSortDuplicateStringArray() {
String[] inputArray = {"s", "b", "d", "a", "d", "c", "h", "b"};
String[] outputArray = shellSort.sort(inputArray);
String[] expectedOutput = {"a", "b", "b", "c", "d", "d", "h", "s"};
assertArrayEquals(outputArray, expectedOutput);
public class ShellSortTest extends SortingAlgorithmTest {
@Override
SortAlgorithm getSortAlgorithm() {
return new ShellSort();
}
}