Shell Sort

[sourcecode language=”java” collapse=”false”]
/* Method: shellSort
* Arguments: array, lowindex, highindex, reversed
* Notes: Performs shell sort on an array with comparable elements using Hibbard’s Increments (1, 3, 7, 15, … 2k-1), between the specified indices (lowindex and highindex). Function also has the feature of sorting backwards, depending on whether or not "reversed" is true (reverse) or false (don’t reverse).
*/

public void shellSort(Comparable[] array, int lowindex, int highindex, boolean reversed) {

Comparable curr;
int length = highindex – lowindex + 1;
int i, j, increment;
i = j = increment = 1;

while (true) {
if (increment * 2 – 1 < length)
increment *= 2;
else
break;
}

increment–;

if (!reversed) {
for (i = increment; i <= highindex && increment >= 1; i += increment) {
curr = array[i];
for (j = i – increment; j >= lowindex && array[j].compareTo(curr) > 0; j -= increment)
array[j + increment] = array[j];
array[j + increment] = curr;

if (i + increment > highindex) {
increment /= 2;
i = 0;
}
}
}

else { // Reverse the array
for (i = increment; i <= highindex && increment >= 1; i += increment) {
curr = array[i];
for (j = i – increment; j >= lowindex && array[j].compareTo(curr) < 0; j -= increment)
array[j + increment] = array[j];
array[j + increment] = curr;

if (i + increment > highindex) {
increment /= 2;
i = 0;
}
}
}
}
[/sourcecode]

Leave a Reply

Your email address will not be published. Required fields are marked *