From 20ad66e839dbc632b844f1c03137efa1a457f5fd Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sat, 1 Jan 2022 12:27:32 +0100
Subject: feat: implement shellsort

---
 .gitignore  |  2 +-
 makefile    |  8 ++++++--
 shellsort.c | 64 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 71 insertions(+), 3 deletions(-)
 create mode 100644 shellsort.c

diff --git a/.gitignore b/.gitignore
index 4d1c44f..08b10b0 100644
--- a/.gitignore
+++ b/.gitignore
@@ -17,4 +17,4 @@ stack2
 tags
 tree
 insertsort
-
+shellsort
diff --git a/makefile b/makefile
index 6bbb98a..14f5db3 100644
--- a/makefile
+++ b/makefile
@@ -1,8 +1,9 @@
 .PHONY: all clean
 
 CFLAGS=-Wall -Werror -Wextra -Wno-unused-function -Wsign-conversion -pedantic -std=c99 -g
+BINS=list list-tail-node dlist stack stack2 queue ringbuff hashtab tree avl heap quicksort allocator rb deque arraylist insertsort shellsort
 
-all: list list-tail-node dlist stack stack2 queue ringbuff hashtab tree avl heap quicksort allocator rb deque arraylist insertsort
+all: $(BINS)
 
 list: list.c util.h
 	cc $(CFLAGS) $< -o $@
@@ -55,6 +56,9 @@ arraylist: arraylist.c util.h
 insertsort: insertsort.c util.h
 	cc $(CFLAGS) $< -o $@
 
+shellsort: shellsort.c util.h
+	cc $(CFLAGS) $< -o $@
+
 clean:
-	rm -f list list-tail-node dlist stack stack2 queue ringbuff hashtab tree avl heap quicksort allocator rb deque arraylist insertsort
+	rm -f $(BINS)
 
diff --git a/shellsort.c b/shellsort.c
new file mode 100644
index 0000000..b19f547
--- /dev/null
+++ b/shellsort.c
@@ -0,0 +1,64 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#include "util.h"
+
+typedef int T;
+
+void
+shellsort(T a[], size_t n)
+{
+	//static const size_t gaps[] = { 701, 301, 132, 57, 23, 10, 4, 1 };
+
+	// Wikipedia:
+	//static const size_t gaps[] = { 2147483647, 1131376761, 410151271, 157840433, 58548857, 21521774, 8810089, 3501671, 1355339, 543749, 213331, 84801, 27901, 11969, 4711, 1968, 815, 271, 111, 41, 13, 4, 1 };
+
+	// https://www.cs.princeton.edu/~rs/shell/paperF.pdf
+	static const size_t gaps[] = { 1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1 };
+
+	for ( size_t k = 0; k < NELEM(gaps); ++k ) {
+		const size_t gap = gaps[k];
+
+		for ( size_t i = gap; i < n; i++ ) {
+			size_t j    = i;
+			T      temp = a[i];
+
+			for ( ; j >= gap && a[j - gap] > temp; j -= gap )
+				a[j] = a[j - gap];
+
+			a[j] = temp;
+		}
+	}
+}
+
+static void
+test(T a[], size_t n)
+{
+	for ( size_t i = 1; i < n; ++i ) {
+		if ( a[i - 1] > a[i] ) {
+			fprintf(stderr, "Error\n");
+			exit(EXIT_FAILURE);
+		}
+	}
+}
+
+int
+main(void)
+{
+	T a[1000000];
+
+	srand(time(NULL));
+	for ( size_t i = 0; i != NELEM(a); ++i )
+		a[i] = rand() % 1000;
+
+	clock_t start = clock();
+	shellsort(a, NELEM(a));
+	clock_t end = clock();
+
+	test(a, NELEM(a));
+
+	printf("duration: %.3f sec\n", ((double) (end - start)) / CLOCKS_PER_SEC);
+
+	return EXIT_SUCCESS;
+}
-- 
cgit v1.3