From 498b794ce5bae04495d916380927e9be23591e49 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Wed, 29 Dec 2021 13:37:57 +0100
Subject: feat: implement insertsort

---
 .gitignore   |  1 +
 insertsort.c | 38 ++++++++++++++++++++++++++++++++++++++
 makefile     |  7 +++++--
 3 files changed, 44 insertions(+), 2 deletions(-)
 create mode 100644 insertsort.c

diff --git a/.gitignore b/.gitignore
index 920e322..4d1c44f 100644
--- a/.gitignore
+++ b/.gitignore
@@ -16,4 +16,5 @@ stack
 stack2
 tags
 tree
+insertsort
 
diff --git a/insertsort.c b/insertsort.c
new file mode 100644
index 0000000..1a30a1a
--- /dev/null
+++ b/insertsort.c
@@ -0,0 +1,38 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#include "util.h"
+
+typedef int T;
+
+void
+insertsort(T a[], size_t n)
+{
+	for ( size_t i = 1; i < n; ++i ) {
+		size_t  j     = i;
+		const T value = a[i];
+
+		for ( ; j > 0 && a[j - 1] > value; --j )
+			a[j] = a[j - 1];
+
+		a[j] = value;
+	}
+}
+
+int
+main(void)
+{
+	T a[10];
+
+	srand(time(NULL));
+	for ( size_t i = 0; i != NELEM(a); ++i )
+		a[i] = rand() % 100;
+
+	insertsort(a, NELEM(a));
+
+	for ( size_t i = 0; i != NELEM(a); ++i )
+		printf("%d ", a[i]);
+	putchar('\n');
+	return EXIT_SUCCESS;
+}
diff --git a/makefile b/makefile
index c83159e..6bbb98a 100644
--- a/makefile
+++ b/makefile
@@ -2,7 +2,7 @@
 
 CFLAGS=-Wall -Werror -Wextra -Wno-unused-function -Wsign-conversion -pedantic -std=c99 -g
 
-all: list list-tail-node dlist stack stack2 queue ringbuff hashtab tree avl heap quicksort allocator rb deque arraylist
+all: list list-tail-node dlist stack stack2 queue ringbuff hashtab tree avl heap quicksort allocator rb deque arraylist insertsort
 
 list: list.c util.h
 	cc $(CFLAGS) $< -o $@
@@ -52,6 +52,9 @@ allocator: allocator.c allocator.h
 arraylist: arraylist.c util.h
 	cc $(CFLAGS) $< -o $@
 
+insertsort: insertsort.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
+	rm -f list list-tail-node dlist stack stack2 queue ringbuff hashtab tree avl heap quicksort allocator rb deque arraylist insertsort
 
-- 
cgit v1.3