6 ms·
You are right, heap sort doesn't need recursion, and is more efficient than shell sort for large arrays. But if you compare the code size, it is hard to beat sh
by thomasmg 4y ago
You are right, heap sort doesn't need recursion, and is more efficient than shell sort for large arrays. But if you compare the code size, it is hard to beat shell sort. This is a Java version:
static <T>void shellSort(T[] a, Comparator<T> c) {
int n = a.length;
int h = 16, g = 1;
while (n > g) {
h = h + h + h / 4 + 16;
g = (h + 15) / 16;
}
do {
h = (h - 16) * 4 / 9;
g = (h + 15) / 16;
for (int i = g; i < n; i++) {
T t = a[i];
int j = i;
for (; j >= g && c.compare(a[j - g], t) > 0; j -= g) {
a[j] = a[j - g];
}
a[j] = t;
}
} while (g > 1);
}
I was wondering, is there anything as simple as that, and similarly efficient? I doubt it.
- graycat 4y agoMy code examples for heaps could be shorter than what I posted if I omitted my verbose documentation, error handling, and double spacing!!