From 33613a85afc4b1481367fbe92a17ee59c240250b Mon Sep 17 00:00:00 2001
From: Sven Eisenhauer <sven@sven-eisenhauer.net>
Date: Fri, 10 Nov 2023 15:11:48 +0100
Subject: add new repo

---
 .../ARM202U/EXAMPLES/SORTS/SORTS.C                 | 135 +++++++++++++++++++++
 1 file changed, 135 insertions(+)
 create mode 100644 Bachelor/Mikroprozessorsysteme2/ARM202U/EXAMPLES/SORTS/SORTS.C

(limited to 'Bachelor/Mikroprozessorsysteme2/ARM202U/EXAMPLES/SORTS/SORTS.C')

diff --git a/Bachelor/Mikroprozessorsysteme2/ARM202U/EXAMPLES/SORTS/SORTS.C b/Bachelor/Mikroprozessorsysteme2/ARM202U/EXAMPLES/SORTS/SORTS.C
new file mode 100644
index 0000000..5a2afa2
--- /dev/null
+++ b/Bachelor/Mikroprozessorsysteme2/ARM202U/EXAMPLES/SORTS/SORTS.C
@@ -0,0 +1,135 @@
+#include <stdio.h>
+#include <time.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define N		1000
+
+#if N > 1000000
+#error "Value of N too big, must be <= 1000000"
+#endif
+
+#define LOG10_N    	6
+#define N_FORMAT  	"%06d"
+
+#if N <= 1000
+static void insert_sort(char *strings[], int n)
+{
+    char *v, *t;
+    char **strp, **endp;
+    int i;
+
+    endp = &strings[N-1];
+    i = N-2;
+    do {
+	strp = &strings[i];
+	v = strp[0];
+	do {
+	    t = strp[1];
+	    if (strcmp(v, t) <= 0) break;
+	    *strp++ = t;
+	} while (strp < endp);
+	strp[0] = v;
+    } while (--i >= 0);
+}
+#endif
+
+static void shell_sort(char *strings[], int n)
+{
+    int h, i, j;
+    char *v;
+
+    strings--;        /* Make array 1 origin */
+    h = 1;
+    do {h = h * 3 + 1;} while (h <= n);
+    do {
+	h = h / 3;
+        for (i = h + 1; i <= n; i++) {
+	    v = strings[i];
+            j = i;
+            while (j > h && strcmp(strings[j-h], v) > 0) {
+		strings[j] = strings[j-h];
+                j = j-h;
+            }
+            strings[j] = v;
+        }
+    }
+    while (h > 1);
+}
+
+static void randomise(char *strings[], int n)
+{
+    int i;
+    int v;
+    char *t;
+
+    /* srand(clock());	/* comment out for reproducible results */
+    for (i = 0; i < N; i++) {
+	v = rand() % N;
+	t = strings[v];
+	strings[v] = strings[i];
+	strings[i] = t;
+    }
+}
+
+static void check_order(char *sort_type, char *strings[], int n)
+{
+    int i;
+
+    for (i = 0; i < n; i++) {
+	if (atoi(strings[i]) != i) {
+	    fprintf(stderr, "%s sort failed - exiting\n", sort_type);
+	    exit(1);
+	}
+    }
+}
+
+int qs_string_compare(const void *a, const void *b)
+{
+    return strcmp(*(char **)a, *(char **)b);
+}
+
+int main(void)
+{
+    char *strings[N], *strings_copy[N];
+    char buffer[N*(LOG10_N+1)];
+    char *p;
+    clock_t starttime, endtime;
+    int i;
+
+    p = buffer;
+    for (i = 0; i < N; i++) {
+	sprintf(p, N_FORMAT, i);
+	strings[i] = p;
+	p += LOG10_N+1;
+    }
+    randomise(strings, N);
+
+#if N <= 1000
+    /* Do insertion sort */
+    memcpy(strings_copy, strings, sizeof(strings));
+    starttime = clock();
+    insert_sort(strings_copy, N);
+    endtime = clock();
+    check_order("Insertion", strings_copy, N);
+    printf("Insertion sort took %d clock ticks\n", endtime - starttime);
+#else
+    printf("Value of N too big to use insertion sort, must be <= 1000\n");
+#endif
+
+    /* Do shell sort */
+    memcpy(strings_copy, strings, sizeof(strings));
+    starttime = clock();
+    shell_sort(strings_copy, N);
+    endtime = clock();
+    check_order("Shell", strings_copy, N);
+    printf("Shell sort took %d clock ticks\n", endtime - starttime);
+
+    /* Do quick sort - use built-in C library sort */
+    memcpy(strings_copy, strings, sizeof(strings));
+    starttime = clock();
+    qsort(strings_copy, N, sizeof(char *), qs_string_compare);
+    endtime = clock();
+    check_order("Quick", strings_copy, N);
+    printf("Quick sort took %d clock ticks\n", endtime - starttime);
+}
-- 
cgit v1.2.3